In welchem ​​Szenario verwende ich einen bestimmten STL-Container?

Ich habe in meinem Buch über C ++ über STL-Container gelesen, insbesondere über den Abschnitt über die STL und ihre Container. Jetzt verstehe ich, dass jeder von ihnen seine eigenen spezifischen Eigenschaften hat, und ich bin kurz davor, sie alle auswendig zu lernen ... Aber was ich noch nicht verstehe, ist, in welchem ​​Szenario jeder von ihnen verwendet wird.

Was ist die Erklärung? Beispielcode wird sehr bevorzugt.

Dieser Spickzettel bietet eine ziemlich gute Zusammenfassung der verschiedenen Container.

Im Flussdiagramm unten finden Sie eine Anleitung zur Verwendung in verschiedenen Verwendungsszenarien:

_{Erstellt von David Moore und lizenziert CC BY-SA 3.0}

Hier ist ein Flussdiagramm, das von der von mir erstellten Version von David Moore (siehe oben) inspiriert ist und (meistens) mit dem neuen Standard (C ++ 11) auf dem neuesten Stand ist. Dies ist nur meine persönliche Einstellung, es ist nicht unbestreitbar, aber ich dachte, es könnte für diese Diskussion wertvoll sein:

Einfache Antwort: Verwenden Sie std::vectorfür alles, es sei denn, Sie haben einen wirklichen Grund, etwas anderes zu tun.

Wenn Sie einen Fall finden, in dem Sie denken: "Gee, std::vectorfunktioniert hier wegen X nicht gut", gehen Sie auf der Grundlage von X.

Schauen Sie sich Effective STL von Scott Meyers an. Es ist gut zu erklären, wie man die STL benutzt.

Wenn Sie eine bestimmte / unbestimmte Anzahl von Objekten speichern möchten und niemals Objekte löschen möchten, ist ein Vektor genau das, was Sie möchten. Es ist der Standardersatz für ein C-Array und funktioniert wie eines, läuft aber nicht über. Sie können die Größe auch vorher mit Reserve () einstellen.

Wenn Sie eine unbestimmte Anzahl von Objekten speichern möchten, diese aber hinzufügen und löschen möchten, möchten Sie wahrscheinlich eine Liste ... weil Sie ein Element löschen können, ohne die folgenden Elemente zu verschieben - im Gegensatz zu Vektoren. Es benötigt jedoch mehr Speicher als ein Vektor, und Sie können nicht nacheinander auf ein Element zugreifen.

Wenn Sie eine Reihe von Elementen nehmen und nur die eindeutigen Werte dieser Elemente finden möchten, reicht es aus, sie alle in eine Menge einzulesen und sie auch für Sie zu sortieren.

Wenn Sie viele Schlüssel-Wert-Paare haben und diese nach Schlüssel sortieren möchten, ist eine Zuordnung nützlich ... aber sie enthält nur einen Wert pro Schlüssel. Wenn Sie mehr als einen Wert pro Schlüssel benötigen, können Sie einen Vektor / eine Liste als Wert in der Karte haben oder eine Multimap verwenden.

Es ist nicht in der STL enthalten, aber es ist im TR1-Update der STL enthalten: Wenn Sie viele Schlüssel-Wert-Paare haben, werden Sie nach Schlüssel suchen, und Sie interessieren sich möglicherweise nicht für deren Reihenfolge möchte einen Hash verwenden - das ist tr1 :: unordered_map. Ich habe es mit Visual C ++ 7.1 verwendet, wo es stdext :: hash_map hieß. Es hat eine Suche von O (1) anstelle einer Suche von O (log n) für die Karte.

Ich habe das Flussdiagramm neu gestaltet, um 3 Eigenschaften zu haben:

1. Ich denke, STL-Container sind in zwei Hauptklassen unterteilt. Die Basiscontainer und diese nutzen die Basiscontainer, um eine Richtlinie zu implementieren.
2. Zuerst sollte das Flussdiagramm den Entscheidungsprozess in die Hauptsituationen aufteilen, über die wir entscheiden sollten, und dann jeden Fall näher erläutern.
3. Einige erweiterte Container haben die Möglichkeit, verschiedene Basiscontainer als Innencontainer zu wählen. Das Flussdiagramm sollte die Situationen berücksichtigen, in denen jeder der Basiscontainer verwendet werden kann.

Das Flussdiagramm:

Weitere Informationen finden Sie unter diesem Link .

