C++ benannte Anforderungen: AssociativeContainer

 

C++

Compiler-Unterstützung

Freestanding und gehostet

Sprache

Standardbibliothek

Header der Standardbibliothek

Benannte Anforderungen

Feature-Test-Makros (C++20)

Bibliothek für Sprachunterstützung

Konzepte-Bibliothek (C++20)

Diagnostik-Bibliothek

Speicherverwaltungsbibliothek

Metaprogrammierungsbibliothek (C++11)

Allgemeine Dienstprogramme-Bibliothek

Container-Bibliothek

Iterator-Bibliothek

Ranges-Bibliothek (C++20)

Algorithmen-Bibliothek

Bibliothek für Zeichenketten

Textverarbeitungsbibliothek

Numerik-Bibliothek

Datums- und Zeitbibliothek

Ein-/Ausgabe-Bibliothek

Dateisystembibliothek (C++17)

Unterstützung für nebenläufige Programmierung (C++11)

Ausführungssteuerungsbibliothek (C++26)

Technische Spezifikationen

Symbolverzeichnis

Externe Bibliotheken

 

C++ benannte Anforderungen

Basis DefaultConstructible MoveConstructible (C++11) CopyConstructible CopyAssignable MoveAssignable (C++11) Destructible Typeneigenschaften ScalarType PODType TriviallyCopyable (C++11) TrivialType (C++11) StandardLayoutType (C++11)   ImplicitLifetimeType Bibliothekweit BooleanTestable EqualityComparable LessThanComparable Swappable ValueSwappable (C++11) NullablePointer (C++11) Hash (C++11) Allocator FunctionObject Callable Predicate BinaryPredicate Compare

Container Container ReversibleContainer AllocatorAwareContainer SequenceContainer ContiguousContainer (C++17) AssociativeContainer UnorderedAssociativeContainer (C++11)   Container-Element DefaultInsertable (C++11) CopyInsertable (C++11) MoveInsertable (C++11) EmplaceConstructible (C++11) Erasable (C++11) Iterator LegacyIterator LegacyInputIterator LegacyOutputIterator LegacyForwardIterator LegacyBidirectionalIterator LegacyRandomAccessIterator LegacyContiguousIterator (C++17) ConstexprIterator (C++20) Stream-I/O FormattedInputFunction UnformattedInputFunction FormattedOutputFunction UnformattedOutputFunction Formatters BasicFormatter (C++20) Formatter (C++20)

Zufallszahlen SeedSequence (C++11) RandomNumberEngine (C++11) RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11) RandomNumberEngineAdaptor (C++11) Concurrency BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11) SharedLockable (C++14) SharedTimedLockable (C++14) Mutex (C++11) TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14) Bereiche (Ranges) RangeAdaptorObject (C++20) RangeAdaptorClosureObject (C++20) Mehrdimensionale Ansicht LayoutMapping (C++23) LayoutMappingPolicy (C++23) AccessorPolicy (C++23) Sonstiges CharTraits RegexTraits (C++11)   BitmaskType LiteralType (C++11) NumericType UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) Clock (C++11) TrivialClock (C++11)

 

Ein AssociativeContainer ist ein geordneter Container, der schnelles Nachschlagen von Objekten anhand von Schlüsseln ermöglicht.

Ein assoziativer Container unterstützt eindeutige Schlüssel, wenn er höchstens ein Element für jeden Schlüssel enthalten darf. Andernfalls unterstützt er gleiche Schlüssel.

Anforderungen

