Wie kann ich einen Standardbibliothekscontainer in C ++ 11 effizient auswählen?

Es gibt ein bekanntes Bild (Spickzettel) namens "C ++ Container Choice". Es ist ein Flussdiagramm, um den besten Container für die gewünschte Verwendung auszuwählen.

Weiß jemand, ob es bereits eine C ++ 11-Version davon gibt?

Dies ist der vorherige:

Nicht das ich wüsste, aber es kann in Textform gemacht werden, denke ich. Außerdem ist das Diagramm leicht abweichend, da listes im Allgemeinen kein so guter Container ist und auch nicht forward_list. Beide Listen sind sehr spezialisierte Container für Nischenanwendungen.

Um ein solches Diagramm zu erstellen, benötigen Sie nur zwei einfache Richtlinien:

• Wählen Sie zuerst für die Semantik
• Wenn mehrere Optionen verfügbar sind, wählen Sie die einfachste

Sich um die Leistung zu sorgen, ist normalerweise zunächst nutzlos. Die großen O-Überlegungen spielen erst dann eine Rolle, wenn Sie mit der Bearbeitung einiger Tausender (oder mehr) Gegenstände beginnen.

Es gibt zwei große Kategorien von Containern:

• Assoziative Container: Sie haben eine findOperation
• Einfache Sequenzcontainer

und dann können Sie mehrere Adapter auf sie bauen: stack, queue, priority_queue. Ich werde die Adapter hier draußen lassen, sie sind ausreichend spezialisiert, um erkennbar zu sein.

Frage 1: Assoziativ ?

• Wenn Sie einfach nach einem Schlüssel suchen müssen, benötigen Sie einen assoziativen Container
• Wenn Sie die Elemente sortieren müssen, benötigen Sie einen geordneten assoziativen Container
• Andernfalls springen Sie zu Frage 2.

Frage 1.1: Bestellt ?

• Wenn Sie keine bestimmte Bestellung benötigen, verwenden Sie einen unordered_Container, andernfalls das traditionell bestellte Gegenstück.

Frage 1.2: Separater Schlüssel ?

• Wenn der Schlüssel vom Wert getrennt ist, verwenden Sie a map, andernfalls aset

Frage 1.3: Duplikate ?

• Wenn Sie Duplikate behalten möchten, verwenden Sie a multi, andernfalls nicht.

Beispiel:

Angenommen, mir sind mehrere Personen mit einer eindeutigen ID zugeordnet, und ich möchte die Personendaten so einfach wie möglich aus ihrer ID abrufen.

1. Ich möchte eine findFunktion, also einen assoziativen Container

   1.1. Die Bestellung ist mir egal, also ein unordered_Container

   1.2. Mein Schlüssel (ID) ist von dem Wert, dem er zugeordnet ist, getrennt, daher amap

   1.3. Die ID ist eindeutig, daher sollte sich kein Duplikat einschleichen.

Die endgültige Antwort lautet : std::unordered_map<ID, PersonData>.

Frage 2: Speicher stabil ?

• Wenn die Elemente im Speicher stabil sein sollen (dh sie sollten sich nicht bewegen, wenn der Container selbst geändert wird), verwenden Sie einige list
• Fahren Sie andernfalls mit Frage 3 fort.

Frage 2.1: Welche ?

• Begnügen Sie sich mit einem list; a forward_listist nur bei geringerem Speicherbedarf nützlich.

Frage 3: Dynamisch dimensioniert ?

• Wenn der Container eine bekannte Größe hat (zur Kompilierungszeit) und diese Größe im Verlauf des Programms nicht geändert wird und die Elemente standardmäßig konstruierbar sind oder Sie eine vollständige Initialisierungsliste (unter Verwendung der { ... }Syntax) bereitstellen können , verwenden Sie eine array. Es ersetzt das traditionelle C-Array, verfügt jedoch über praktische Funktionen.
• Fahren Sie andernfalls mit Frage 4 fort.

