Sortierreihenfolge in STL map und set

Question

Wie sind die benutzerdefinierten Objekte in Map und Set sortiert? Soweit ich weiß, sind map/set sortierte assoziative Container: Die einzufügenden Elemente werden basierend auf dem Schlüssel sortiert, den sie enthält.

Aber Karte und Satz intern verwenden operator >, um ihre Elemente zu sortieren.

Von der SGI-Website, ich habe die folgenden Beispiele:

struct ltstr 
{ 
    bool operator()(const char* s1, const char* s2) const 
    { 
     return strcmp(s1, s2) < 0; 
    } 
}; 

int main() 
{ 
    map<const char*, int, ltstr> months; 

    months["january"] = 31; 
    months["february"] = 28; 
    months["march"] = 31; 
    months["april"] = 30; 
    months["may"] = 31; 
    months["june"] = 30; 
    months["july"] = 31; 
    months["august"] = 31; 
    months["september"] = 30; 
    months["october"] = 31; 
    months["november"] = 30; 
    months["december"] = 31; 

    cout << "june -> " << months["june"] << endl; 

    map<const char*, int, ltstr>::iterator cur = months.find("june"); 
    map<const char*, int, ltstr>::iterator prev = cur; 
    map<const char*, int, ltstr>::iterator next = cur; 

    ++next; 
    --prev; 

    cout << "Previous (in alphabetical order) is " << (*prev).first << endl; 
    cout << "Next (in alphabetical order) is " << (*next).first << endl; 
} 

Im obigen Beispiel, wie die Werte sortieren?

bearbeiten: Code aus Kommentar bewegt:

typedef map <string, int> Mint ; 

int main() 
{ 
    string Name ; 
    int Marks; 
    Mint Grade; 
    for (int i = 0; i<4; i++) 
    { 
     cin>> Name ; 
     cin >> Marks; 
     Grade [Name] = Marks ; 
    } 
    Mint :: iterator iter; 
    for(iter = Grade.begin(); iter != Grade.end(); iter++) 
     cout<< (*iter).first<<“ \t ” <<(*iter).second<<“\n” ; 
    return 0; 

} 

Wie würden die Werte sortiert werden?

Answer 1

std::map verwendet einen Funktor zum Sortieren von Elementen. Standardmäßig ist es std::less<Key>, die operator< verwendet. In Ihrem Beispiel gibt es einen benutzerdefinierten Funktor ltstr, der hilft, Elemente nach ihren Schlüsseln in alphabetischer Reihenfolge zu sortieren.

Answer 2

Zuerst wird operator< standardmäßig verwendet und nicht operator>. In Ihrem Fall übergeben Sie eine benutzerdefinierte Vergleichsfunktion, indem Sie beim Erstellen des Kartenobjekts den dritten Vorlagenparameter übergeben. Während jedes Element in die Karte eingefügt wird, wird dieser Vergleichsfunktor verwendet, um die relative Reihenfolge des Objekts in der Karte zu bestimmen, d. H. Es wird verwendet, um die Schlüssel zu vergleichen. Zum Beispiel, wenn Sie months["february"] = 28; tun, vergleicht map die Tasten "Januar" und "Februar". Da wir einen Zeichenkettenvergleich durchführen, gibt dieser Vergleich einen Wert größer als 0 zurück. Dieser Wert wird verwendet, um die Position des Schlüssels "Februar" in Bezug auf "Januar" zu bestimmen.