Containers library

Die Containers-Bibliothek ist eine generische Sammlung von Klassentemplates und Algorithmen, die es Programmierern ermöglicht, gängige Datenstrukturen wie Warteschlangen, Listen und Stapel einfach zu implementieren. Es gibt zwei (until C++11) drei (since C++11) Klassen von Containern:

• Sequenzcontainer,
• Assoziative Container,

von denen jede entwickelt wurde, um einen unterschiedlichen Satz von Operationen zu unterstützen.

Der Container verwaltet den Speicherplatz, der für seine Elemente alloziert ist, und stellt Member-Funktionen bereit, um darauf zuzugreifen, entweder direkt oder durch Iteratoren (Objekte mit Eigenschaften ähnlich Zeigern).

Die meisten Container haben mindestens mehrere Memberfunktionen gemeinsam und teilen Funktionalitäten. Welcher Container für eine bestimmte Anwendung am besten geeignet ist, hängt nicht nur von der angebotenen Funktionalität ab, sondern auch von seiner Effizienz für verschiedene Arbeitslasten.

Sequenzcontainer

Sequenzcontainer implementieren Datenstrukturen, die sequenziell abgerufen werden können.

Assoziative Container

Assoziative Container implementieren sortierte Datenstrukturen, die schnell durchsucht werden können ( O(log n) Komplexität).

Ungeordnete assoziative Container (since C++11)

Ungeordnete assoziative Container implementieren ungeordnete (gehashte) Datenstrukturen, die schnell durchsucht werden können ( O(1) durchschnittlich, O(n) Worst-Case-Komplexität).

Container-Adapter

Container-Adaptoren bieten eine andere Schnittstelle für sequentielle Container.

Views (seit C++20)

Views bieten flexible Möglichkeiten zur Interaktion mit ein- oder mehrdimensionalen Ansichten über ein nicht-besitzendes Array von Elementen.

Iterator-Invalidierung

Schreibgeschützte Methoden machen Iteratoren oder Referenzen niemals ungültig . Methoden, die den Inhalt eines Containers verändern, können Iteratoren und/oder Referenzen ungültig machen, wie in dieser Tabelle zusammengefasst.

Hier bezieht sich insertion auf jede Methode, die ein oder mehrere Elemente zum Container hinzufügt, und erasure auf jede Methode, die ein oder mehrere Elemente aus dem Container entfernt.

• Beispiele für Einfügemethoden sind std::set::insert , std::map::emplace , std::vector::push_back , und std::deque::push_front .

• Beispiele für Löschmethoden sind std::set::erase , std::vector::pop_back , std::deque::pop_front , und std::map::clear .
  • clear macht alle Iteratoren und Referenzen ungültig. Da es alle Elemente löscht, erfüllt es technisch gesehen die oben genannten Regeln.

Sofern nicht anders angegeben (entweder explizit oder durch Definition einer Funktion in Bezug auf andere Funktionen), führt das Übergeben eines Containers als Argument an eine Bibliotheksfunktion niemals zur Ungültigkeit von Iteratoren oder zur Änderung der Werte von Objekten innerhalb dieses Containers.

Der Past-the-End-Iterator verdient besondere Erwähnung. Im Allgemeinen wird dieser Iterator ungültig, als ob es sich um einen normalen Iterator auf ein nicht gelöschtes Element handeln würde. Daher wird std::set::end niemals ungültig , std::unordered_set::end wird nur bei Rehash ungültig (since C++11) , std::vector::end wird immer ungültig (da es sich immer nach den modifizierten Elementen befindet), und so weiter.

Es gibt eine Ausnahme: Ein Löschvorgang, der das letzte Element eines std::deque macht den Past-the-End-Iterator ungültig, obwohl es sich nicht um ein gelöschtes Element des Containers handelt (oder überhaupt um ein Element). In Kombination mit den allgemeinen Regeln für std::deque Iteratoren ist das Endergebnis, dass die einzige modifizierende Operation, die nicht std::deque::end ungültig macht, ein Löschvorgang ist, der das erste Element löscht, aber nicht das letzte.

Funktionstabelle

Hinweis: std::basic_string wird vom Standard nicht als Container behandelt, verhält sich jedoch aufgrund seiner Ähnlichkeit weitgehend wie einer. Es wird hier der Übersichtlichkeit halber als 'Pseudo-Container' aufgeführt.

Member-Funktionstabelle