Frage 4: Double-Ended ?

• Wenn Sie Elemente sowohl von der Vorder- als auch von der Rückseite entfernen möchten, verwenden Sie a deque, andernfalls a vector.

Sie werden feststellen, dass Sie standardmäßig a wählen, es sei denn, Sie benötigen einen assoziativen Container vector. Es stellt sich heraus, dass dies auch die Empfehlung von Sutter und Stroustrup ist .

Ich mag Matthieus Antwort, aber ich werde das Flussdiagramm wie folgt wiederholen:

Wann sollte std :: vector NICHT verwendet werden?

Wenn Sie einen Container mit Material benötigen, verwenden Sie standardmäßig std::vector. Daher ist jeder andere Container nur durch die Bereitstellung einer Funktionsalternative zu gerechtfertigt std::vector.

Konstruktoren

std::vectorerfordert, dass sein Inhalt beweglich konstruierbar ist, da er in der Lage sein muss, die Elemente zu mischen. Dies ist keine schreckliche Belastung für den Inhalt (beachten Sie, dass dank usw. keine Standardkonstruktoren erforderlich sind emplace). Die meisten anderen Container benötigen jedoch keinen bestimmten Konstruktor (wiederum dank emplace). Wenn Sie also ein Objekt haben, in dem Sie einen Verschiebungskonstruktor absolut nicht implementieren können , müssen Sie etwas anderes auswählen.

A std::dequewäre der allgemeine Ersatz, der viele der Eigenschaften von aufweist std::vector, aber Sie können ihn nur an beiden Enden der Deque einfügen. Einsätze in der Mitte müssen verschoben werden. A std::liststellt keine Anforderungen an seinen Inhalt.

Benötigt Bools

std::vector<bool>ist nicht. Nun, es ist Standard. Dies ist jedoch nicht vectorim üblichen Sinne der Fall, da Operationen, die std::vectornormalerweise zulässig sind, verboten sind. Und es enthält mit Sicherheit kein bools .

Wenn Sie also echtes vectorVerhalten aus einem Container mit bools benötigen , werden Sie es nicht erhalten std::vector<bool>. Also musst du mit einem fällig werden std::deque<bool>.

Suchen

Wenn Sie Elemente in einem Container finden müssen und das Such-Tag nicht nur ein Index sein kann, müssen Sie möglicherweise std::vectorzugunsten von setund aufgeben map. Beachten Sie das Schlüsselwort " may "; Eine Sortierung std::vectorist manchmal eine vernünftige Alternative. Oder Boost.Container's flat_set/map, das eine sortierte implementiert std::vector.

Es gibt jetzt vier Variationen davon, jede mit ihren eigenen Bedürfnissen.

• Verwenden Sie a, mapwenn das Such-Tag nicht mit dem gesuchten Element übereinstimmt. Andernfalls verwenden Sie a set.
• Verwenden Sie, unorderedwenn Sie einen haben viele der Elemente in dem Behälter und Suchleistung absolut sein muss O(1), statt O(logn).
• Verwenden multiSie diese Option, wenn Sie mehrere Elemente benötigen, um dasselbe Such-Tag zu haben.

Bestellung

Wenn Sie einen Container mit Elementen benötigen, der immer nach einer bestimmten Vergleichsoperation sortiert werden soll, können Sie a verwenden set. Oder a, multi_setwenn Sie mehrere Elemente benötigen, um denselben Wert zu haben.

Oder Sie können eine sortierte verwenden std::vector, aber Sie müssen sie sortiert halten.

Stabilität

Wenn Iteratoren und Referenzen ungültig sind, ist dies manchmal ein Problem. Wenn Sie eine Liste von Elementen benötigen, sodass Sie an verschiedenen anderen Stellen Iteratoren / Zeiger auf diese Elemente haben, ist std::vectorder Ansatz zur Ungültigmachung möglicherweise nicht angemessen. Jeder Einfügevorgang kann je nach aktueller Größe und Kapazität zu einer Ungültigmachung führen.

