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

184

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.

Daniel Sloof
quelle
meinst du map, vectot, set etc?
Thomas Tempelmann
Selbst wenn ich mir dieses Diagramm ansehe, kann ich nicht sagen, welches das beste ist, um es in meinem Quastion stackoverflow.com/questions/9329011/…
Sergiol
2
@sbi: Entfernen des C ++ - Faq-Tags aus diesem Tag und Hinzufügen zum neueren und C ++ 11-Tag Wie kann ich einen Standardbibliothekscontainer in C ++ 11 effizient auswählen?
Alok Save

Antworten:

336

Dieser Spickzettel bietet eine ziemlich gute Zusammenfassung der verschiedenen Container.

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

http://linuxsoftware.co.nz/containerchoice.png

Erstellt von David Moore und lizenziert CC BY-SA 3.0

zdan
quelle
14
Dieses Flussdiagramm ist golden, ich wünschte, ich hätte so etwas in c #
Bruno
2
Aktualisierter Link: C ++ Containers Cheat Sheet .
Bill Door
3
Der Ausgangspunkt muss vectoreher leer als leer sein. stackoverflow.com/questions/10699265/…
Eonil
5
Sie haben jetzt unordered_mapund unordered_set(und ihre Multi-Varianten), die nicht im Flussdiagramm enthalten sind, aber gute Tipps sind, wenn Sie sich nicht um die Reihenfolge kümmern, sondern Elemente nach Schlüssel suchen müssen. Ihre Suche ist normalerweise O (1) anstelle von O (log n).
Aidiakapi
2
@ shuttle87 nicht nur diese Größe wird niemals variieren, sondern vor allem, dass die Größe zur Kompilierungszeit bestimmt wird und niemals variieren wird.
YoungJohn
188

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:

Geben Sie hier die Bildbeschreibung ein

Mikael Persson
quelle
4
Können Sie das Original zur Verfügung stellen? Es ist ein ausgezeichnetes Diagramm. Vielleicht auf einem Blog oder GitHub bleiben?
Kevinarpe
1
Dies ist ein ausgezeichnetes Diagramm. Kann mir jemand erklären, was unter "hartnäckigen Positionen" zu verstehen ist?
IDDQD
3
@STALKER Persistente Positionen bedeutet, dass, wenn Sie einen Zeiger oder Iterator auf ein Element im Container haben, dieser Zeiger oder Iterator gültig bleibt (und auf dasselbe Element zeigt), unabhängig davon, was Sie dem Container hinzufügen oder daraus entfernen (solange es vorhanden ist) ist nicht das fragliche Element).
Mikael Persson
1
Dies ist wirklich ein großartiges Diagramm, aber ich denke, es vector (sorted)ist ein bisschen unvereinbar mit dem Rest. Es ist kein anderer Containertyp, nur derselbe, std::vectoraber sortiert. Noch wichtiger ist, ich verstehe nicht, warum man eine std::setfür geordnete Iteration nicht verwenden kann , wenn dies das Standardverhalten der Iteration durch eine Menge ist. Sicher, wenn es in der Antwort um den ordnungsgemäßen Zugriff auf die Werte des Containertrogs geht [], können Sie dies nur mit einem Soted tun std::vector. Aber in jedem Fall sollte die Entscheidung unmittelbar nach der Frage "Bestellung ist erforderlich" getroffen werden
RAs
1
@ user2019840 Ich wollte das Diagramm auf Standardcontainer beschränken. Was anstelle von "sortiertem Vektor" erscheinen sollte, ist "flat_set" (von Boost.Container ) oder ein Äquivalent (jede Hauptbibliothek oder Codebasis hat ein flat_set-Äquivalent, AFAIK). Aber diese sind nicht standardisiert und eine ziemlich krasse Auslassung aus der STL. Und der Grund, warum Sie nicht durch std :: set oder std :: map iterieren möchten (zumindest nicht häufig), ist, dass dies sehr ineffizient ist .
Mikael Persson
42

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.

