Namespaces
Variants

C++ named requirements: AssociativeContainer

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

Un AssociativeContainer est un Container ordonné qui permet une recherche rapide d'objets basée sur des clés.

Un conteneur associatif prend en charge des clés uniques s'il peut contenir au plus un élément pour chaque clé. Sinon, il prend en charge des clés équivalentes .

Table des matières

Exigences

Légende
X Une classe de conteneur associatif
T Le type d'élément de X
A Le type d'allocateur de X : X::allocator_type s'il existe, sinon std:: allocator < X :: value_type >
a Une valeur de type X
a2 Une valeur d'un type Y dont les node handles sont compatibles avec X
b Une valeur de type X ou const X
u Un nom de variable en cours de déclaration
a_uniq Une valeur de type X lorsque X prend en charge les clés uniques
a_eq Une valeur de type X lorsque X prend en charge les clés équivalentes
a_tran Une valeur de type X ou const X lorsque le type X::key_compare::is_transparent existe
i , j Les LegacyInputIterator s faisant référence à des éléments implicitement convertibles en X::value_type
[ i , j ) Une plage valide
rg
(depuis C++23) 		Une valeur d'un type R qui modélise container-compatible-range <value_type>
p Un itérateur constant valide vers a
q Un itérateur constant déréférençable valide vers a
r Un itérateur déréférençable valide vers a
q1 , q2 Une plage valide d'itérateurs constants dans a
il Un objet de type std:: initializer_list < X :: value_type >
t Une valeur de type X::value_type
k Une valeur de type X::key_type
c Une valeur de type X::key_compare ou const X :: key_compare
kl Une valeur telle que a soit partitionné par rapport à c ( x, kl ) , avec x la valeur de clé de e et e dans a
ku Une valeur telle que a soit partitionné par rapport à ! c ( ku, x ) , avec x la valeur clé de e et e dans a
ke Une valeur telle que a soit partitionnée par rapport à c ( x, ke ) et ! c ( ke, x ) , avec c ( x, ke ) impliquant ! c ( ke, x ) et avec x la valeur de clé de e et e dans a
kx
(depuis C++23) 		Une valeur telle que :
  • a est partitionnée par rapport à c ( x, kx ) et ! c ( kx, x ) , avec c ( x, kx ) impliquant ! c ( kx, x ) et avec x la valeur clé de e et e dans a , et
  • kx n'est pas convertible en X::iterator ou X::const_iterator
m Un allocateur d'un type convertible en A
nh Une rvalue non constante de type X::node_type