std::listbietet eine feste Garantie: Ein Iterator und die zugehörigen Referenzen / Zeiger werden nur ungültig, wenn das Element selbst aus dem Container entfernt wird. std::forward_listist da, wenn das Gedächtnis ein ernstes Problem ist.

Wenn das eine zu starke Garantie ist, std::dequebietet sie eine schwächere, aber nützliche Garantie. Die Ungültigerklärung resultiert aus Einfügungen in der Mitte, aber Einfügungen am Kopf oder am Ende führen nur zur Ungültigmachung von Iteratoren , nicht zu Zeigern / Verweisen auf Elemente im Container.

Einfügeleistung

std::vector bietet nur billiges Einsetzen am Ende (und selbst dann wird es teuer, wenn Sie Kapazität blasen).

std::listist in Bezug auf die Leistung teuer (jedes neu eingefügte Element kostet eine Speicherzuweisung), aber es ist konsistent . Es bietet auch die gelegentlich unverzichtbare Möglichkeit, Gegenstände praktisch ohne Leistungskosten zu mischen und Gegenstände mit anderen std::listBehältern des gleichen Typs ohne Leistungsverlust zu handeln. Wenn Sie viel herum mischen müssen , verwenden Sie std::list.

std::dequeBietet eine zeitlich konstante Einführung / Entfernung an Kopf und Schwanz, aber die Einführung in der Mitte kann ziemlich teuer sein. Wenn Sie also Dinge sowohl von vorne als auch von hinten hinzufügen / entfernen müssen, ist dies std::dequemöglicherweise das, was Sie benötigen.

Es ist zu beachten, dass die Einfügeleistung dank der Verschiebungssemantik std::vectormöglicherweise nicht mehr so ​​schlecht ist wie früher. Einige Implementierungen implementierten eine Form des semantischen Verschiebens von Elementen (die sogenannte "Swaptimization"), aber jetzt, da das Verschieben Teil der Sprache ist, wird es vom Standard vorgeschrieben.

Keine dynamischen Zuordnungen

std::arrayist ein guter Container, wenn Sie möglichst wenige dynamische Zuordnungen wünschen. Es ist nur ein Wrapper um ein C-Array; Dies bedeutet, dass seine Größe zur Kompilierungszeit bekannt sein muss . Wenn Sie damit leben können, dann verwenden Sie std::array.

Davon abgesehen würde das Verwenden std::vectorund Verwenden reserveeiner Größe für einen Begrenzten genauso gut funktionieren std::vector. Auf diese Weise kann die tatsächliche Größe variieren und Sie erhalten nur eine Speicherzuordnung (es sei denn, Sie sprengen die Kapazität).

Hier ist die C ++ 11-Version des obigen Flussdiagramms. [ursprünglich ohne Zuschreibung an seinen ursprünglichen Autor, Mikael Persson, veröffentlicht ]

Hier ist ein kurzer Dreh, obwohl es wahrscheinlich Arbeit braucht

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Sie werden feststellen, dass diese unterscheidet sich wild von der C ++ 03 - Version, in erster Linie aufgrund der Tatsache , dass ich nicht wie verknüpften Knoten wirklich tun. Die Leistung der verknüpften Knotencontainer kann normalerweise von einem nicht verknüpften Container übertroffen werden, außer in einigen seltenen Situationen. Wenn Sie diese Situationen nicht kennen und Zugriff auf Boost haben, verwenden Sie keine verknüpften Knotencontainer. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). Diese Liste konzentriert sich hauptsächlich auf kleine und mittlere Container, da (A) das 99,99% des Codes sind und (B) eine große Anzahl von Elementen benutzerdefinierte Algorithmen benötigt, keine unterschiedlichen Container.