C++ benannte Anforderungen: UnorderedAssociativeContainer (seit C++11)

Ungeordnete assoziative Container sind Container, die ein schnelles Nachschlagen von Objekten anhand von Schlüsseln ermöglichen. Die Komplexität im Worst-Case ist linear, aber im Durchschnitt für die meisten Operationen deutlich schneller.

Ungeordnete assoziative Container werden durch Key; Hash, ein Hash-Funktionsobjekt, das als Hash-Funktion für Key fungiert; und Pred, ein BinaryPredicate, das die Gleichheit zwischen Keys evaluiert, parametrisiert. std::unordered_map und std::unordered_multimap haben außerdem einen zu Key assoziierten Werttyp T.

Wenn zwei Keys gemäß Pred gleich sind, muss Hash für beide Schlüssel denselben Wert zurückgeben.

Wenn sowohl Hash::is_transparent als auch Pred::is_transparent existieren und jeweils einen Typ benennen, akzeptieren die Member-Funktionen find, contains, count, equal_range und bucket Argumente von anderen Typen als Key und erwarten, dass Hash mit Werten dieser Typen aufrufbar ist und dass Pred eine transparente Vergleichsfunktion ist, wie z. B. std::equal_to<>.

(seit C++20)

std::unordered_map und std::unordered_set können höchstens ein Element mit einem bestimmten Schlüssel enthalten. std::unordered_multiset und std::unordered_multimap können stattdessen mehrere Elemente mit demselben Schlüssel enthalten (die bei Iterationen immer nebeneinander liegen müssen).

Für std::unordered_set und std::unordered_multiset ist der Werttyp identisch mit dem Schlüsseltyp und sowohl iterator als auch const_iterator sind konstante Iteratoren. Für std::unordered_map und std::unordered_multimap ist der Werttyp std::pair<const Key, T>.

Elemente in einem ungeordneten assoziativen Container sind in Buckets organisiert. Schlüssel mit demselben Hash landen im selben Bucket. Die Anzahl der Buckets wird erhöht, wenn die Größe des Containers zunimmt, um die durchschnittliche Anzahl der Elemente in jedem Bucket unter einem bestimmten Wert zu halten.

Rehashing macht Iteratoren ungültig und kann dazu führen, dass die Elemente in verschiedenen Buckets neu angeordnet werden, ungültig macht aber keine Referenzen auf die Elemente.

Ungeordnete assoziative Container erfüllen die Anforderungen an AllocatorAwareContainer. Für std::unordered_map und std::unordered_multimap gelten die Anforderungen an value_type in AllocatorAwareContainer für key_type und mapped_type (nicht für value_type).

[bearbeiten] Anforderungen

Legende
`X`	Eine Klasse für ungeordnete assoziative Container
a	Ein Wert vom Typ `X`
a2	Ein Wert eines Typs mit Knoten, die mit Typ `X` kompatibel sind
b	Ein Wert vom Typ `X` oder `const X`
a_uniq	Ein Wert vom Typ `X`, wenn `X` eindeutige Schlüssel unterstützt
a_eq	Ein Wert vom Typ `X`, wenn `X` äquivalente Schlüssel unterstützt
a_tran	Ein Wert vom Typ `X` oder const X, wenn die qualifizierten Bezeichner `X::key_equal::is_transparent` und `X::hasher::is_transparent` beide gültig sind und Typen bezeichnen
i, j	Input-Iteratoren, die auf `value_type` verweisen
`[`i`,` j`)`	Ein gültiger Bereich
rg (seit C++23)	Ein Wert eines Typs `R`, der `container-compatible-range<value_type>` modelliert
p, q2	Gültige konstante Iteratoren zu a
q, q1	Gültige dereferenzierbare konstante Iteratoren zu a
r	Ein gültiger dereferenzierbarer Iterator zu a
`[`q1`,` q2`)`	Ein gültiger Bereich in a
il	Ein Wert vom Typ std::initializer_list<value_type>
t	Ein Wert vom Typ `X::value_type`
k	Ein Wert vom Typ `key_type`
hf	Ein Wert vom Typ `hasher` oder const hasher
eq	Ein Wert vom Typ `key_equal` oder const key_equal
ke	Ein Wert, so dass eq(r1, ke) == eq(ke, r1), hf(r1) == hf(ke) wenn eq(r1, ke) true ist, und wenn zwei der Ausdrücke eq(r1, ke), eq(r2, ke), und eq(r1, r2) true sind, dann sind alle drei true, wobei r1 und r2 Schlüssel von Elementen in a_tran sind
kx (seit C++23)	Ein Wert, so dass eq(r1, kx) == eq(kx, r1), hf(r1) == hf(kx) wenn eq(r1, kx) true ist, wenn zwei der Ausdrücke eq(r1, kx), eq(r2, kx), und eq(r1, r2) true sind, dann sind alle drei true, und kx ist nicht in `iterator` oder `const_iterator` konvertierbar, wobei r1 und r2 Schlüssel von Elementen in a_tran sind
n	Ein Wert vom Typ `size_type`
z	Ein Wert vom Typ float
nh (seit C++17)	Ein Rvalue vom Typ X::node_type