Legende
X	Eine assoziative Containerklasse
T	Der Elementtyp von X
A	Der Allokator-Typ von X: X::allocator_type, falls vorhanden, sonst std::allocator<X::value_type>
a	Ein Wert vom Typ X
a2	Ein Wert eines Typs Y, dessen Node-Handles mit X kompatibel sind
b	Ein Wert vom Typ X oder const X
u	Ein Name einer zu deklarierenden Variablen
a_uniq	Ein Wert vom Typ X, wenn X eindeutige Schlüssel unterstützt
a_eq	Ein Wert vom Typ X, wenn X gleiche Schlüssel unterstützt
a_tran	Ein Wert vom Typ X oder const X, wenn der Typ X::key_compare::is_transparent existiert
i, j	Die LegacyInputIteratorn, die auf Elemente verweisen, die implizit in X::value_type konvertierbar sind
[i, j)	Ein gültiger Bereich
rg (seit C++23)	Ein Wert eines Typs R, der container-compatible-range<value_type> modelliert
p	Ein gültiger Konstanten-Iterator zu a
q	Ein gültiger dereferenzierbarer Konstanten-Iterator zu a
r	Ein gültiger dereferenzierbarer Iterator zu a
q1, q2	Ein gültiger Bereich von Konstanten-Iteratoren in a
il	Ein Objekt vom Typ std::initializer_list<X::value_type>
t	Ein Wert vom Typ X::value_type
k	Ein Wert vom Typ X::key_type
c	Ein Wert vom Typ X::key_compare oder const X::key_compare
kl	Ein Wert, sodass a in Bezug auf c(x, kl) partitioniert ist, wobei x der Schlüsselwert von e ist und e in a liegt
ku	Ein Wert, sodass a in Bezug auf !c(ku, x) partitioniert ist, wobei x der Schlüsselwert von e ist und e in a liegt
ke	Ein Wert, sodass a in Bezug auf c(x, ke) und !c(ke, x) partitioniert ist, wobei c(x, ke) !c(ke, x) impliziert und wobei x der Schlüsselwert von e ist und e in a liegt
kx (seit C++23)	Ein Wert, sodass a in Bezug auf c(x, kx) und !c(kx, x) partitioniert ist, wobei c(x, kx) !c(kx, x) impliziert und wobei x der Schlüsselwert von e ist und e in a liegt, und kx nicht in X::iterator oder X::const_iterator konvertierbar ist
m	Ein Allokator eines Typs, der in A konvertierbar ist
nh	Ein nicht-konstantes Rvalue vom Typ X::node_type

Der Typ X erfüllt AssociativeContainer, wenn

• Der Typ X erfüllt Container(bis C++11)AllocatorAwareContainer(seit C++11),
• parametrisiert ist mit Key und einer Ordnungsrelation Compare, die eine strikt schwache Ordnung auf Elementen von Key induziert, und
  • Zusätzlich assoziieren std::map und std::multimap einen beliebigen zugeordneten Typ T mit dem Key.
  • Das Objekt vom Typ Compare wird als Vergleichsobjekt eines Containers vom Typ X bezeichnet.
• Die folgenden Ausdrücke müssen für alle assoziativen Container gültig sein und ihre angegebenen Effekte haben

Typen

Name	Typ	Anforderungen
key_type	Key
mapped_type	T (nur für std::map und std::multimap)
value_type	Key (nur für std::set und std::multiset) std::pair<const Key, T> (nur für std::map und std::multimap)	Erasable aus X
key_compare	Compare	CopyConstructible
value_compare	gleich key_compare (nur für std::set und std::multiset) eine Ordnungsrelation auf Paaren, induziert durch die erste Komponente (d.h. Key) (für std::map und std::multimap)	BinaryPredicate
node_type	Eine Spezialisierung der Node-Handle-Klassenschablone, sodass die öffentlichen verschachtelten Typen dieselben Typen wie die entsprechenden Typen in X sind.

Memberfunktionen und Operatoren