Le type X satisfait AssociativeContainer si

  • Le type X satisfait Container (jusqu'en C++11) AllocatorAwareContainer (depuis C++11) ,
  • Est paramétré sur Key et une relation d'ordre Compare qui induit un ordre strict faible sur les éléments de Key , et
    • De plus, std::map et std::multimap associent un type mappé arbitraire T avec la Key .
    • L'objet de type Compare est appelé l' objet de comparaison d'un conteneur de type X .
  • Les expressions suivantes doivent être valides et avoir leurs effets spécifiés pour tous les conteneurs associatifs :

Types

Nom Type Exigences
key_type Key
mapped_type T (uniquement pour std::map et std::multimap )
value_type Effaçable depuis X
key_compare Compare CopiableConstructible
value_compare PrédicatBinaire
node_type Une spécialisation du modèle de classe node-handle , telle que les types imbriqués publics soient les mêmes types que les types correspondants dans X .

Fonctions membres et opérateurs

**Note:** Aucune traduction n'a été effectuée car : - Le texte contenu dans les balises ` ` est considéré comme du code C++ - Les termes "il", "begin" et "end" sont des termes spécifiques au C++ (initializer_list et ses méthodes) - Toutes les balises HTML et leurs attributs ont été préservés - La mise en forme originale a été maintenue **Note:** Le code C++ dans les balises ` ` n'a pas été traduit conformément aux instructions, car il s'agit de code de programmation qui doit rester en anglais. Seul le texte en dehors de ces balises aurait été traduit, mais dans cet extrait, il n'y a pas de texte français à traduire en dehors du code C++.
Expression Résultat Préconditions Effets Retourne Complexité
X ( c ) Construit un conteneur vide. Utilise une copie de c comme objet de comparaison Constant
X u = X ( ) ;
X u ; 		key_compare satisfait les exigences DefaultConstructible Construit un conteneur vide. Utilise Compare ( ) comme objet de comparaison Constant
X ( i, j, c ) value_type est EmplaceConstructible dans X à partir de * i Construit un conteneur vide et insère les éléments de l'intervalle [ i , j ) dans celui-ci ; utilise c comme objet de comparaison N·log ( N ) en général, où N a la valeur std:: distance ( i, j ) ; linéaire si [ i , j ) est trié par rapport à value_comp ( )
X ( i, j ) key_compare satisfait les exigences DefaultConstructible . value_type est EmplaceConstructible dans X à partir de * i Construit un conteneur vide et insère les éléments de l'intervalle [ i , j ) dans celui-ci ; utilise Compare ( ) comme objet de comparaison
X ( from_range, rg, c )
(depuis C++23) 		value_type est EmplaceConstructible dans X à partir de * ranges:: begin ( rg ) Construit un conteneur vide et insère chaque élément de rg dans celui-ci. Utilise c comme objet de comparaison N·log ( N ) en général, où N a la valeur ranges:: distance ( rg ) ; linéaire si rg est trié par rapport à value_comp ( )
X ( from_range, rg )
(depuis C++23) 		key_compare satisfait aux exigences DefaultConstructible . value_type est EmplaceConstructible dans X à partir de * ranges:: begin ( rg ) Construit un conteneur vide et insère chaque élément de rg dans celui-ci. Utilise Compare ( ) comme objet de comparaison
X ( il, c ) X ( il. begin ( ) , il. end ( ) , c )
X ( il ) X ( il. begin ( ) , il. end ( ) )
a = il X & value_type est CopyInsertable dans X et CopyAssignable Assigne la plage [ il. begin ( ) , il. end ( ) ) dans a . Tous les éléments existants de a sont soit assignés soit détruits N·log ( N ) en général, où N a la valeur il. size ( ) + a. size ( ) ; linéaire si [ il. begin ( ) , il. end ( ) ) est triée par rapport à value_comp ( )
b. key_comp ( ) X::key_compare L'objet de comparaison à partir duquel b a été construit Constant
b. value_comp ( ) X::value_compare Un objet de type value_compare construit à partir de l'objet de comparaison Constant
a_uniq. emplace ( args ) std:: pair <
iterator,
bool > 		value_type est EmplaceConstructible dans X à partir de args Insère un objet value_type t construit avec std:: forward < Args > ( args ) ... si et seulement s'il n'existe aucun élément dans le conteneur avec une clé équivalente à la clé de t La composante bool de la paire retournée est true si et seulement si l'insertion a lieu, et la composante itérateur de la paire pointe vers l'élément avec une clé équivalente à la clé de t Logarithmique
a_eq. emplace ( args ) iterator value_type est EmplaceConstructible dans X à partir de args Insère un objet value_type t construit avec std:: forward < Args > ( args ) ... . Si une plage contenant des éléments équivalents à t existe dans a_eq , t est inséré à la fin de cette plage Un itérateur pointant vers l'élément nouvellement inséré Logarithmique
a. emplace_hint ( p, args ) iterator Équivalent à

a. emplace (
std:: forward < Args > ( args ) ... ) , sauf que l'élément est inséré aussi près que possible de la position juste avant p

Un itérateur pointant vers l'élément avec la clé équivalente à l'élément nouvellement inséré Logarithmique en général, mais constant amorti si l'élément est inséré juste avant p
a_uniq. insert ( t ) std:: pair <
iterator,
bool > 		Si t est une rvalue non constante, value_type doit être MoveInsertable dans X ; sinon, value_type doit être CopyInsertable dans X Insère t si et seulement s'il n'existe aucun élément dans le conteneur avec une clé équivalente à celle de t La composante bool de la paire retournée est true si et seulement si l'insertion a lieu, et la composante iterator de la paire pointe vers l'élément avec une clé équivalente à celle de t Logarithmique
a_eq. insert ( t ) iterator Si t est une rvalue non constante, value_type doit être MoveInsertable dans X ; sinon, value_type doit être CopyInsertable dans X Insère t et retourne l'itérateur pointant vers l'élément nouvellement inséré. Si une plage contenant des éléments équivalents à t existe dans a_eq , t est inséré à la fin de cette plage Logarithmique
a. insert ( p, t ) iterator Si t est une rvalue non constante, value_type doit être MoveInsertable dans X ; sinon, value_type doit être CopyInsertable dans X Insère t si et seulement s'il n'existe pas d'élément avec une clé équivalente à celle de t dans les conteneurs à clés uniques ; insère toujours t dans les conteneurs à clés équivalentes. t est inséré aussi près que possible de la position juste avant p Un itérateur pointant vers l'élément avec une clé équivalente à celle de t Logarithmique en général, mais constant amorti si t est inséré juste avant p
a. insert ( i, j ) void value_type est EmplaceConstructible dans X à partir de * i . Ni i ni j ne sont des itérateurs vers a Insère chaque élément de l'intervalle [ i , j ) si et seulement s'il n'existe pas d'élément avec une clé équivalente à la clé de cet élément dans les conteneurs à clés uniques ; insère toujours cet élément dans les conteneurs à clés équivalentes N·log ( a. size ( ) + N ) , où N a la valeur std:: distance ( i, j )
a. insert_range ( rg )
(depuis C++23) 		void value_type est EmplaceConstructible dans X à partir de * ranges:: begin ( rg ) . rg et a ne se chevauchent pas Insère chaque élément de rg si et seulement s'il n'existe pas d'élément avec une clé équivalente à la clé de cet élément dans les conteneurs à clés uniques ; insère toujours cet élément dans les conteneurs à clés équivalentes N·log ( a. size ( ) + N ) , où N a la valeur ranges:: distance ( rg )
a. insert ( il ) a. insert ( il. begin ( ) , il. end ( ) )
a_uniq. insert ( nh ) insert_return_type nh est vide ou

a_uniq. get_allocator ( )
==
nh. get_allocator ( ) est true

Si nh est vide, n'a aucun effet. Sinon, insère l'élément possédé par nh si et seulement s'il n'y a pas d'élément dans le conteneur avec une clé équivalente à nh. key ( ) Si nh est vide, inserted est false , position est end ( ) , et node est vide. Sinon, si l'insertion a eu lieu, inserted est true , position pointe vers l'élément inséré, et node est vide ; si l'insertion a échoué, inserted est false , node a la valeur précédente de nh , et position pointe vers un élément avec une clé équivalente à nh. key ( ) Logarithmique
a_eq. insert ( nh ) iterator nh est vide ou

a_eq. get_allocator ( )
==
nh. get_allocator ( ) est true

Si nh est vide, n'a aucun effet et retourne a_eq. end ( ) . Sinon, insère l'élément possédé par nh et retourne un itérateur pointant vers l'élément nouvellement inséré. Si une plage contenant des éléments avec des clés équivalentes à nh. key ( ) existe dans a_eq , l'élément est inséré à la fin de cette plage. Garantit : nh est vide Logarithmique
a. insert ( p, nh ) iterator nh est vide ou

a. get_allocator ( )
==
nh. get_allocator ( ) est true

Si nh est vide, n'a aucun effet et retourne a. end ( ) . Sinon, insère l'élément possédé par nh si et seulement s'il n'existe pas d'élément avec une clé équivalente à nh. key ( ) dans les conteneurs avec des clés uniques ; insère toujours l'élément possédé par nh dans les conteneurs avec des clés équivalentes. L'élément est inséré aussi près que possible de la position juste avant p . Garantit : nh est vide si l'insertion réussit, inchangé si l'insertion échoue Un itérateur pointant vers l'élément avec une clé équivalente à nh. key ( ) Logarithmique en général, mais temps constant amorti si l'élément est inséré juste avant p
a. extract ( k ) node_type Supprime le premier élément du conteneur avec une clé équivalente à k Un node_type possédant l'élément s'il est trouvé, sinon un node_type vide log ( a. size ( ) )
a_tran. extract ( kx )
(depuis C++23) 		node_type Supprime le premier élément du conteneur avec la clé r telle que ! c ( r, kx ) && ! c ( kx, r ) est true Un node_type possédant l'élément s'il est trouvé, sinon un node_type vide log ( a_tran. size ( ) )
a. extract ( q ) node_type Supprime l'élément pointé par q Un node_type possédant cet élément Temps amorti constant
a. merge ( a2 ) void a. get_allocator ( )
==
a2. get_allocator ( ) 		Tente d'extraire chaque élément de a2 et de l'insérer dans a en utilisant l'objet de comparaison de a . Dans les conteneurs avec des clés uniques, s'il existe un élément dans a avec une clé équivalente à la clé d'un élément de a2 , alors cet élément n'est pas extrait de a2 . Garantit : Les pointeurs et références vers les éléments transférés de a2 se réfèrent à ces mêmes éléments mais en tant que membres de a . Les itérateurs se référant aux éléments transférés continueront de se référer à leurs éléments, mais ils se comportent désormais comme des itérateurs dans a , et non dans a2 . Lance : Rien sauf si l'objet de comparaison lance une exception N·log ( a. size ( ) + N ) , où N a la valeur a2. size ( )
a. erase ( k ) size_type Supprime tous les éléments du conteneur dont la clé est équivalente à k Le nombre d'éléments supprimés log ( a. size ( ) )
+ a. count ( k )
a_tran. erase ( kx )
(depuis C++23) 		size_type Supprime tous les éléments du conteneur dont la clé r vérifie ! c ( r, kx ) && ! c ( kx, r ) est true Le nombre d'éléments supprimés log ( a_tran. size ( ) )
+ a_tran. count ( kx )
a. erase ( q ) iterator Supprime l'élément pointé par q Un itérateur pointant vers l'élément immédiatement suivant q avant la suppression de l'élément. Si aucun tel élément n'existe, retourne a. end ( ) Temps constant amorti
a. erase ( r ) iterator Supprime l'élément pointé par r Un itérateur pointant vers l'élément immédiatement suivant r avant la suppression de l'élément. Si aucun tel élément n'existe, retourne a. end ( ) Complexité amortie constante
a. erase ( q1, q2 ) iterator Supprime tous les éléments dans l'intervalle
[ q1 , q2 ) 		Un itérateur pointant vers l'élément pointé par q2 avant que des éléments ne soient supprimés. Si aucun tel élément n'existe, a. end ( ) est retourné log ( a. size ( ) ) + N , où N a la valeur std:: distance ( q1, q2 )
a. clear ( ) a. erase ( a. begin ( ) , a. end ( ) ) . Garantit : a. empty ( ) est true Linéaire en a. size ( )
b. find ( k ) iterator ; const_iterator pour constante b Un itérateur pointant vers un élément avec la clé équivalente à k , ou b. end ( ) si un tel élément n'est pas trouvé Logarithmique
a_tran. find ( ke ) iterator ; const_iterator pour une constante a_tran Un itérateur pointant vers un élément avec la clé r tel que

! c ( r, ke ) &&
! c ( ke, r ) est true , ou a_tran. end ( ) si un tel élément n'est pas trouvé

Logarithmique
b. count ( k ) size_type Le nombre d'éléments avec une clé équivalente à k log ( b. size ( ) )
+ b. count ( k )
a_tran. count ( ke ) size_type Le nombre d'éléments avec la clé r tel que

! 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 pour constante b Un itérateur pointant vers le premier élément avec une clé non inférieure à k , ou b. end ( ) si un tel élément n'est pas trouvé Logarithmique
a_tran. lower_bound ( kl ) iterator ; const_iterator pour une constante a_tran Un itérateur pointant vers le premier élément avec la clé r tel que ! c ( r, kl ) , ou a_tran. end ( ) si un tel élément n'est pas trouvé Logarithmique
b. upper_bound ( k ) iterator ; const_iterator pour constante b Un itérateur pointant vers le premier élément avec une clé supérieure à k , ou b. end ( ) si un tel élément n'est pas trouvé Logarithmique
a_tran. upper_bound ( ku ) iterator ; const_iterator pour une constante a_tran Un itérateur pointant vers le premier élément avec la clé r tel que c ( ku, r ) , ou a_tran. end ( ) si un tel élément n'est pas trouvé Logarithmique
b. equal_range ( k ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > pour une constante b

Équivalent à :

return
std:: make_pair (
b. lower_bound ( k ) ,
b. upper_bound ( k ) ) ;

Logarithmique
a_tran. equal_range ( ke ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > pour la version constante de a_tran

Équivalent à :

return
std:: make_pair (
a_tran. lower_bound ( ke ) ,
a_tran. upper_bound ( ke ) ) ;

Logarithmique

Itérateurs

Les itérateurs des conteneurs associatifs satisfont aux exigences du LegacyBidirectionalIterator .

Pour les conteneurs associatifs où value_type est identique à key_type , à la fois iterator et const_iterator sont des itérateurs constants. Il n'est pas spécifié si iterator et const_iterator sont du même type ou non.

Les itérateurs des conteneurs associatifs parcourent les conteneurs dans l'ordre non décroissant des clés, où non décroissant est défini par la comparaison qui a été utilisée pour construire les conteneurs. C'est-à-dire, étant donné

  • a , un conteneur associatif
  • i et j , des itérateurs déréférençables vers a .

Si la distance de i à j est positive, alors a. value_comp ( ) ( * j, * i ) == false . De plus, si a est un conteneur associatif à clés uniques, la condition plus forte a. value_comp ( ) ( * i, * j ) ! = false s'applique.

Cette section est incomplète
Motif : Terminer les exigences.

Bibliothèque standard

Les conteneurs standards suivants satisfont aux exigences AssociativeContainer :

collection de clés uniques, triées par clés
(modèle de classe)
collection de clés, triées par clés
(modèle de classe)
collection de paires clé-valeur, triées par clés, clés uniques
(modèle de classe)
collection de paires clé-valeur, triées par clés
(modèle de classe)

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR S'applique à Comportement publié Comportement corrigé
LWG 354 C++98 lower_bound et upper_bound ne
retournaient pas l'itérateur de fin si aucun élément n'était trouvé 		ils retournent l'itérateur
de fin dans ce cas
LWG 589 C++98 les éléments auxquels i et j se réfèrent
avaient le type X::value_type 		les éléments sont implicitement
convertibles en X::value_type