[bearbeiten] Member-Typen

Name	Typ	Anforderungen	Anmerkungen
`X::key_type`	`Key`
`X::mapped_type`	`T`	std::unordered_map und std::unordered_multimap nur
`X::value_type`	`Key`	std::unordered_set und std::unordered_multiset nur. Löschbar in `X`
`X::value_type`	std::pair<const Key, T>	std::unordered_map und std::unordered_multimap nur. Löschbar in `X`
`X::hasher`	`Hash`	Hash
`X::key_equal`	`Pred`	Kopierkonstruierbar; BinaryPredicate, das zwei Argumente vom Typ `Key` annimmt und eine Äquivalenzrelation ausdrückt
`X::local_iterator`	LegacyIterator	Kategorie und Typen sind identisch mit `X::iterator`	Kann verwendet werden, um durch einen einzelnen Bucket zu iterieren, aber nicht über Buckets hinweg
`X::const_local_iterator`	LegacyIterator	Kategorie und Typen sind identisch mit `X::const_iterator`
`X::node_type` (seit C++17)	Eine Spezialisierung der node-handle-Klassentemplate	Die öffentlichen verschachtelten Typen sind identisch mit den entsprechenden Typen in `X`

[bearbeiten] Member-Funktionen und Operatoren

Ausdruck	Ergebnis	Vorbedingungen	Effekte	Gibt zurück	Komplexität
X(n, hf, eq)			Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und eq als Schlüsselgleichheitspredikat verwendet werden		$O$ (n)
X(n, hf)		`key_equal` ist Standardkonstruierbar	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden		$O$ (n)
X(n)		`hasher` und `key_equal` sind Standardkonstruierbar	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden		$O$ (n)
X a = X(); X a;		`hasher` und `key_equal` sind Standardkonstruierbar	Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden		Konstante
X(i, j, n, hf, eq)		`value_type` ist EmplaceConstructible in `X` aus *i	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und eq als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus `[`i`,` j`)` ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist std::distance(i, j)), Worst-Case $O(N 2)$
X(i, j, n, hf)		`key_equal` ist Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *i	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus `[`i`,` j`)` ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist std::distance(i, j)), Worst-Case $O(N 2)$
X(i, j, n)		`hasher` und `key_equal` sind Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *i	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus `[`i`,` j`)` ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist std::distance(i, j)), Worst-Case $O(N 2)$
X(i, j)		`hasher` und `key_equal` sind Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *i	Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus `[`i`,` j`)` ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist std::distance(i, j)), Worst-Case $O(N 2)$
X(std::from_range, rg, n, hf, eq) (seit C++23)		`value_type` ist EmplaceConstructible in `X` aus *ranges::begin(rg)	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und eq als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus rg ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist ranges::distance(rg)), Worst-Case $O(N 2)$
X(std::from_range, rg, n, hf) (seit C++23)		`key_equal` ist Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *ranges::begin(rg)	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hf als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus rg ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist ranges::distance(rg)), Worst-Case $O(N 2)$
X(std::from_range, rg, n) (seit C++23)		`hasher` und `key_equal` sind Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *ranges::begin(rg)	Konstruiert einen leeren Container mit mindestens n Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus rg ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist ranges::distance(rg)), Worst-Case $O(N 2)$
X(std::from_range, rg) (seit C++23)		`hasher` und `key_equal` sind Standardkonstruierbar. `value_type` ist EmplaceConstructible in `X` aus *ranges::begin(rg)	Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, wobei hasher() als Hash-Funktion und key_equal() als Schlüsselgleichheitspredikat verwendet werden, und fügt Elemente aus rg ein		Durchschnittliche Komplexität $O(N)$ ( $N$ ist ranges::distance(rg)), Worst-Case $O(N 2)$
X(il)			X(il.begin(), il.end())
X(il, n)			X(il.begin(), il.end(), n)
X(il, n, hf)			X(il.begin(), il.end(), n, hf)
X(il, n, hf, eq)			X(il.begin(), il.end(), n, hf, eq)
X(b)			Container; Kopiert die Hash-Funktion, das Prädikat und die maximale Auslastungsdichte		Durchschnittliche Komplexität linear in b.size(), Worst-Case $O(N 2)$
a = b	`X&`		Container; kopiert die Hash-Funktion, das Prädikat und die maximale Auslastungsdichte		Durchschnittliche Komplexität linear in b.size(), Worst-Case $O(N 2)$
a = il	`X&`	`value_type` ist Kopierbar einfügbar in `X` und kopierzuweisbar	Weist den Bereich `[`il.begin()`,` il.end()`)` dem Container a zu. Alle vorhandenen Elemente von a werden entweder zugewiesen oder zerstört		Durchschnittliche Komplexität linear in il.size(), Worst-Case $O(N 2)$
b.hash_function()	`hasher`			Hash-Funktion von b	Konstante
b.key_eq()	`key_equal`			Schlüsselgleichheitspredikat von b	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 wurde, genau dann, wenn kein Element im Container vorhanden ist, dessen Schlüssel mit dem Schlüssel von t äquivalent ist	Die Komponente bool des zurückgegebenen Paares ist true genau dann, wenn die Einfügung stattfindet, und die Iterator-Komponente des Paares zeigt auf das Element mit dem Schlüssel, der mit dem Schlüssel von t äquivalent ist	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_uniq.size())
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 wurde	Ein Iterator, der auf das neu eingefügte Element zeigt	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_eq.size())
a.emplace_hint(p, args)	`iterator`	`value_type` ist EmplaceConstructible in `X` aus args	a.emplace( std::forward<Args>(args)...	Ein Iterator, der auf das Element mit dem Schlüssel zeigt, der mit dem neu eingefügten Element äquivalent ist. Der `const_iterator` p ist ein Hinweis, wo die Suche beginnen soll. Implementierungen dürfen den Hinweis ignorieren	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a_uniq.insert(t)	std::pair< iterator, bool>	Wenn t ein nicht-konstanter Rvalue ist, ist `value_type` MoveInsertable in `X`; andernfalls ist `value_type` Kopierbar einfügbar in `X`	Fügt t ein genau dann, wenn kein Element im Container vorhanden ist, dessen Schlüssel mit dem Schlüssel von t äquivalent ist	Die Komponente bool des zurückgegebenen Paares gibt an, ob die Einfügung stattfindet, und die `iterator`-Komponente zeigt auf das Element mit dem Schlüssel, der mit dem Schlüssel von t äquivalent ist	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_uniq.size())
a_eq.insert(t)	`iterator`	Wenn t ein nicht-konstanter Rvalue ist, ist `value_type` MoveInsertable in `X`; andernfalls ist `value_type` Kopierbar einfügbar in `X`	Fügt t ein	Ein Iterator, der auf das neu eingefügte Element zeigt	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_eq.size())
a.insert(p, t)	`iterator`	Wenn t ein nicht-konstanter Rvalue ist, ist `value_type` MoveInsertable in `X`; andernfalls ist `value_type` Kopierbar einfügbar in `X`	a.insert(t). Der Iterator p ist ein Hinweis darauf, wo die Suche beginnen soll. Implementierungen dürfen den Hinweis ignorieren	Ein Iterator, der auf das Element mit dem Schlüssel zeigt, der mit dem von t äquivalent ist	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a.insert(i, j)	void	`value_type` ist EmplaceConstructible in `X` aus *i. Weder i noch j sind Iteratoren in a	a.insert(t) für jedes Element in `[`i`,` j`)`		Durchschnittsfall $O(N)$ , wobei $N$ std::distance(i, j) ist, Worst Case $O$ (N·(a.size() + 1))
a.insert_range(rg) (seit C++23)	void	`value_type` ist EmplaceConstructible in `X` aus *ranges::begin(rg). rg und a überlappen sich nicht	a.insert(t) für jedes Element t in rg		Durchschnittsfall $O(N)$ , wobei $N$ ranges::distance(rg) ist, Worst Case $O$ (N·(a.size() + 1))
a.insert(il)			a.insert(il.begin(), il.end())
a_uniq.insert(nh) (seit C++17)	`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, wenn und nur wenn kein Element im Container mit einem Schlüssel vorhanden ist, der dem von nh.key() entspricht. Stellt sicher: 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		Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_uniq.size())
a_eq.insert(nh) (seit C++17)	`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. Stellt sicher: nh ist leer		Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a_eq.size())
a.insert(q, nh) (seit C++17)	`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, wenn und nur wenn kein Element mit einem Schlüssel, der dem von nh.key() entspricht, in Containern mit eindeutigen Schlüsseln vorhanden ist; in Containern mit äquivalenten Schlüsseln wird das von nh besessene Element immer eingefügt. Der Iterator q ist ein Hinweis darauf, wo die Suche beginnen soll. Implementierungen dürfen den Hinweis ignorieren. 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 einem Schlüssel zeigt, der dem von nh.key() entspricht	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a.extract(k) (seit C++17)	`node_type`		Entfernt ein Element im Container mit einem Schlüssel, der dem von k entspricht	Ein `node_type`, der das Element besitzt, falls es gefunden wurde, andernfalls ein leerer `node_type`	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a_tran.extract(kx) (seit C++23)	`node_type`		Entfernt ein Element im Container mit einem Schlüssel, der dem von kx entspricht	Ein `node_type`, der das Element besitzt, falls es gefunden wurde, andernfalls ein leerer `node_type`	Durchschnittsfall $O(1)$ , Worst Case $O$ (a_tran.size())
a.extract(q) (seit C++17)	`node_type`		Entfernt das von q dargestellte Element	Ein `node_type`, der dieses Element besitzt	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a.merge(a2) (seit C++17)	void	a.get_allocator() == a2.get_allocator()	Versucht, jedes Element in a2 zu extrahieren und in a einzufügen, wobei die Hash-Funktion und das Schlüsselgleichheitsprädikat von a verwendet werden. In Containern mit eindeutigen Schlüsseln wird, wenn ein Element in a mit einem Schlüssel vorhanden ist, der dem Schlüssel eines Elements aus a2 entspricht, 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, sowie alle Iteratoren, die auf a verweisen, werden ungültig, aber Iteratoren zu verbleibenden Elementen in a2 bleiben gültig		Durchschnittsfall $O(N)$ , wobei $N$ a2.size() ist, Worst Case $O$ (N·(a.size() + 1))
a.erase(k)	`size_type`		Löscht alle Elemente mit einem Schlüssel, der dem von k entspricht	Die Anzahl der gelöschten Elemente	Durchschnittsfall $O$ (a.count(k)), Worst Case $O$ (a.size())
a_tran.erase(kx) (seit C++23)	`size_type`		Löscht alle Elemente mit einem Schlüssel, der dem von kx entspricht	Die Anzahl der gelöschten Elemente	Durchschnittsfall $O$ (a_tran.count(kx)), Worst Case $O$ (a_tran.size())
a.erase(q)	`iterator`		Löscht das von q dargestellte Element	Der Iterator, der unmittelbar auf q folgt, vor dem Löschen	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a.erase(r) (seit C++17)	`iterator`		Löscht das von r dargestellte Element	Der Iterator, der unmittelbar auf r folgt, vor dem Löschen	Durchschnittliche Komplexität $O(1)$ , Worst-Case $O$ (a.size())
a.erase(q1, q2)	`iterator`		Löscht alle Elemente im Bereich `[`q1`,` q2`)`	Der Iterator, der unmittelbar auf die gelöschten Elemente folgt, vor dem Löschen	Durchschnittsfall linear in std::distance(q1, q2), Worst Case $O$ (a.size())
a.clear()	void		Löscht alle Elemente im Container. 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 dem von k entspricht, oder b.end(), wenn kein solches Element existiert	Durchschnittsfall $O(1)$ , Worst Case $O$ (b.size())
a_tran.find(ke) (seit C++17)?	`iterator`; `const_iterator` für konstantes a_tran			Ein Iterator, der auf ein Element mit einem Schlüssel zeigt, der dem von ke entspricht, oder a_tran.end(), wenn kein solches Element existiert	Durchschnittsfall $O(1)$ , Worst Case $O$ (a_tran.size())
b.count(k)	`size_type`			Die Anzahl der Elemente mit einem Schlüssel, der dem von k entspricht	Durchschnittsfall $O$ (b.count(k)), Worst Case $O$ (b.size())
a_tran.count(ke) (seit C++17)?	`size_type`			Die Anzahl der Elemente mit einem Schlüssel, der dem von ke entspricht	Durchschnittsfall $O$ (a_tran.count(ke)), Worst Case $O$ (a_tran.size())
b.contains(k) (seit C++20)?			b.find(k) != b.end()
a_tran.contains(ke) (seit C++20)?			a_tran.find(ke) != a_tran.end()
b.equal_range(k)	std::pair< iterator, iterator>; std::pair< const_iterator, const_iterator> für konstantes b			Ein Bereich, der alle Elemente mit Schlüsseln enthält, die dem von k entsprechen. Gibt std::make_pair( b.end(), b.end()) zurück, wenn keine solchen Elemente existieren	Durchschnittsfall $O$ (b.count(k)), Worst Case $O$ (b.size())
a_tran.equal_range(ke) (seit C++20)?	std::pair< iterator, iterator>; std::pair< const_iterator, const_iterator> für konstantes a_tran			Ein Bereich, der alle Elemente mit Schlüsseln enthält, die dem von ke entsprechen. Gibt std::make_pair( a_tran.end(), a_tran.end()) zurück, wenn keine solchen Elemente existieren	Durchschnittsfall $O$ (a_tran.count(ke)), Worst Case $O$ (a_tran.size())
b.bucket_count()	`size_type`			Die Anzahl der Buckets, die b enthält	Konstante
b.max_bucket_count()	`size_type`			Eine Obergrenze für die Anzahl der Buckets, die b jemals enthalten kann	Konstante
b.bucket(k)	`size_type`	b.bucket_count() > 0		Der Index des Buckets, in dem Elemente mit Schlüsseln, die dem von k entsprechen, gefunden würden, falls ein solches Element existiert. Der Rückgabewert liegt im Bereich `[`0`,` b.bucket_count()`)`	Konstante
a_tran.bucket(ke)	`size_type`	a_tran. bucket_count() > 0		Der Index des Buckets, in dem Elemente mit Schlüsseln, die dem von ke entsprechen, gefunden würden, falls ein solches Element existiert. Der Rückgabewert muss im Bereich `[`0`,` a_tran.bucket_count()`)` liegen	Konstante
b.bucket_size(n)	`size_type`	n liegt im Bereich `[`0`,` b.bucket_count()`)`		Die Anzahl der Elemente im n-ten Bucket	$O$ (b.bucket_size(n))
b.begin(n)	`local_iterator`; `const_local_iterator` für konstantes b	n liegt im Bereich `[`0`,` b.bucket_count()`)`		Ein Iterator, der auf das erste Element im Bucket verweist. Wenn der Bucket leer ist, dann ist b.begin(n) == b.end(n)	Konstante
b.end(n)	`local_iterator`; `const_local_iterator` für konstantes b	n liegt im Bereich `[`0`,` b.bucket_count()`)`		Ein Iterator, der den Past-the-End-Wert für den Bucket darstellt	Konstante
b.cbegin(n)	`const_local_iterator`	n liegt im Bereich `[`0`,` b.bucket_count()`)`		Ein Iterator, der auf das erste Element im Bucket verweist. Wenn der Bucket leer ist, dann ist b.cbegin(n) == b.cend(n)	Konstante
b.cend(n)	`const_local_iterator`	n liegt im Bereich `[`0`,` b.bucket_count()`)`		Ein Iterator, der den Past-the-End-Wert für den Bucket darstellt	Konstante
b.load_factor()	float			Die durchschnittliche Anzahl von Elementen pro Bucket	Konstante
b.max_load_factor()	float			Eine positive Zahl, die der Container versucht, den Ladefaktor kleiner oder gleich zu halten. Der Container erhöht automatisch die Anzahl der Buckets, wenn nötig, um den Ladefaktor unter dieser Zahl zu halten	Konstante
a.max_load_factor(z)	void	z ist positiv. Kann den maximalen Ladefaktor des Containers ändern, wobei z als Hinweis verwendet wird			Konstante
a.rehash(n)	void		Stellt sicher a.bucket_count() >= a.size() / a.max_load_factor() und a.bucket_count() >= n		Durchschnittsfall linear in a.size(), Worst Case $O(N 2)$
a.reserve(n)			a.rehash(std::ceil( n / a.max_load_factor()))

[bearbeiten] Standardbibliothek

Die folgenden Standardbibliothekscontainer erfüllen die Anforderungen an UnorderedAssociativeContainer

unordered_set (C++11)	Sammlung eindeutiger Schlüssel, gehasht nach Schlüsseln (Klassenvorlage) [edit]
unordered_multiset (C++11)	Sammlung von Schlüsseln, gehasht nach Schlüsseln (Klassenvorlage) [edit]
unordered_map (C++11)	Sammlung von Schlüssel-Wert-Paaren, gehasht nach Schlüsseln, Schlüssel sind eindeutig (Klassenvorlage) [edit]
unordered_multimap (C++11)	Sammlung von Schlüssel-Wert-Paaren, gehasht nach Schlüsseln (Klassenvorlage) [edit]

[bearbeiten] Defect Reports

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 2156	C++11	der Ladefaktor nach dem Rehash könnte nur strikt niedriger sein als der maximale Ladefaktor	darf gleich sein

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

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen