Conteneurs de la bibliothèque standard C++

  • Article

La Bibliothèque standard fournit divers conteneurs de type sécurisé pour stocker des collections d’objets connexes. Les conteneurs sont des modèles de classe. Lorsque vous déclarez une variable de conteneur, vous spécifiez le type des éléments que le conteneur contiendra. Vous pouvez construire des conteneurs avec des listes d'initialiseurs. Ils ont des fonctions membres pour ajouter et supprimer des éléments et effectuer d’autres opérations.

Les itérateurs vous permettent d’itérer les éléments dans un conteneur et d’accéder à chacun de ces éléments. Vous pouvez utiliser des itérateurs explicitement à l’aide de leurs fonctions membres et opérateurs et fonctions globales. Vous pouvez également les utiliser implicitement, par exemple avec une boucle for basée sur un intervalle. Les itérateurs pour tous les conteneurs de la bibliothèque standard C++ ont une interface commune, mais chaque conteneur définit ses propres itérateurs spécialisés.

Les conteneurs peuvent être divisés en trois catégories : les conteneurs de séquence, les conteneurs associatifs et les adaptateurs de conteneur.

Conteneurs de séquences

Les conteneurs de séquence conservent l'ordonnancement des éléments insérés que vous spécifiez.

Un conteneur vector se comporte comme un tableau, mais il peut croître automatiquement selon les besoins. Il est en accès aléatoire et à stockage contigu, et sa longueur est hautement flexible. Pour ces raisons, entre autres, vector est le conteneur de séquence par défaut pour la plupart des applications. En cas de doute sur le type de conteneur de séquence à utiliser, commencez par utiliser un vecteur. Pour plus d’informations, consultez vector Classe.

Un array conteneur a certaines des forces de vector, mais la longueur n’est pas aussi flexible. Pour plus d’informations, consultez array Classe.

Un conteneur deque (file d'attente double) autorise les insertions et les suppressions rapides au début et à la fin du conteneur. Il partage les avantages d’accès aléatoire et de longueur flexible de vector, mais n’est pas contigu. Pour plus d’informations, consultez deque Classe.

Un list conteneur est une liste doublement liée qui permet l’accès bidirectionnel, les insertions rapides et les suppressions rapides n’importe où dans le conteneur, mais vous ne pouvez pas accéder de manière aléatoire à un élément dans le conteneur. Pour plus d’informations, consultez list Classe.

Un conteneur forward_list est une liste à liaison unique, la version à accès direct de list. Pour plus d’informations, consultez forward_list Classe.

Conteneurs associatifs

Dans les conteneurs associatifs, les éléments sont insérés dans un ordre prédéfini, par exemple par ordre croissant. Des conteneurs associatifs non ordonnés sont également disponibles. Les conteneurs associatifs peuvent être regroupés dans deux sous-ensembles : les maps et les sets.

Un map, parfois appelé dictionnaire, se compose d'une paire clé/valeur. La clé est utilisée pour trier la séquence et la valeur est associée à cette clé. Par exemple, un map peut contenir des clés qui représentent chaque mot unique dans un texte et des valeurs correspondantes qui représentent le nombre de fois que chaque mot apparaît dans le texte. La version non ordonnée de map est unordered_map. Pour plus d’informations, consultez Classe et unordered_map classe.map

Un set est simplement un conteneur croissant d'éléments uniques. La valeur est également la clé. La version non ordonnée de set est unordered_set. Pour plus d’informations, consultez Classe et unordered_set classe.set

map et set autorisent l'insertion d'une seule instance d'une clé ou d'un élément dans le conteneur. Si plusieurs instances d'éléments sont nécessaires, utilisez multimap ou multiset. Les versions non ordonnées sont unordered_multimap et unordered_multiset. Pour plus d’informations, consultez multimap Classe,unordered_multimapClasse,multisetClasse et unordered_multiset Classe.

Les maps et les sets ordonnés prennent en charge les itérateurs bidirectionnels et leurs équivalents non ordonnés prennent en charge les itérateurs vers l'avant. Pour plus d'informations, consultez Itérateurs.

Recherche hétérogène dans les conteneurs associatifs (C++14)

Les conteneurs associatifs ordonnés (map, multimap, set et multiset) prennent désormais en charge la recherche hétérogène, ce qui signifie que vous n’êtes plus obligé de passer exactement le même type d’objet que la clé ou l’élément dans les fonctions membres telles que find() et lower_bound(). Au lieu de cela, vous pouvez passer n'importe quel type pour lequel un operator< surchargé est défini et permet la comparaison avec le type de clé.

La recherche hétérogène est activée sur une base d’opt-in lorsque vous spécifiez le std::less<> comparateur « std::greater<> diamond functor » lors de la déclaration de la variable conteneur, comme illustré ici :

std::set<BigObject, std::less<>> myNewSet;

Si vous utilisez le comparateur par défaut, le conteneur se comporte exactement comme dans C++11 et versions antérieures.

L’exemple suivant montre comment surcharger operator< pour permettre aux utilisateurs d’effectuer std::set des recherches simplement en passant une petite chaîne qui peut être comparée au membre de BigObject::id chaque objet.

#include <set>
#include <string>
#include <iostream>
#include <functional>

using namespace std;

class BigObject
{
public:
    string id;
    explicit BigObject(const string& s) : id(s) {}
    bool operator< (const BigObject& other) const
    {
        return this->id < other.id;
    }

    // Other members....
};

inline bool operator<(const string& otherId, const BigObject& obj)
{
    return otherId < obj.id;
}

inline bool operator<(const BigObject& obj, const string& otherId)
{
    return obj.id < otherId;
}

int main()
{
    // Use C++14 brace-init syntax to invoke BigObject(string).
    // The s suffix invokes string ctor. It is a C++14 user-defined
    // literal defined in <string>
    BigObject b1{ "42F"s };
    BigObject b2{ "52F"s };
    BigObject b3{ "62F"s };
    set<BigObject, less<>> myNewSet; // C++14
    myNewSet.insert(b1);
    myNewSet.insert(b2);
    myNewSet.insert(b3);
    auto it = myNewSet.find(string("62F"));
    if (it != myNewSet.end())
        cout << "myNewSet element = " << it->id << endl;
    else
        cout << "element not found " << endl;

    // Keep console open in debug mode:
    cout << endl << "Press Enter to exit.";
    string s;
    getline(cin, s);
    return 0;
}

//Output: myNewSet element = 62F

Les fonctions membres suivantes dans map, multimap, set et multiset ont été surchargées pour prendre en charge la recherche hétérogène :

  1. find

  2. count

  3. lower_bound

  4. upper_bound

  5. equal_range

Adaptateurs de conteneur

Un adaptateur de conteneur est une variante d'un conteneur de séquence ou associatif qui restreint l'interface à des fins de simplicité et de clarté. Les adaptateurs de conteneur ne prennent pas en charge les itérateurs.

Un conteneur queue suit la sémantique FIFO (premier entré, premier sorti). Le premier élément qui est transféré par push (autrement dit, qui est inséré dans la file d’attente) est le premier à être dépilé (autrement dit, à être supprimé de la file d’attente). Pour plus d’informations, consultez queue Classe.

Un conteneur priority_queue est organisé de telle façon que l'élément qui a la valeur la plus élevée soit toujours le premier dans la file d'attente. Pour plus d’informations, consultez priority_queue Classe.

Un conteneur stack suit la sémantique LIFO (dernier entré, premier sorti). Le dernier élément inséré sur la pile est le premier élément dépilé. Pour plus d’informations, consultez stack Classe.

Étant donné que les adaptateurs de conteneur ne prennent pas en charge les itérateurs, ils ne peuvent pas être utilisés avec les algorithmes de bibliothèque standard C++. Pour plus d’informations, consultez Algorithmes.

Exigences pour les éléments de conteneurs

En général, s’ils peuvent être copiés, les éléments insérés dans un conteneur de la bibliothèque standard C++ peuvent être de presque n’importe quel type d’objet. Les éléments qui ne peuvent qu'être déplacés, par exemple ceux tel que vector<unique_ptr<T>> et qui sont créés à l'aide de unique_ptr<> fonctionnent tant que vous n'appelez pas de fonctions membres qui essaient de les copier.

Le destructeur n’est pas autorisé à lever une exception.

Les conteneurs associatifs ordonnés (décrits plus haut dans cet article) doivent avoir un opérateur de comparaison public défini. Par défaut, l’opérateur est operator<, mais même les types qui ne fonctionnent operator< pas sont pris en charge.

Certaines opérations sur les conteneurs peuvent également nécessiter un constructeur public par défaut et un opérateur d'équivalence public. Par exemple, les conteneurs associatifs non ordonnés nécessitent la prise en charge de l'égalité et du hachage.

Accès aux éléments de conteneurs

Les éléments des conteneurs sont accessibles à l'aide d'itérateurs. Pour plus d'informations, consultez Itérateurs.

Remarque

Vous pouvez également utiliser des boucles for basées sur une plage pour itérer des collections de la bibliothèque standard C++.

Comparaison des conteneurs

Tous les conteneurs surchargent l'opérateur == pour la comparaison de deux conteneurs du même type qui ont le même type d'élément. Vous pouvez utiliser == pour comparer une chaîne> vectorielle à une autre chaîne> vectorielle<<, mais vous ne pouvez pas l’utiliser pour comparer une chaîne> vectorielle<à une chaîne> de liste<ou une chaîne> vectorielle<à un vecteur<char*>. En C++98/03, vous pouvez utiliser std::equal ou std::mismatch comparer des types de conteneurs dissimilar et/ou des types d’éléments. En C++11, vous pouvez également utiliser std::is_permutation. Toutefois, dans tous ces cas, les fonctions supposent que les conteneurs sont de la même longueur. Si la deuxième plage est plus courte que la première, un comportement non défini se produit. Si la deuxième plage est plus longue, les résultats peuvent encore être incorrects, car la comparaison ne continue jamais au-delà de la fin de la première plage.

Comparaison de conteneurs différents (C++14)

En C++14 et versions ultérieures, vous pouvez comparer des conteneurs dissimilar et/ou des types d’éléments dissimilar à l’aide de l’une std::equaldes surcharges de std::mismatchfonction ou std::is_permutation d’un conteneur qui acceptent deux plages complètes. Ces surcharges vous permettent de comparer des conteneurs ayant des longueurs différentes. Elles sont beaucoup moins vulnérables aux erreurs des utilisateurs et sont optimisées pour retourner la valeur false en temps fixe quand des conteneurs de longueurs différentes sont comparés. Par conséquent, nous vous recommandons d’utiliser ces surcharges, sauf si vous avez une raison claire de ne pas utiliser, ou si vous utilisez un std::list conteneur, qui ne bénéficie pas des optimisations à double plage.

Voir aussi

Conteneurs parallèles
<sample container>
Sécurité des threads dans la bibliothèque C++ Standard