Zugriff auf map-Wert von index

Wenn ich eine Struktur haben, wie

std::map<string, int> myMap;
myMap["banana"] = 1;
myMap["apple"] = 1;
myMap["orange"] = 1;

Wie kann ich auf myMap[0]?

Ich weiß, dass die Karte Arten intern und ich bin mit diesem feinen, ich möchte einen Wert in der map-index. Ich habe versucht myMap[0], aber ich bekomme die Fehlermeldung:

Error   1   error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)

Ich begreife, dass ich tun könnte etwas wie diese:

string getKeyAtIndex (int index){
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0;
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) {
        counter++;

        if (counter == index)
            return it->first;
    }
}

Aber sicher ist dies äußerst ineffizient? Gibt es einen besseren Weg?

InformationsquelleAutor Sam | 2011-10-21
  1. 22

    Ihre map soll nicht zugegriffen werden, die Art und Weise, ist es indiziert, die durch Tasten nicht durch Positionen. Ein map iterator bidirektionale, genau wie ein list, also die Funktion, die Sie verwenden, ist nicht ineffizienter als der Zugriff auf eine list nach position. Ihre Funktion geschrieben werden kann, mit Hilfe von std::advance( iter, index ) ab begin(). Wenn Sie möchten, random access durch die position dann mit einem vector oder eine deque.

    InformationsquelleAutor K-ballo
  2. 4

    Vorherigen Antwort (siehe Kommentar): Wie wäre es einfach myMap.begin();

    Könnten Sie implementieren eine random-access-Karte mithilfe eines Vektor-backing-store, die ist im wesentlichen ein Vektor von Paaren. Sie natürlich verlieren alle Vorteile der standard-Bibliothek Karte an diesem Punkt.

    • Ich sehe jetzt,... Du willst den wahlfreien Zugriff. Index 0 war nur ein Beispiel, nicht das eigentliche Ziel.
    InformationsquelleAutor Michael Price
  3. 4

    Gibt es vielleicht eine Umsetzung von spezifischen (nicht-portable) - Methode, um Ihr Ziel zu erreichen, aber nicht eine, die tragbar ist.

    Im Allgemeinen, die std::map ist implementiert als eine Art binärer Baum, in der Regel sortiert nach dem key. Die definition des ersten Elements unterscheidet sich je nach Bestellung. Auch in Ihrer definition, ist element[0] den Knoten an der Spitze des Baumes oder der linke Blattknoten?

    Viele binäre Bäume implementiert werden, die als verknüpfte Listen. Die meisten verlinkten Listen können nicht direkt aufgerufen werden wie ein array, da element 5, Sie haben zu Folgen Sie den links. Dies ist per definition.

    Können Sie dieses Problem beheben, indem Sie sowohl eine std::vector und ein std::map:

    1. Reservieren das Objekt vom dynamischen Speicher.
    2. Speichern Sie die Zeiger, zusammen mit dem Schlüssel in der std::map.
    3. Speichern der Zeiger in der std::vector an die gewünschte position
      an.

    Den std::map es erlauben, eine effiziente Methode für den Zugriff auf das Objekt durch die-Taste.

    Die std::vector es erlauben, eine effiziente Methode für den Zugriff auf den Objekt-index.
    Speichern von Zeigern erlaubt nur eine Instanz des Objekts, anstatt zur Pflege mehrerer Kopien.

    • Und dann, was tun Sie mit dem Vektor, wenn Sie müssen, legen Sie ein neues element in die Karte?
    • Eine interessante alternative ist das speichern von einem Vektor von Iteratoren auf die Karte neben der Karte. Auf diese Weise können Sie den Zugriff auf den Schlüssel und den Wert jedes Elementes Ihrer Karte, die durch den index ohne die Speicherung entweder von Ihnen wieder. Natürlich, würden Sie immer noch benötigen, um die Vektor-Synchronisierung auf der Karte - append-iterator für das einfügen, entfernen iterator (O(N)) vor der Löschung.
    InformationsquelleAutor Thomas Matthews
  4. 3

    Gut, eigentlich kann man es nicht. Die Art und Weise, die Sie gefunden haben, ist sehr unefficient, Sie haben eine rechnerische Komplexität von O(n) (n Operationen worst-case, wobei n die Anzahl der Elemente in einer Karte).

    Zugriff auf ein Element in einem Vektor oder in einem array haben Komplexität O(1) durch Vergleich (Konstante Komplexität, die eine einzelne operation).

    Bedenkt, dass Karte ist intern umgesetzt, als rot-schwarz-Baum (oder avl-Baum, es hängt von der Implementierung) und jeder insert -, delete-und lookup-operation sind O(log n) worst case (es erfordert Logarithmus zur Basis 2 Operationen zum finden eines Elements in der Baumstruktur), das ist ziemlich gut.

    Einer Weise, die Sie behandeln können, ist die Verwendung einer benutzerdefinierten Klasse, die haben innen sowohl eine Vektor-und eine Karte.
    Einfügen am Ende der Klasse werden durchschnittlich O(1), Suche nach Namen werden in O(log n), - Suche nach index O(1) aber in diesem Fall, entfernen operation O(n).

    InformationsquelleAutor Salvatore Previti
  5. 1

    können Sie eine andere Karte wie Behältern .

    halten Sie eine Größe der Felder machen kann binary search tree einfach zu random access .

    hier ist meine Umsetzung ...

    std-Stil , random-access-iterator ...

    Größe ausgeglichenen Baum ...

    https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h

    und B+ - Baum ...

    https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

    • Willkommen ALSO! Versuchen Sie zu vermeiden link nur Antworten, weil der link gebrochen werden kann in Zukunft, nur sind einige Ausschnitte aus diesem link in deine Antwort, Sie pflegen den link, aber bitte, etwas mehr auf Ihre Antwort, und versuchen zu erklären, warum Sie denken, es ist eine gute Idee.
    InformationsquelleAutor 奏之章
Schreibe einen Kommentar