Ausdruck	Ergebnis	Vorbedingungen	Effekte	Gibt zurück	Komplexität
X(c)			Konstruiert einen leeren Container. Verwendet eine Kopie von c als Vergleichsobjekt		Konstante
X u = X(); X u;		key_compare erfüllt die DefaultConstructible-Anforderungen	Konstruiert einen leeren Container. Verwendet Compare() als Vergleichsobjekt		Konstante
X(i, j, c)		value_type ist EmplaceConstructible in X aus *i	Konstruiert einen leeren Container und fügt Elemente aus dem Bereich [i, j) ein; verwendet c als Vergleichsobjekt		N·log(N) im Allgemeinen, wobei N den Wert std::distance(i, j) hat; linear, wenn [i, j) in Bezug auf value_comp() sortiert ist
X(i, j)		key_compare erfüllt die DefaultConstructible-Anforderungen. value_type ist EmplaceConstructible in X aus *i	Konstruiert einen leeren Container und fügt Elemente aus dem Bereich [i, j) ein; verwendet Compare() als Vergleichsobjekt
X(from_range, rg, c) (seit C++23)		value_type ist EmplaceConstructible in X aus *ranges::begin(rg)	Konstruiert einen leeren Container und fügt jedes Element aus rg ein. Verwendet c als Vergleichsobjekt		N·log(N) im Allgemeinen, wobei N den Wert ranges::distance(rg) hat; linear, wenn rg in Bezug auf value_comp() sortiert ist
X(from_range, rg) (seit C++23)		key_compare erfüllt die DefaultConstructible-Anforderungen. value_type ist EmplaceConstructible in X aus *ranges::begin(rg)	Konstruiert einen leeren Container und fügt jedes Element aus rg ein. Verwendet Compare() als Vergleichsobjekt
X(il, c)			X(il.begin(), il.end(), c)
X(il)			X(il.begin(), il.end())
a = il	X&	value_type ist CopyInsertable in X und CopyAssignable	Weist den Bereich [il.begin(), il.end()) a zu. Alle vorhandenen Elemente von a werden entweder zugewiesen oder zerstört		N·log(N) im Allgemeinen, wobei N den Wert il.size() + a.size() hat; linear, wenn [il.begin(), il.end()) in Bezug auf value_comp() sortiert ist
b.key_comp()	X::key_compare			Das Vergleichsobjekt, aus dem b konstruiert wurde	Konstante
b.value_comp()	X::value_compare			Ein Objekt von value_compare, das aus dem Vergleichsobjekt konstruiert wurde	Konstante
a_uniq.emplace(args)	std::pair<   iterator,   bool>	value_type ist EmplaceConstructible in X aus args	Fügt ein value_type-Objekt t ein, das mit std::forward<Args>(args)... konstruiert wird, genau dann, wenn kein Element im Container mit einem Schlüssel vorhanden ist, der dem Schlüssel von t entspricht	Die bool-Komponente des zurückgegebenen Paares ist true genau dann, wenn die Einfügung stattfindet, und die Iterator-Komponente des Paares zeigt auf das Element mit einem Schlüssel, der dem Schlüssel von t entspricht	Logarithmisch
a_eq.emplace(args)	iterator	value_type ist EmplaceConstructible in X aus args	Fügt ein value_type-Objekt t ein, das mit std::forward<Args>(args)... konstruiert wird. Wenn ein Bereich mit Elementen, die t entsprechen, in a_eq vorhanden ist, wird t am Ende dieses Bereichs eingefügt	Ein Iterator, der auf das neu eingefügte Element zeigt	Logarithmisch
a.emplace_hint(p, args)	iterator		Äquivalent zu a.emplace(   std::forward<Args>(args)...), außer dass das Element so nah wie möglich an der Position unmittelbar vor p eingefügt wird	Ein Iterator, der auf das Element mit dem Schlüssel zeigt, der dem neu eingefügten Element entspricht	Logarithmisch im Allgemeinen, aber amortisiert konstant, wenn das Element direkt vor p eingefügt wird
a_uniq.insert(t)	std::pair<   iterator,   bool>	Wenn t ein nicht-konstantes Rvalue ist, ist value_type MoveInsertable in X; andernfalls ist value_type CopyInsertable in X	Fügt t ein, genau dann, wenn kein Element im Container mit einem Schlüssel vorhanden ist, der dem Schlüssel von t entspricht	Die bool-Komponente des zurückgegebenen Paares ist true genau dann, wenn die Einfügung stattfindet, und die iterator-Komponente des Paares zeigt auf das Element mit einem Schlüssel, der dem Schlüssel von t entspricht	Logarithmisch
a_eq.insert(t)	iterator	Wenn t ein nicht-konstantes Rvalue ist, ist value_type MoveInsertable in X; andernfalls ist value_type CopyInsertable in X	Fügt t ein und gibt den Iterator zurück, der auf das neu eingefügte Element zeigt. Wenn ein Bereich mit Elementen, die t entsprechen, in a_eq vorhanden ist, wird t am Ende dieses Bereichs eingefügt		Logarithmisch
a.insert(p, t)	iterator	Wenn t ein nicht-konstantes Rvalue ist, ist value_type MoveInsertable in X; andernfalls ist value_type CopyInsertable in X	Fügt t ein, genau dann, wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem Schlüssel vorhanden ist, der dem Schlüssel von t entspricht; fügt in Containern mit gleichen Schlüsseln immer t ein. t wird so nah wie möglich an die Position unmittelbar vor p eingefügt	Ein Iterator, der auf das Element mit dem Schlüssel zeigt, der dem Schlüssel von t entspricht	Logarithmisch im Allgemeinen, aber amortisiert konstant, wenn t direkt vor p eingefügt wird
a.insert(i, j)	void	value_type ist EmplaceConstructible in X aus *i. Weder i noch j sind Iteratoren in a	Fügt jedes Element aus dem Bereich [i, j) ein, genau dann, wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem Schlüssel vorhanden ist, der dem Schlüssel dieses Elements entspricht; fügt in Containern mit gleichen Schlüsseln immer dieses Element ein		N·log(a.size() + N), wobei N den Wert std::distance(i, j) hat
a.insert_range(rg) (seit C++23)	void	value_type ist EmplaceConstructible in X aus *ranges::begin(rg). rg und a überlappen sich nicht	Fügt jedes Element aus rg ein, genau dann, wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem Schlüssel vorhanden ist, der dem Schlüssel dieses Elements entspricht; fügt in Containern mit gleichen Schlüsseln immer dieses Element ein		N·log(a.size() + N), wobei N den Wert ranges::distance(rg) hat
a.insert(il)			a.insert(il.begin(), il.end())
a_uniq.insert(nh)	insert_return_type	nh ist leer oder a_uniq.get_allocator() == nh.get_allocator() ist true	Wenn nh leer ist, hat dies keine Auswirkung. Andernfalls wird das von nh besessene Element eingefügt, genau dann, wenn kein Element im Container mit einem Schlüssel vorhanden ist, der dem Schlüssel von nh.key() entspricht	Wenn nh leer ist, ist inserted false, position ist end() und node ist leer. Andernfalls, wenn die Einfügung stattgefunden hat, ist inserted true, position zeigt auf das eingefügte Element und node ist leer; wenn die Einfügung fehlgeschlagen ist, ist inserted false, node hat den vorherigen Wert von nh und position zeigt auf ein Element mit einem Schlüssel, der dem von nh.key() entspricht	Logarithmisch
a_eq.insert(nh)	iterator	nh ist leer oder a_eq.get_allocator() == nh.get_allocator() ist true	Wenn nh leer ist, hat dies keine Auswirkung und gibt a_eq.end() zurück. Andernfalls wird das von nh besessene Element eingefügt und ein Iterator zurückgegeben, der auf das neu eingefügte Element zeigt. Wenn ein Bereich mit Elementen mit Schlüsseln, die nh.key() entsprechen, in a_eq vorhanden ist, wird das Element am Ende dieses Bereichs eingefügt. Stellt sicher: nh ist leer		Logarithmisch
a.insert(p, nh)	iterator	nh ist leer oder a.get_allocator() == nh.get_allocator() ist true	Wenn nh leer ist, hat dies keine Auswirkung und gibt a.end() zurück. Andernfalls wird das von nh besessene Element eingefügt, genau dann, wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem Schlüssel vorhanden ist, der dem Schlüssel von nh.key() entspricht; in Containern mit gleichen Schlüsseln wird immer das von nh besessene Element eingefügt. Das Element wird so nah wie möglich an die Position unmittelbar vor p eingefügt. Stellt sicher: nh ist leer, wenn die Einfügung erfolgreich ist, unverändert, wenn die Einfügung fehlschlägt	Ein Iterator, der auf das Element mit dem Schlüssel zeigt, der dem von nh.key() entspricht	Logarithmisch im Allgemeinen, aber amortisiert konstant, wenn das Element direkt vor p eingefügt wird
a.extract(k)	node_type		Entfernt das erste Element im Container mit einem Schlüssel, der k entspricht	Ein node_type, der das Element besitzt, falls gefunden, andernfalls ein leerer node_type	log(a.size())
a_tran.extract(kx) (seit C++23)	node_type		Entfernt das erste Element im Container mit dem Schlüssel r, sodass !c(r, kx) && !c(kx, r) true ist	Ein node_type, der das Element besitzt, falls gefunden, andernfalls ein leerer node_type	log(a_tran.size())
a.extract(q)	node_type		Entfernt das Element, auf das q zeigt	Ein node_type, der dieses Element besitzt	Amortisiert konstant
a.merge(a2)	void	a.get_allocator() == a2.get_allocator()	Versucht, jedes Element in a2 zu extrahieren und es in a mithilfe des Vergleichsobjekts von a einzufügen. In Containern mit eindeutigen Schlüsseln, wenn in a ein Element mit einem Schlüssel vorhanden ist, der dem Schlüssel eines Elements aus a2 entspricht, wird dieses Element nicht aus a2 extrahiert. Stellt sicher: Zeiger und Referenzen auf die übertragenen Elemente von a2 verweisen auf dieselben Elemente, jedoch als Mitglieder von a. Iteratoren, die auf die übertragenen Elemente verweisen, verweisen weiterhin auf ihre Elemente, verhalten sich aber jetzt wie Iteratoren in a, nicht in a2. Wirft: Nichts, es sei denn, das Vergleichsobjekt wirft.		N·log(a.size() + N), wobei N den Wert a2.size() hat
a.erase(k)	size_type		Löscht alle Elemente im Container mit einem Schlüssel, der k entspricht	Die Anzahl der gelöschten Elemente	log(a.size()) + a.count(k)
a_tran.erase(kx) (seit C++23)	size_type		Löscht alle Elemente im Container mit dem Schlüssel r, sodass !c(r, kx) && !c(kx, r) true ist	Die Anzahl der gelöschten Elemente	log(a_tran.size()) + a_tran.count(kx)
a.erase(q)	iterator		Löscht das Element, auf das von q gezeigt wird	Ein Iterator, der auf das Element unmittelbar nach q vor dem Löschen des Elements zeigt. Wenn kein solches Element vorhanden ist, wird a.end() zurückgegeben	Amortisiert konstant
a.erase(r)	iterator		Löscht das Element, auf das von r gezeigt wird	Ein Iterator, der auf das Element unmittelbar nach r vor dem Löschen des Elements zeigt. Wenn kein solches Element vorhanden ist, wird a.end() zurückgegeben	Amortisiert konstant
a.erase(q1, q2)	iterator		Löscht alle Elemente im Bereich [q1, q2)	Ein Iterator, der auf das Element zeigt, auf das von q2 vor dem Löschen von Elementen gezeigt wurde. Wenn kein solches Element vorhanden ist, wird a.end() zurückgegeben	log(a.size()) + N, wobei N den Wert std::distance(q1, q2) hat
a.clear()			a.erase(a.begin(), a.end()). Stellt sicher: a.empty() ist true		Linear in a.size()
b.find(k)	iterator; const_iterator für konstantes b			Ein Iterator, der auf ein Element mit einem Schlüssel zeigt, der k entspricht, oder b.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
a_tran.find(ke)	iterator; const_iterator für konstantes a_tran			Ein Iterator, der auf ein Element mit dem Schlüssel r zeigt, so dass !c(r, ke) && !c(ke, r) ist true, oder a_tran.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
b.count(k)	size_type			Die Anzahl der Elemente mit einem Schlüssel, der k entspricht	log(b.size()) + b.count(k)
a_tran.count(ke)	size_type			Die Anzahl der Elemente mit dem Schlüssel r, so dass !c(r, ke) && !c(ke, r)	log(a_tran.size()) + a_tran.count(ke)
b.contains(k)	bool		return b.find(k) != b.end();
a_tran.contains(ke)	bool		return   a_tran.find(ke) !=   a_tran.end();
b.lower_bound(k)	iterator; const_iterator für konstantes b			Ein Iterator, der auf das erste Element mit einem Schlüssel zeigt, der nicht kleiner als k ist, oder b.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
a_tran.lower_bound(kl)	iterator; const_iterator für konstantes a_tran			Ein Iterator, der auf das erste Element mit dem Schlüssel r zeigt, so dass !c(r, kl), oder a_tran.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
b.upper_bound(k)	iterator; const_iterator für konstantes b			Ein Iterator, der auf das erste Element mit einem Schlüssel zeigt, der größer als k ist, oder b.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
a_tran.upper_bound(ku)	iterator; const_iterator für konstantes a_tran			Ein Iterator, der auf das erste Element mit dem Schlüssel r zeigt, so dass c(ku, r), oder a_tran.end(), wenn ein solches Element nicht gefunden wird	Logarithmisch
b.equal_range(k)	std::pair<   iterator,   iterator>; std::pair<   const_iterator,   const_iterator> für konstantes b		Äquivalent zu return   std::make_pair(     b.lower_bound(k),     b.upper_bound(k));		Logarithmisch
a_tran.equal_range(ke)	std::pair<   iterator,   iterator>; std::pair<   const_iterator,   const_iterator> für konstantes a_tran		Äquivalent zu return   std::make_pair(     a_tran.lower_bound(ke),     a_tran.upper_bound(ke));		Logarithmisch

