Namespaces
Variants

std:: flat_set

From cppreference.net
C++
Containers library
std::flat_set
Member types
Member functions
Helper classes
Tags
Deduction guides
Défini dans l'en-tête <flat_set>
template <

class Key,
class Compare = std:: less < Key > ,
class KeyContainer = std:: vector < Key >

> class flat_set ;
(depuis C++23)

Le flat set est un adaptateur de conteneur qui fournit les fonctionnalités d'un conteneur associatif stockant un ensemble trié d'objets uniques de type Key . Le tri est effectué en utilisant la fonction de comparaison de clés Compare .

Le modèle de classe flat_set agit comme un wrapper pour le conteneur trié sous-jacent passé en tant qu'objet de type KeyContainer .

Partout où la bibliothèque standard utilise les exigences Compare , l'unicité est déterminée en utilisant la relation d'équivalence. Informellement, deux objets a et b sont considérés équivalents si aucun n'est comparé comme inférieur à l'autre : ! comp ( a, b ) && ! comp ( b, a ) .

std::flat_set satisfait aux exigences de Container , ReversibleContainer , exigences optionnelles de conteneur , et toutes les exigences de AssociativeContainer (y compris la complexité de recherche logarithmique), sauf que :

  • les exigences relatives aux nœuds ne sont pas applicables,
  • les exigences d'invalidation des itérateurs diffèrent,
  • la complexité des opérations d'insertion et d'effacement est linéaire.

Un ensemble plat prend en charge la plupart des AssociativeContainer opérations qui utilisent des clés uniques.

Toutes les fonctions membres de std::flat_set sont constexpr : il est possible de créer et d'utiliser des objets std::flat_set lors de l'évaluation d'une expression constante.

Cependant, les objets std::flat_set ne peuvent généralement pas être constexpr , car toute allocation de mémoire dynamique doit être libérée lors de la même évaluation d'expression constante.

(depuis C++26)

Table des matières

Invalidation des itérateurs

Cette section est incomplète

Paramètres du modèle

Key - Le type des éléments stockés. Le programme est mal formé si Key n'est pas du même type que KeyContainer::value_type .
Compare - Un type Compare fournissant un ordre strict faible.
KeyContainer - Le type du conteneur sous-jacent SequenceContainer pour stocker les éléments. Les itérateurs de ce conteneur doivent satisfaire LegacyRandomAccessIterator ou modéliser random_access_iterator .

Les conteneurs standards std::vector et std::deque satisfont ces exigences.

Types membres

Type Définition
container_type Key Container
key_type Key
value_type Key
key_compare Compare
value_compare Compare
reference value_type &
const_reference const value_type &
size_type typename KeyContainer :: size_type
difference_type typename KeyContainer :: difference_type
iterator défini par l'implémentation LegacyRandomAccessIterator , ConstexprIterator (depuis C++26) et random_access_iterator vers value_type
const_iterator défini par l'implémentation LegacyRandomAccessIterator , ConstexprIterator (depuis C++26) et random_access_iterator vers const value_type
reverse_iterator std:: reverse_iterator < iterator >
const_reverse_iterator std:: reverse_iterator < const_iterator >

Objets membres

Membre Description
container_type c (privé) le conteneur adapté
( objet membre d'exposition uniquement* )
key_compare compare (privé) l'objet fonction de comparaison
( objet membre d'exposition uniquement* )

Fonctions membres

construit le flat_set
(fonction membre publique)
(destructor)
(implicitly declared)
détruit chaque élément de l'adaptateur de conteneur
(fonction membre publique)
assigne des valeurs à l'adaptateur de conteneur
(fonction membre publique)
Itérateurs
retourne un itérateur vers le début
(fonction membre publique)
retourne un itérateur vers la fin
(fonction membre publique)
retourne un itérateur inverse vers le début
(fonction membre publique)
retourne un itérateur inverse vers la fin
(fonction membre publique)
Capacité
vérifie si l'adaptateur de conteneur est vide
(fonction membre publique)
retourne le nombre d'éléments
(fonction membre publique)
retourne le nombre maximum possible d'éléments
(fonction membre publique)
Modificateurs
construit un élément en place
(fonction membre publique)
construit des éléments en place en utilisant un indice
(fonction membre publique)
insère des éléments
(fonction membre publique)
insère une plage d'éléments
(fonction membre publique)
extrait le conteneur sous-jacent
(fonction membre publique)
remplace le conteneur sous-jacent
(fonction membre publique)
efface les éléments
(fonction membre publique)
échange le contenu
(fonction membre publique)
efface le contenu
(fonction membre publique)
Recherche
trouve l'élément avec une clé spécifique
(fonction membre publique)
retourne le nombre d'éléments correspondant à une clé spécifique
(fonction membre publique)
vérifie si le conteneur contient un élément avec une clé spécifique
(fonction membre publique)
renvoie un itérateur vers le premier élément non inférieur à la clé donnée
(fonction membre publique)
retourne un itérateur vers le premier élément supérieur à la clé donnée
(fonction membre publique)
renvoie la plage d'éléments correspondant à une clé spécifique
(fonction membre publique)
Observateurs
renvoie la fonction qui compare les clés
(fonction membre publique)
renvoie la fonction qui compare les clés dans les objets de type value_type
(fonction membre publique)

Fonctions non membres

(C++23)
compare lexicographiquement les valeurs de deux flat_set s
(modèle de fonction)
(C++23)
spécialise l'algorithme std::swap
(modèle de fonction)
(C++23)
efface tous les éléments satisfaisant des critères spécifiques
(modèle de fonction)

Classes d'assistance

(C++23)
spécialise le trait de type std::uses_allocator
(spécialisation de modèle de classe)

Étiquettes

(C++23)
indique que les éléments d'une plage sont triés et uniques
(étiquette)

Guides de déduction

Notes

Les types membres iterator et const_iterator peuvent être des alias vers le même type. Cela signifie que définir une paire de surcharges de fonction utilisant ces deux types comme types de paramètres peut violer la Règle de Définition Unique . Puisque iterator est convertible en const_iterator , une fonction unique avec un const_iterator comme type de paramètre fonctionnera à la place.

Certains avantages du flat set par rapport aux autres adaptateurs de conteneur standards sont :

  • Recherche potentiellement plus rapide (même si les opérations de recherche ont une complexité logarithmique).
  • Itération beaucoup plus rapide : itérateurs à accès aléatoire au lieu d' itérateurs bidirectionnels .
  • Consommation mémoire réduite pour les petits objets (et pour les grands objets si KeyContainer :: shrink_to_fit ( ) est disponible).
  • Meilleures performances de cache (selon KeyContainer , les clés sont stockées dans un ou plusieurs blocs contigus de mémoire).

Certains inconvénients de flat set sont :

  • Itérateurs non stables (les itérateurs sont invalidés lors de l'insertion et de la suppression d'éléments).
  • Les valeurs de types non copiables et non déplaçables ne peuvent pas être stockées.
  • Sûreté d'exception plus faible (les constructeurs de copie/déplacement peuvent lever des exceptions lors du décalage des valeurs dans les suppressions et insertions).
  • Insertion et suppression plus lentes (c'est-à-dire linéaires), particulièrement pour les types non déplaçables.
Macro de test de fonctionnalité Valeur Std Fonctionnalité
__cpp_lib_flat_set 202207L (C++23) std::flat_set et std::flat_multiset
__cpp_lib_constexpr_flat_set 202502L (C++26) constexpr std::flat_set

Exemple

Cette section est incomplète
Raison : aucun exemple

Voir aussi

(C++23)
adapte un conteneur pour fournir une collection de clés, triées par clés
(modèle de classe)
collection de clés uniques, triées par clés
(modèle de classe)
(C++11)
collection de clés uniques, hachées par clés
(modèle de classe)