Wie kann ich effizient wählen Sie eine Standard-Bibliothek container in C++11?

Ich wie Matthieu Antwort, aber ich werde noch einmal der Ablaufplan:

, Wenn NICHT für die Verwendung der std::vector

Standardmäßig, wenn Sie einen container von Sachen, verwenden Sie std::vector. So, alle anderen container ist nur dann gerechtfertigt, indem Sie einige Funktionen, die alternative zu std::vector.

Konstruktoren

std::vector verlangt, dass seine Inhalte bewegen-baubar, da es braucht, um in der Lage, schieben Sie die Gegenstände um. Dies ist nicht eine schreckliche Bürde, die auf den Inhalt (beachten Sie, dass die default-Konstruktoren sind nicht erforderlich, Dank emplace und so weiter). Jedoch, die meisten anderen Behälter benötigen keine besonderen Konstruktor (wieder, Dank emplace). Also, wenn Sie ein Objekt haben, wo Sie absolut nicht Umsetzung einer move-Konstruktor, dann müssen Sie wählen Sie etwas anderes.

Einen std::deque wäre der Allgemeine Ersatz -, dass viele der Eigenschaften des std::vector, aber Sie können nur stecken Sie an beiden enden der deque. Fügt in der Mitte erfordern verschieben. Ein std::list Orten keine Anforderung auf Ihren Inhalt.

Muss Bools

std::vector<bool> ist... nicht. Gut, es ist standard. Aber es ist nicht eine vector im üblichen Sinne, wie Operationen, die std::vector normal erlaubt sind, sind verboten. Und das wird es ganz sicher nicht enthalten bools.

Deshalb, wenn Sie brauchen echte vector Verhalten aus einem container von bools, du bist nicht gehen, um es von std::vector<bool>. So müssen Sie dies mit einem std::deque<bool>.

Suchen

Wenn Sie brauchen, um die Elemente in einem container, und die Suche tag kann man nicht einfach einen index, dann müssen Sie möglicherweise aufgeben std::vector zu Gunsten von set und map. Beachten Sie das wichtige Wort "kann"; a sortiert std::vector ist manchmal eine sinnvolle alternative. Oder "Boost".Container flat_set/map, die Implementierung einer sortierten std::vector.

Gibt es nun vier Varianten dieser, jede mit Ihren eigenen Bedürfnissen.

• Verwenden map wenn der such-tag ist nicht das gleiche wie das Element, das Sie suchen für sich selbst. Sonst ein set.
• Verwenden unordered wenn Sie eine viel der Elemente im container und Suche Leistung absolut sein muss O(1) eher als O(logn).
• Verwenden multi wenn Sie mehrere Punkte haben, um die gleiche Suche-tag.

Bestellung

Wenn Sie einen container der die Elemente immer sortiert werden basierend auf einer bestimmten Vergleich Betrieb, können Sie ein set. Oder ein multi_set wenn Sie mehrere Elemente den gleichen Wert haben.

Oder Sie können eine sortierte std::vector, aber Sie haben, um es zu halten sortiert.

Stabilität

Wenn Iteratoren und Referenzen werden ungültig ist manchmal ein Anliegen. Wenn Sie eine Liste der Elemente, so, dass Sie über Iteratoren/Zeiger auf diese Objekte in verschiedene andere Plätze, dann std::vector's Ansatz zur Ungültigkeitserklärung möglicherweise nicht geeignet. Jede Einfüge-operation kann die Ursache Abwertung, abhängig von der aktuellen Größe und Kapazität.

std::list bietet eine Feste Garantie: ein iterator und Ihre zugehörigen Referenzen/Zeiger sind nur dann ungültig, wenn das Objekt selbst aus dem container entfernt wird. std::forward_list ist es, wenn der Speicher ist ein ernstes Problem.

Wenn das zu starke Garantie std::deque bietet eine schwächere, aber nützliche Garantie. Aufhebungs-Ergebnisse von Insertionen in der Mitte, aber die Einfügungen in den Kopf oder Schwanz Ursachen nur die Ungültigkeitserklärung von Iteratoren, keine Zeiger/Referenzen auf die Elemente im container.

Einlegen Leistung

std::vector nur bietet Billig einfügen am Ende (und selbst dann wird es teuer, wenn Sie Schlag Kapazität).

std::list ist teuer in Bezug auf Leistung (jedes neu eingefügte Element kostet ein memory allocation), aber es ist konsistente. Es bietet auch die gelegentlich unverzichtbare Fähigkeit, shuffle-Elemente, um für praktisch keine Leistung Kosten, sowie das handeln mit items mit anderen std::list Behältern des gleichen Typs ohne performance-Verlust. Wenn Sie brauchen, um zu schieben das Zeug herum viel, verwenden Sie std::list.

std::deque bietet eine Konstante-Zeit einfügen/entfernen am Kopf und Schwanz, aber die Einfügung in der Mitte ziemlich teuer werden kann. Also, wenn Sie brauchen, um hinzuzufügen/entfernen Sie Dinge aus der Vorder-sowie der Rückseite, std::deque könnte das sein, was Sie brauchen.

Es sollte angemerkt werden, dass, Dank move-Semantik std::vector insertion kann die Leistung nicht so schlecht, wie es verwendet werden. Einige Implementierungen implementiert eine form des move-Semantik-basierten Element kopieren (die so genannte "swaptimization"), aber jetzt, dass der Umzug ist Teil der Sprache, es ist Auftrag des standard.

Keine Dynamischen Zuweisungen

std::array ist ein feiner Behälter, wenn Sie wollen, dass die wenigsten möglich dynamische Zuordnungen. Es ist nur ein wrapper um ein C-array; dies bedeutet, dass Ihre Größe bekannt sein muss, an compile-Zeit. Wenn Sie damit Leben kann, dann verwenden Sie std::array.

Dass gesagt wird, mit std::vector und reserveing eine Größe würde genauso gut funktionieren, für ein eingegrenztes std::vector. Auf diese Weise, die tatsächliche Größe kann variieren, und Sie bekommen nur eine Speicherreservierung (es sei denn, Sie sprengen die Kapazität).

InformationsquelleAutor Nicol Bolas

Hier ist eine schnelle Drehung, obwohl es muss wahrscheinlich arbeiten

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

Können Sie feststellen, dass dies unterscheidet sich Wild aus C++03-version, vor allem aufgrund der Tatsache, dass ich weiß wirklich nicht, wie verknüpften Knoten. Die verlinkten Knoten-Container können in der Regel schlagen in der Leistung durch eine nicht verlinkte container, außer in ein paar seltenen Fällen. Wenn Sie nicht wissen, was diese Situationen sind, und haben Zugang zu steigern, nicht verknüpfte Knoten-Container. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). Diese Liste konzentriert sich hauptsächlich auf kleine und mittlere sided-Container, weil (A) das ist zu 99,99% von dem, was wir im code, und (B) Große Anzahl von Elementen benötigen, benutzerdefinierte algorithmen, nicht in verschiedene Behälter.

InformationsquelleAutor Mooing Duck