C++ named requirements: UnorderedAssociativeContainer (since C++11)
Ungeordnete assoziative Container sind Container s , die schnelles Nachschlagen von Objekten basierend auf Schlüsseln ermöglichen. Die Komplexität im schlimmsten Fall ist linear, aber im Durchschnitt sind die meisten Operationen deutlich schneller.
Ungeordnete assoziative Container werden parametrisiert durch
Key
;
Hash
, ein
Hash
-Funktionsobjekt, das als Hash-Funktion auf
Key
agiert; und
Pred
, ein
BinaryPredicate
, das Äquivalenz zwischen
Key
s evaluiert.
std::unordered_map
und
std::unordered_multimap
haben außerdem einen zugeordneten Typ
T
, der mit dem
Key
assoziiert ist.
Wenn zwei
Key
s gemäß
Pred
gleich sind,
Hash
muss für beide Schlüssel den gleichen Wert zurückgeben.
|
Wenn sowohl
|
(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 dagegen mehrere Elemente mit demselben Schlüssel enthalten (die bei Iterationen stets benachbart sein 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 von Elementen in jedem Bucket unter einem bestimmten Wert zu halten.
Rehashing macht Iteratoren ungültig und kann dazu führen, dass Elemente in verschiedenen Buckets neu angeordnet werden, aber es macht Referenzen auf die Elemente nicht ungültig.
Ungeordnete assoziative Container erfüllen die Anforderungen von
AllocatorAwareContainer
.
Für
std::unordered_map
und
std::unordered_multimap
gelten die Anforderungen für
value_type
in
AllocatorAwareContainer
für
key_type
und
mapped_type
(nicht für
value_type
).
Inhaltsverzeichnis |
Anforderungen
Legende |
|
X
|
Eine ungeordnete assoziative Container-Klasse |
| a |
Ein Wert vom Typ
X
|
| a2 |
Ein Wert eines Typs mit
zu Typ
X
kompatiblen Nodes
|
| 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 auf 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, für den gilt:
wobei r1 und r2 Schlüssel von Elementen in a_tran sind. |
| kx (seit C++23) |
Ein Wert, für den gilt:
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 |
Mitgliedertypen
| 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.
Erasable
in
X
|
|
| std:: pair < const Key, T > |
std::unordered_map
und
std::unordered_multimap
nur.
Erasable
in
X
|
||
X::hasher
|
Hash
|
Hash | |
X::key_equal
|
Pred
|
CopyConstructible
;
BinaryPredicate
, das zwei Argumente vom Typ
Key
nimmt 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
(since C++17)
|
Eine Spezialisierung der node-handle Klassen-Template |
Die öffentlichen verschachtelten Typen sind identisch mit den entsprechenden Typen in
X
|
Memberfunktionen und Operatoren
| Ausdruck | Ergebnis | Vorbedingungen | Effekte | Rückgabewerte | Komplexität |
|---|---|---|---|---|---|
| X ( n, hf, eq ) | Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hf als Hash-Funktion und eq als Gleichheitsprädikat für Schlüssel | O ( n ) | |||
| X ( n, hf ) |
key_equal
ist
DefaultConstructible
|
Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hf als Hash-Funktion und key_equal ( ) als Schlüssel-Gleichheitsprädikat | O ( n ) | ||
| X ( n ) |
hasher
und
key_equal
sind
DefaultConstructible
|
Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hasher ( ) als Hash-Funktion und key_equal ( ) als Schlüsselgleichheitsprädikat | O ( n ) | ||
|
X a
=
X
(
)
;
X a ; |
hasher
und
key_equal
sind
DefaultConstructible
|
Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, verwendet hasher ( ) als Hash-Funktion und key_equal ( ) als Schlüssel-Gleichheitsprädikat | Konstante | ||
| X ( i, j, n, hf, eq ) |
value_type
ist
EmplaceConstructible
in
X
aus
*
i
|
Konstruiert einen leeren Container mit mindestens
n
Buckets, verwendet
hf
als Hash-Funktion und
eq
als Schlüsselgleichheitsprädikat, und fügt Elemente aus
[
i
,
j
)
ein
|
Durchschnittlicher Fall O(N) ( N ist std:: distance ( i, j ) ), schlechtester Fall O(N 2 ) | ||
| X ( i, j, n, hf ) |
key_equal
ist
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
von
*
i
|
Konstruiert einen leeren Container mit mindestens
n
Buckets, verwendet
hf
als Hash-Funktion und
key_equal
(
)
als Schlüsselgleichheitsprädikat und fügt Elemente aus
[
i
,
j
)
ein
|
Durchschnittlicher Fall O(N) ( N ist std:: distance ( i, j ) ), schlechtester Fall O(N 2 ) | ||
| X ( i, j, n ) |
hasher
und
key_equal
sind
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
von
*
i
|
Konstruiert einen leeren Container mit mindestens
n
Buckets, verwendet
hasher
(
)
als Hash-Funktion und
key_equal
(
)
als Schlüssel-Gleichheitsprädikat und fügt Elemente aus
[
i
,
j
)
ein
|
Durchschnittlicher Fall O(N) ( N ist std:: distance ( i, j ) ), schlechtester Fall O(N 2 ) | ||
| X ( i, j ) |
hasher
und
key_equal
sind
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
aus
*
i
|
Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, verwendet
hasher
(
)
als Hash-Funktion und
key_equal
(
)
als Schlüssel-Gleichheitsprädikat und fügt Elemente aus
[
i
,
j
)
ein
|
Durchschnittlicher Fall O(N) ( N ist std:: distance ( i, j ) ), schlechtester Fall O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n, hf, eq ) (seit C++23) |
value_type
ist
EmplaceConstructible
in
X
von
*
ranges::
begin
(
rg
)
|
Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hf als Hash-Funktion und eq als Schlüsselgleichheitsprädikat und fügt Elemente aus rg ein | Durchschnittlicher Fall O(N) ( N ist ranges:: distance ( rg ) ), schlechtester Fall O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n, hf ) (seit C++23) |
key_equal
ist
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
von
*
ranges::
begin
(
rg
)
|
Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hf als Hash-Funktion und key_equal ( ) als Schlüsselgleichheitsprädikat und fügt Elemente aus rg ein | Durchschnittlicher Fall O(N) ( N ist ranges:: distance ( rg ) ), schlechtester Fall O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n ) (seit C++23) |
hasher
und
key_equal
sind
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
von
*
ranges::
begin
(
rg
)
|
Konstruiert einen leeren Container mit mindestens n Buckets, verwendet hasher ( ) als Hash-Funktion und key_equal ( ) als Schlüssel-Gleichheitsprädikat und fügt Elemente aus rg ein | Durchschnittlicher Fall O(N) ( N ist ranges:: distance ( rg ) ), schlechtester Fall O(N 2 ) | ||
|
X
(
std::
from_range
,
rg ) (seit C++23) |
hasher
und
key_equal
sind
DefaultConstructible
.
value_type
ist
EmplaceConstructible
in
X
von
*
ranges::
begin
(
rg
)
|
Konstruiert einen leeren Container mit einer nicht spezifizierten Anzahl von Buckets, verwendet hasher ( ) als Hash-Funktion und key_equal ( ) als Schlüssel-Gleichheitsprädikat, und fügt Elemente aus rg ein | Durchschnittsfall 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 den maximalen Ladefaktor | Durchschnittlicher Fall linear in b. size ( ) , schlechtester Fall O(N 2 ) | |||
| a = b |
X&
|
Container ; kopiert die Hash-Funktion, das Prädikat und den maximalen Ladefaktor | Durchschnittlicher Fall linear in b. size ( ) , schlechtester Fall O(N 2 ) | ||
| a = il |
X&
|
value_type
ist
CopyInsertable
in
X
und
CopyAssignable
|
Weist den Bereich
[
il.
begin
(
)
,
il.
end
(
)
)
in
a
zu. Alle vorhandenen Elemente von
a
werden entweder zugewiesen oder zerstört
|
Durchschnittlicher Fall linear in il. size ( ) , schlechtester Fall O(N 2 ) | |
| b. hash_function ( ) |
hasher
|
b 's Hash-Funktion | Konstante | ||
| b. key_eq ( ) |
key_equal
|
b 's Schlüsselgleichheitsprädikat | 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 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 | Durchschnittlicher Fall O(1) , schlechtester Fall 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 | Durchschnittlicher Fall O(1) , schlechtester Fall 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 dem neu eingefügten Element entspricht. Der
const_iterator
p
ist ein Hinweis, der angibt, wo die Suche beginnen soll. Implementierungen dürfen den Hinweis ignorieren
|
Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) |
| a_uniq. insert ( t ) |
std::
pair
<
iterator, bool > |
Falls
t
ein nicht-konstanter R-Wert ist, muss
value_type
MoveInsertable
in
X
sein; andernfalls muss
value_type
CopyInsertable
in
X
sein.
|
Fügt t genau dann ein, wenn kein Element im Container mit einem Schlüssel vorhanden ist, der äquivalent zum Schlüssel von t ist. |
Die
bool
-Komponente des zurückgegebenen Paars gibt an, ob die Einfügung stattfindet, und die
iterator
-Komponente zeigt auf das Element mit einem Schlüssel, der äquivalent zum Schlüssel von
t
ist.
|
Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_uniq. size ( ) ) |
| a_eq. insert ( t ) |
iterator
|
Wenn
t
ein nicht-konstanter R-Wert ist, muss
value_type
MoveInsertable
in
X
sein; andernfalls muss
value_type
CopyInsertable
in
X
sein
|
Fügt t ein | Ein Iterator, der auf das neu eingefügte Element zeigt | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_eq. size ( ) ) |
| a. insert ( p, t ) |
iterator
|
Falls
t
ein nicht-konstanter R-Wert ist, muss
value_type
MoveInsertable
in
X
sein; andernfalls muss
value_type
CopyInsertable
in
X
sein
|
a. insert ( t ) . Der Iterator p ist ein Hinweis, der auf den Startpunkt der Suche zeigt. Implementierungen dürfen den Hinweis ignorieren | Ein Iterator, der auf das Element mit dem äquivalenten Schlüssel zu t zeigt | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) |
| a. insert ( i, j ) | void |
value_type
muss
EmplaceConstructible
in
X
aus
*
i
sein. Weder
i
noch
j
sind Iteratoren in
a
|
a.
insert
(
t
)
für jedes Element in
[
i
,
j
)
|
Durchschnittlicher Fall O(N) , wobei N ist std:: distance ( i, j ) , schlechtester Fall O ( N· ( a. size ( ) + 1 ) ) | |
|
a.
insert_range
(
rg
)
(seit C++23) |
void |
value_type
ist
EmplaceConstructible
in
X
von
*
ranges::
begin
(
rg
)
.
rg
und
a
überlappen sich nicht
|
a. insert ( t ) für jedes Element t in rg | Durchschnittsfall O(N) , wobei N ist ranges:: distance ( rg ) , 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
(
)
|
Wenn nh leer ist, hat dies keine Auswirkung. Andernfalls wird das von nh besessene Element genau dann eingefügt, wenn kein Element im Container mit einem Schlüssel vorhanden ist, der äquivalent zu nh. key ( ) ist. Sicherstellt: 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 äquivalent zu nh. key ( ) ist | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_uniq. size ( ) ) | |
|
a_eq.
insert
(
nh
)
(seit C++17) |
iterator
|
nh
ist leer oder
a_eq.
get_allocator
(
)
|
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 auf das neu eingefügte Element zurückgegeben. Stellt sicher: nh ist leer | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_eq. size ( ) ) | |
|
a.
insert
(
q, nh
)
(seit C++17) |
iterator
|
nh
ist leer oder
a.
get_allocator
(
)
|
Falls 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 in Containern mit eindeutigen Schlüsseln kein Element mit einem Schlüssel äquivalent zu nh. key ( ) vorhanden ist; in Containern mit äquivalenten Schlüsseln wird das von nh besessene Element immer eingefügt. Der Iterator q ist ein Hinweis, der angibt, wo die Suche beginnen soll. Implementierungen dürfen den Hinweis ignorieren. Stellt sicher: nh ist leer bei erfolgreichem Einfügen, unverändert bei fehlgeschlagenem Einfügen | Ein Iterator, der auf das Element mit einem Schlüssel äquivalent zu nh. key ( ) zeigt | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) |
|
a.
extract
(
k
)
(seit C++17) |
node_type
|
Entfernt ein Element im Container mit Schlüssel äquivalent zu k |
Ein
node_type
, der das Element besitzt, falls gefunden, andernfalls ein leerer
node_type
|
Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) | |
|
a_tran.
extract
(
kx
)
(seit C++23) |
node_type
|
Entfernt ein Element im Container mit einem Schlüssel, der äquivalent zu kx ist |
Ein
node_type
, der das Element besitzt, falls gefunden, andernfalls ein leerer
node_type
|
Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_tran. size ( ) ) | |
|
a.
extract
(
q
)
(seit C++17) |
node_type
|
Entfernt das Element, auf das q zeigt |
Ein
node_type
, der dieses Element besitzt
|
Durchschnittlicher Fall O(1) , schlechtester Fall 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 unter Verwendung der Hash-Funktion und des Schlüsselgleichheitsprädikats von a einzufügen. In Containern mit eindeutigen Schlüsseln wird ein Element nicht aus a2 extrahiert, falls bereits ein Element mit äquivalentem Schlüssel in a vorhanden ist. Gewährleistet: 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 für a werden ungültig, während Iteratoren für in a2 verbleibende Elemente gültig bleiben. | Durchschnittlicher Fall O(N) , wobei N für a2. size ( ) steht, schlechtester Fall O ( N· ( a. size ( ) + 1 ) ) | |
| a. erase ( k ) |
size_type
|
Löscht alle Elemente mit Schlüssel äquivalent zu k | Die Anzahl der gelöschten Elemente | Durchschnittlicher Fall O ( a. count ( k ) ), schlechtester Fall O ( a. size ( ) ) | |
|
a_tran.
erase
(
kx
)
(seit C++23) |
size_type
|
Löscht alle Elemente mit Schlüssel äquivalent zu kx | Die Anzahl der gelöschten Elemente | Durchschnittlicher Fall O ( a_tran. count ( kx ) ), schlechtester Fall O ( a_tran. size ( ) ) | |
| a. erase ( q ) |
iterator
|
Löscht das Element, auf das q zeigt | Der Iterator unmittelbar nach q vor dem Löschvorgang | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) | |
|
a.
erase
(
r
)
(seit C++17) |
iterator
|
Löscht das Element, auf das r zeigt | Der Iterator unmittelbar nach r vor dem Löschen | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a. size ( ) ) | |
| a. erase ( q1, q2 ) |
iterator
|
Löscht alle Elemente im Bereich
[
q1
,
q2
)
|
Der Iterator unmittelbar nach den gelöschten Elementen vor der Löschung | Durchschnittlich 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 konstante
b
|
Ein Iterator, der auf ein Element mit Schlüssel äquivalent zu k zeigt, oder b. end ( ) falls kein solches Element existiert | Durchschnittlicher Fall O(1) , schlechtester Fall O ( b. size ( ) ) | ||
|
a_tran.
find
(
ke
)
(seit C++17) ? |
iterator
;
const_iterator
für konstante
a_tran
|
Ein Iterator, der auf ein Element mit einem Schlüssel zeigt, der äquivalent zu ke ist, oder a_tran. end ( ) , falls kein solches Element existiert | Durchschnittlicher Fall O(1) , schlechtester Fall O ( a_tran. size ( ) ) | ||
| b. count ( k ) |
size_type
|
Die Anzahl der Elemente mit Schlüssel äquivalent zu k | Durchschnittlicher Fall O ( b. count ( k ) ), schlechtester Fall O ( b. size ( ) ) | ||
|
a_tran.
count
(
ke
)
(seit C++17) ? |
size_type
|
Die Anzahl der Elemente mit Schlüssel äquivalent zu ke | Durchschnittlicher Fall O ( a_tran. count ( ke ) ), schlechtester Fall 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
<
|
Ein Bereich, der alle Elemente mit Schlüsseln äquivalent zu
k
enthält. Gibt zurück
std::
make_pair
(
|
Durchschnittlicher Fall O ( b. count ( k ) ), schlechtester Fall O ( b. size ( ) ) | ||
|
a_tran.
equal_range
(
ke
)
(seit C++20) ? |
std::
pair
<
iterator, iterator > ;
std::
pair
<
|
Ein Bereich, der alle Elemente mit Schlüsseln äquivalent zu
ke
enthält. Gibt zurück
std::
make_pair
(
|
Durchschnittlicher Fall O ( a_tran. count ( ke ) ), schlechtester Fall O ( a_tran. size ( ) ) | ||
| b. bucket_count ( ) |
size_type
|
Die Anzahl der Buckets, die b enthält | Konstant | ||
| 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 äquivalent zu
k
gefunden würden, falls solche Elemente existieren. Der Rückgabewert liegt im Bereich
[
0
,
b.
bucket_count
(
)
)
|
Konstante Zeit | |
| a_tran. bucket ( ke ) |
size_type
|
a_tran.
bucket_count ( ) > 0 |
Der Index des Buckets, in dem Elemente mit Schlüsseln äquivalent zu
ke
gefunden würden, falls solche Elemente existieren. Der Rückgabewert muss im Bereich
[
0
,
a_tran.
bucket_count
(
)
)
liegen.
|
Konstante | |
| b. bucket_size ( n ) |
size_type
|
n
liegt in
[
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 konstante
b
|
n
liegt in
[
0
,
b.
bucket_count
(
)
)
|
Ein Iterator, der auf das erste Element im Bucket verweist. Wenn der Bucket leer ist, dann b. begin ( n ) == b. end ( n ) | Konstante | |
| b. end ( n ) |
local_iterator
;
const_local_iterator
für konstante
b
|
n
liegt in
[
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 in
[
0
,
b.
bucket_count
(
)
)
|
Ein Iterator, der auf das erste Element im Bucket verweist. Wenn der Bucket leer ist, dann gilt b. cbegin ( n ) == b. cend ( n ) | Konstante Zeit | |
| b. cend ( n ) |
const_local_iterator
|
n
liegt in
[
0
,
b.
bucket_count
(
)
)
|
Ein Iterator, der den Endwert für den Bucket darstellt | Konstant | |
| 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 nach Bedarf, 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
(
)
>=
|
Durchschnittliche Laufzeit linear in a. size ( ) , schlimmster Fall O(N 2 ) | ||
| a. reserve ( n ) |
a.
rehash
(
std::
ceil
(
n / a. max_load_factor ( ) ) ) |
|
Dieser Abschnitt ist unvollständig
Grund: Anforderungen bezüglich Memberfunktionen. |
Standardbibliothek
Die folgenden Standardbibliothek-Container erfüllen die UnorderedAssociativeContainer -Anforderungen:
|
(C++11)
|
Sammlung eindeutiger Schlüssel, gehasht nach Schlüsseln
(Klassen-Template) |
|
(C++11)
|
Sammlung von Schlüsseln, gehasht nach Schlüsseln
(Klassen-Template) |
|
(C++11)
|
Sammlung von Schlüssel-Wert-Paaren, gehasht nach Schlüsseln, Schlüssel sind eindeutig
(Klassen-Template) |
|
(C++11)
|
Sammlung von Schlüssel-Wert-Paaren, gehasht nach Schlüsseln
(Klassen-Template) |
Fehlerberichte
Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.
| DR | Angewendet auf | Verhalten wie veröffentlicht | Korrektes Verhalten |
|---|---|---|---|
| LWG 2156 | C++11 |
der Ladefaktor nach Rehashing konnte nur
strikt niedriger als der maximale Ladefaktor sein |
Gleichheit erlaubt |