Ein wichtiger Punkt nur kurz so weit erwähnt, ist , dass , wenn Sie zusammenhängenden Speicher erfordern (wie ein C - Array gibt), dann können Sie nur verwenden vector, arrayoder string.

Verwenden Sie arraydiese Option, wenn die Größe zur Kompilierungszeit bekannt ist.

Verwenden stringSie diese Option, wenn Sie nur mit Zeichentypen arbeiten müssen und eine Zeichenfolge benötigen, nicht nur einen Allzweckcontainer.

Verwendung vectorin allen anderen Fällen ( vectorsollte in den meisten Fällen ohnehin die Standardauswahl für Container sein).

Mit allen drei können Sie data()die Elementfunktion verwenden, um einen Zeiger auf das erste Element des Containers zu erhalten.

Es hängt alles davon ab, was Sie speichern möchten und was Sie mit dem Container tun möchten. Hier sind einige (sehr nicht erschöpfende) Beispiele für die Containerklassen, die ich am häufigsten verwende:

vector: Kompaktes Layout mit geringem oder keinem Speicheraufwand pro enthaltenem Objekt. Effizient zu iterieren. Das Anhängen, Einfügen und Löschen kann insbesondere bei komplexen Objekten teuer sein. Günstig, um ein enthaltenes Objekt anhand des Index zu finden, z. B. myVector [10]. Verwenden Sie, wo Sie ein Array in C verwendet hätten. Gut, wo Sie viele einfache Objekte haben (z. B. int). Vergessen Sie nicht, es zu verwenden, reserve()bevor Sie dem Container viele Objekte hinzufügen.

list: Kleiner Speicheraufwand pro enthaltenem Objekt. Effizient zu iterieren. Anhängen, Einfügen und Löschen sind billig. Verwenden Sie, wo Sie eine verknüpfte Liste in C verwendet hätten.

set(und multiset): Signifikanter Speicheraufwand pro enthaltenem Objekt. Verwenden Sie diese Option, um schnell herauszufinden, ob dieser Container ein bestimmtes Objekt enthält, oder um Container effizient zusammenzuführen.

map(und multimap): Signifikanter Speicheraufwand pro enthaltenem Objekt. Verwenden Sie diese Option, um Schlüssel-Wert-Paare zu speichern und Werte nach Schlüssel schnell nachzuschlagen.

Das von zdan vorgeschlagene Flussdiagramm auf dem Spickzettel bietet eine ausführlichere Anleitung.

Eine Lektion, die ich gelernt habe, ist: Versuchen Sie, sie in eine Klasse einzupacken, da das Ändern des Containertyps an einem schönen Tag große Überraschungen bringen kann.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Es kostet im Voraus nicht viel und spart Zeit beim Debuggen, wenn Sie eine Unterbrechung durchführen möchten, wenn jemand die Operation x für diese Struktur ausführt.

Zur Auswahl der perfekten Datenstruktur für einen Job:

Jede Datenstruktur bietet einige Operationen, die zeitlich unterschiedlich sein können:

O (1), O (lg N), O (N) usw.

Sie müssen im Wesentlichen eine Vermutung anstellen, welche Operationen am häufigsten ausgeführt werden, und eine Datenstruktur verwenden, die diese Operation als O (1) hat.

Einfach, nicht wahr (-:

Ich habe das fantastische Flussdiagramm von Mikael Persson erweitert . Ich habe einige Containerkategorien, den Array-Container und einige Notizen hinzugefügt. Wenn Sie eine eigene Kopie wünschen, finden Sie hier die Google-Zeichnung. Danke, Mikael, dass du die Grundlagen geschaffen hast! C ++ Container Picker

Ich habe dies in einer anderen Frage beantwortet, die als Dup dieser Frage markiert ist. Ich finde es jedoch schön, einige gute Artikel über die Entscheidung für einen Standardbehälter zu lesen.

Wie @David Thornley antwortete, ist std :: vector der richtige Weg, wenn es keine anderen speziellen Anforderungen gibt. Dies ist der Rat des Entwicklers von C ++, Bjarne Stroustrup, in einem Blog von 2014.

Hier ist der Link zum Artikel https://isocpp.org/blog/2014/06/stroustrup-lists

und zitiere aus diesem,

Und ja, meine Empfehlung ist, standardmäßig std :: vector zu verwenden.

In den Kommentaren bietet Benutzer @NathanOliver auch einen weiteren guten Blog an, der konkretere Messungen enthält. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .