Namespaces
Variants

C++ named requirements: AssociativeContainer

From cppreference.net
C++
C++ named requirements

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

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

Inhaltsverzeichnis

Anforderungen

Legende
X Eine assoziative Container-Klasse
T Der Elementtyp von X
A Der Allokatortyp von X : X::allocator_type falls vorhanden, andernfalls std:: allocator < X :: value_type >
a Ein Wert vom Typ X
a2 Ein Wert eines Typs Y , dessen Node Handles kompatibel mit X sind
b Ein Wert vom Typ X oder const X
u Ein Name einer zu deklarierenden Variable
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 der Typ X::key_compare::is_transparent existiert
i , j Die LegacyInputIterator s , 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 das Konzept container-compatible-range <value_type> modelliert
p Ein gültiger konstanter Iterator zu a
q Ein gültiger dereferenzierbarer konstanter Iterator auf a
r Ein gültiger dereferenzierbarer Iterator auf a
q1 , q2 Ein gültiger Bereich von const-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 bezüglich c ( x, kl ) partitioniert ist, wobei x der Schlüsselwert von e ist und e in a
ku Ein Wert, bei dem a bezüglich ! c ( ku, x ) partitioniert ist, wobei x der Schlüsselwert von e ist und e in a
ke Ein Wert, sodass a bezüglich c ( x, ke ) und ! c ( ke, x ) partitioniert wird, wobei c ( x, ke ) ! c ( ke, x ) impliziert und x der Schlüsselwert von e ist und e in a enthalten ist
kx
(seit C++23) 		Ein Wert, sodass:
  • a bezüglich c ( x, kx ) und ! c ( kx, x ) partitioniert ist, wobei c ( x, kx ) ! c ( kx, x ) impliziert und x der Schlüsselwert von e ist und e in a enthalten ist, 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-konstanter Rvalue vom Typ X::node_type

Der Typ X erfüllt die Anforderungen eines AssociativeContainer wenn

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

Typen

Name Typ Anforderungen
key_type Key
mapped_type T (nur für std::map und std::multimap )
value_type Erasable von X
key_compare Compare CopyConstructible
value_compare BinaryPredicate
node_type Eine Spezialisierung der Node-Handle-Klassenvorlage , sodass die öffentlichen verschachtelten Typen identisch mit den entsprechenden Typen in X sind.

Memberfunktionen und Operatoren

**Erklärung:** - HTML-Tags und Attribute wurden unverändert beibehalten - C++ Code innerhalb der ` ` Tags wurde nicht übersetzt - Die Formatierung und Struktur der Tabelle bleibt erhalten - Nur der umgebende Text (der in diesem Fall nicht vorhanden ist) wäre übersetzt worden **Anmerkung:** Der gesamte Code innerhalb der ` ` Tags wurde nicht übersetzt, da es sich um C++-Code handelt. Die HTML-Struktur und Attribute bleiben ebenfalls unverändert.
Ausdruck Ergebnis Vorbedingungen Effekte Rückgabewerte 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 von * 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, falls [ i , j ) bezüglich 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 von * 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, falls rg sortiert ist bezüglich value_comp ( )
X ( from_range, rg )
(seit C++23) 		key_compare erfüllt die DefaultConstructible Anforderungen. value_type ist EmplaceConstructible in X von * 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 ( ) ) in 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, falls [ il. begin ( ) , il. end ( ) ) bezüglich 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 vom Typ value_compare , erstellt aus dem Vergleichsobjekt Konstant
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 dem 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 wurde. Falls ein Bereich mit Elementen äquivalent zu t in a_eq existiert, 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 Entspricht