David Thornley
quelle
1
Achten Sie jedoch darauf, beim Iterieren keine Elemente zu löschen / einzufügen. Verwenden Sie const_iterator so weit wie möglich, um dies zu vermeiden.
vrdhn
11
Hmm ... Ich denke, die Leute verwenden Vektoren übermäßig. Der Grund dafür ist, dass der Fall "funktioniert nicht" nicht einfach vorkommt. Die Leute halten sich also an den am häufigsten verwendeten Container und missbrauchen ihn zum Speichern von Listen, Warteschlangen, ... Meiner Meinung nach - das entspricht dem Flussdiagramm - man sollte den Behälter basierend auf dem Verwendungszweck auswählen, anstatt den "man scheint für alle zu passen" anzuwenden.
Schwarz
13
@Black Point ist, dass der Vektor normalerweise schneller ist, selbst bei Operationen, die theoretisch langsamer arbeiten sollten.
Bartek Banachewicz
1
@Vardhan std::remove_ifist dem Ansatz "Während der Iteration löschen" fast immer überlegen.
Fredoverflow
1
Einige Benchmarks würden dieser Diskussion wirklich helfen, weniger subjektiv zu sein.
Felix D.
11

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.

Mark Krenitsky
quelle
Ich habe jetzt ein paar Anekdoten gehört, die darauf hindeuten, dass Microsoft hash_mapkeine sehr gute Implementierung ist. Ich hoffe, sie haben es besser gemacht unordered_map.
Mark Ransom
3
Von Listen - "Sie können nicht nacheinander auf ein Element zugreifen." - Ich denke, Sie meinen, Sie können nicht direkt auf ein Element zugreifen oder es direkt indizieren ...
Tony Delroy
^ Ja, denn sequentieller Zugriff ist genau das, was a listtut. Eher eklatanter Fehler da.
underscore_d
7

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: Geben Sie hier die Bildbeschreibung ein

Weitere Informationen finden Sie unter diesem Link .

Ebrahim
quelle
5

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.

Jonathan Wakely
quelle
3

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.

Gebote
quelle
"Kleiner Speicheraufwand pro enthaltenem Objekt" gilt nicht für die Liste. std :: list ist als doppelt verknüpfte Liste implementiert und behält daher 2 Zeiger pro gespeichertem Objekt bei, die nicht zu vernachlässigen sind.
Hanna Khalil
Ich würde immer noch zwei Zeiger pro gespeichertem Objekt als "klein" zählen.
Gebote
verglichen mit was? std :: forward_list ist ein Container, in dem hauptsächlich weniger Metadaten pro Objekt gespeichert werden sollen (nur ein Zeiger). Während std :: vector 0 Metadaten pro Objekt enthält. 2 Zeiger sind also im Vergleich zu anderen Containern nicht verhandelbar
Hanna Khalil
Es hängt alles von der Größe Ihrer Objekte ab. Ich habe bereits gesagt, dass der Vektor ein "kompaktes Layout mit wenig oder keinem Speicheraufwand pro enthaltenem Objekt" hat. Ich würde immer noch sagen, dass die Liste im Vergleich zu Set und Map einen geringen Speicheraufwand und einen etwas größeren Speicheraufwand als der Vektor hat. Ich bin mir nicht sicher, an welchem ​​Punkt Sie versuchen, TBH zu machen!
Gebote
Alle modebasierten Container haben aufgrund der dynamischen Zuweisung, die selten kostenlos ist, tendenziell einen erheblichen Overhead. Es sei denn, Sie verwenden einen benutzerdefinierten Allokator.
MikeMB
2

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 (-:

vrdhn
quelle
5
Verwenden wir deshalb nicht Iteratoren?
Platinum Azure
@PlatinumAzure Sogar Iteratoren sollten Mitglied typedef sein. Wenn Sie den Containertyp ändern, müssen Sie auch alle Iteratordefinitionen ändern ... dies wurde jedoch in c ++ 1x behoben!
vrdhn
4
Für den Neugierigen ist dies der Fix in C ++ 11: auto myIterator = whateverCollection.begin(); // <-- immune to changes of container type
Black
1
Wäre ein typedef Collection<Foo*> CollectionOfFoo;ausreichend?
Craig McQueen
5
Es ist ziemlich unwahrscheinlich, dass Sie Ihre Meinung später ändern und einfach an einen anderen Container delegieren können: Hüten Sie sich vor der Illusion von containerunabhängigem Code
fredoverflow
1

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

John DiFini
quelle
1

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 .

CS Pei
quelle