Iteratoren

Iteratoren assoziativer Container erfüllen die Anforderungen eines LegacyBidirectionalIterator.

Für assoziative Container, bei denen value_type gleich key_type ist, sind sowohl iterator als auch const_iterator konstante Iteratoren. Es ist nicht spezifiziert, ob iterator und const_iterator gleich sind.

Iteratoren assoziativer Container durchlaufen die Container in aufsteigender Reihenfolge der Schlüssel, wobei "aufsteigend" durch den Vergleich definiert ist, der zum Erstellen der Container verwendet wurde. Das heißt, gegeben

• a, ein assoziativer Container
• i und j, dereferenzierbare Iteratoren zu a.

Wenn der Abstand von i zu j positiv ist, dann gilt a.value_comp()(*j, *i) = false. Zusätzlich gilt, wenn a ein assoziativer Container mit eindeutigen Schlüsseln ist, die stärkere Bedingung a.value_comp()(*i, *j) != false.

Standardbibliothek

Die folgenden Standardbibliothekscontainer erfüllen die AssociativeContainer-Anforderungen

setzt	Sammlung eindeutiger Schlüssel, sortiert nach Schlüsseln (Klassenvorlage)
multiset	Sammlung von Schlüsseln, sortiert nach Schlüsseln (Klassenvorlage)
map	Sammlung von Schlüssel-Wert-Paaren, sortiert nach Schlüsseln, Schlüssel sind eindeutig (Klassenvorlage)
multimap	Sammlung von Schlüssel-Wert-Paaren, sortiert nach Schlüsseln (Klassenvorlage)

Fehlerberichte

Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 354	C++98	lower_bound und upper_bound gaben nicht den End-Iterator zurück, wenn kein Element gefunden wurde	sie geben den End- Iterator in diesem Fall zurück
LWG 589	C++98	die Elemente, auf die i und j verweisen hatten den Typ X::value_type	die Elemente sind implizit konvertierbar zu X::value_type