a. emplace (
std:: forward < Args > ( args ) ... ) , außer dass das Element so nah wie möglich an der Position direkt 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 > 		Falls t ein nicht-konstanter Rvalue 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 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 äquivalent zum Schlüssel von t ist. Logarithmisch
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 und gibt den Iterator zurück, der auf das neu eingefügte Element zeigt. Wenn ein Bereich mit Elementen, die äquivalent zu t sind, in a_eq existiert, wird t am Ende dieses Bereichs eingefügt Logarithmisch
a. insert ( p, t ) iterator Falls t ein nicht-konstantes Rvalue ist, muss value_type MoveInsertable in X sein; andernfalls muss value_type CopyInsertable in X sein. Fügt t nur dann ein, wenn kein Element mit einem zum Schlüssel von t äquivalenten Schlüssel in Containern mit eindeutigen Schlüsseln existiert; fügt t in Containern mit äquivalenten Schlüsseln immer ein. t wird so nah wie möglich an der Position direkt vor p eingefügt. Ein Iterator, der auf das Element mit einem zum Schlüssel von t äquivalenten Schlüssel zeigt. Logarithmisch im Allgemeinen, aber amortisiert konstant, falls t direkt vor p eingefügt wird.
a. insert ( i, j ) void value_type ist EmplaceConstructible in X von * i . Weder i noch j sind Iteratoren in a Fügt jedes Element aus dem Bereich [ i , j ) ein, wenn und nur wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem äquivalenten Schlüssel existiert; in Containern mit äquivalenten Schlüsseln wird das Element immer eingefügt 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 von * ranges:: begin ( rg ) . rg und a überlappen sich nicht Fügt jedes Element aus rg ein, wenn und nur wenn in Containern mit eindeutigen Schlüsseln kein Element mit einem äquivalenten Schlüssel existiert; fügt dieses Element in Containern mit äquivalenten Schlüsseln immer 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 gehaltene Element genau dann eingefügt, wenn kein Element im Container mit einem Schlüssel existiert, der äquivalent zu nh. key ( ) ist. 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. 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 gehaltene Element eingefügt und ein Iterator auf das neu eingefügte Element zurückgegeben. Falls ein Bereich mit Elementen, deren Schlüssel äquivalent zu nh. key ( ) sind, in a_eq existiert, 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 gehaltene Element eingefügt, wenn und nur wenn kein Element mit einem Schlüssel äquivalent zu nh. key ( ) in Containern mit eindeutigen Schlüsseln vorhanden ist; in Containern mit äquivalenten Schlüsseln wird das von nh gehaltene Element immer eingefügt. Das Element wird so nah wie möglich an der Position direkt vor p eingefügt. 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 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 Schlüssel äquivalent zu k 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 Schlüssel r für das ! c ( r, kx ) && ! c ( kx, r ) den Wert true hat 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 unter Verwendung des Vergleichsobjekts von a in a einzufügen. In Containern mit eindeutigen Schlüsseln wird ein Element nicht aus a2 extrahiert, falls bereits ein Element in a mit einem äquivalenten Schlüssel existiert. Sicherstellt: 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, bleiben gültig, verhalten sich jedoch nun als Iteratoren in a , nicht in a2 . Wirft: Nichts, es sei denn, das Vergleichsobjekt wirft eine Ausnahme. N·log ( a. size ( ) + N ) , wobei N den Wert a2. size ( ) hat.
a. erase ( k ) size_type Löscht alle Elemente im Container mit dem Schlüssel äquivalent zu k 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 für die ! c ( r, kx ) && ! c ( kx, r ) wahr ist true Die Anzahl der gelöschten Elemente log ( a_tran. size ( ) )
+ a_tran. count ( kx )
a. erase ( q ) iterator Löscht das Element, auf das q zeigt Ein Iterator, der auf das Element unmittelbar nach q vor dem Löschen des Elements zeigt. Falls kein solches Element existiert, wird a. end ( ) zurückgegeben Amortisiert konstant
a. erase ( r ) iterator Löscht das Element, auf das r zeigt Ein Iterator, der auf das Element unmittelbar nach r vor dem Löschen des Elements zeigt. Falls kein solches Element existiert, 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 q2 vor dem Löschen gezeigt hat. Falls kein solches Element existiert, 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 ( ) ) . Sichert zu: 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 dem Schlüssel verweist, der äquivalent zu k ist, oder b. end ( ) , falls ein solches Element nicht gefunden wurde Logarithmisch
a_tran. find ( ke ) iterator ; const_iterator für konstante a_tran Ein Iterator, der auf ein Element mit Schlüssel r zeigt, sodass

! c ( r, ke ) &&
! c ( ke, r ) ist true , oder a_tran. end ( ) falls kein solches Element gefunden wurde

Logarithmisch
b. count ( k ) size_type Die Anzahl der Elemente mit Schlüssel äquivalent zu k log ( b. size ( ) )
+ b. count ( k )
a_tran. count ( ke ) size_type Die Anzahl der Elemente mit Schlüssel r für die gilt:

! 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 konstante b Ein Iterator, der auf das erste Element mit einem Schlüssel nicht kleiner als k zeigt, oder b. end ( ) , falls ein solches Element nicht gefunden wurde Logarithmisch
a_tran. lower_bound ( kl ) iterator ; const_iterator für konstante a_tran Ein Iterator, der auf das erste Element mit dem Schlüssel r zeigt, für das ! c ( r, kl ) gilt, oder a_tran. end ( ) , falls ein solches Element nicht gefunden wurde Logarithmisch
b. upper_bound ( k ) iterator ; const_iterator für konstante b Ein Iterator, der auf das erste Element mit einem Schlüssel größer als k zeigt, oder b. end ( ) falls ein solches Element nicht gefunden wird Logarithmisch
a_tran. upper_bound ( ku ) iterator ; const_iterator für konstante a_tran Ein Iterator, der auf das erste Element mit dem Schlüssel r zeigt, so dass c ( ku, r ) , oder a_tran. end ( ) falls kein solches Element gefunden wurde Logarithmisch
b. equal_range ( k ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > für konstante b

Entspricht:

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 konstante a_tran

Entspricht:

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 denselben Typ haben.

Iteratoren assoziativer Container durchlaufen die Container in nicht-absteigender Reihenfolge der Schlüssel, wobei nicht-absteigend durch den Vergleich definiert wird, der zur Konstruktion der Container verwendet wurde. Das heißt, gegeben

  • a , ein assoziativer Container
  • i und j , dereferenzierbare Iteratoren für 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 .

Dieser Abschnitt ist unvollständig
Grund: Anforderungen vervollständigen.

Standardbibliothek

Die folgenden Standardbibliothek-Container erfüllen die AssociativeContainer -Anforderungen:

Sammlung eindeutiger Schlüssel, nach Schlüsseln sortiert
(Klassentemplate)
Sammlung von Schlüsseln, nach Schlüsseln sortiert
(Klassentemplate)
Sammlung von Schlüssel-Wert-Paaren, nach Schlüsseln sortiert, Schlüssel sind eindeutig
(Klassentemplate)
Sammlung von Schlüssel-Wert-Paaren, nach Schlüsseln sortiert
(Klassentemplate)

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 354 C++98 lower_bound und upper_bound gaben nicht
den End-Iterator zurück, wenn kein Element gefunden wurde 		sie geben in diesem Fall den End-
Iterator 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