La version 11 du C++ a introduit de nouveaux conteneurs standards. Cet article décrit les différents types de conteneurs dont vous disposez en C++11 et s’intéresse tout particulièrement aux vector, qui reste le conteneur à préférer de par son efficacité et sa simplicité.
Les conteneurs standards se classent en 2 grandes catégories : les conteneurs séquentiels et les conteneurs associatifs. Ces derniers utilisent une clé pour accéder à la valeur. En plus des conteneurs classiques, quelques types sont considérés comme des conteneurs, par exemple string.
Les conteneurs séquentiels sont : vector, deque, list, forward_list. Cette dernière est apparue avec C++11.
Les conteneurs associatifs sont : map, multimap, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset. Les 4 derniers sont apparus avec C++11.
La classe vector
Pour utiliser vector, inclure le fichier <vector>
Le vecteur est un conteneur séquentiel, tableau dynamique. Les éléments sont stockés contigüement, et donc accessibles via des pointeurs. Le vecteur alloue la mémoire lorsque nécessaire, et en général, plus que nécessaire. La capacité du vecteur (accessible par capacity() ) est la mémoire allouée, alors que la taille est le nombre d’éléments réellement stockés (accessible par size() ). Il est possible de réduire la capacité à la taille en appelant shrink_to_fit(). Au contraire, on peut réserver de la mémoire an avance avec reserve().
L’efficacité du vector est grande : l’accès aléatoire est en temps constant, ce qui signifie que quel que soit le nombre d’éléments dans le vector, le temps d’accès ne change pas. Même chose pour l’ajout ou la suppression d’un élément en extrémité, mais l’insertion ou la suppression au milieu du vector est fonction linéaire du nombre d’éléments. Enfin, les types utilisables avec vector sont les types qui supportent l’affectation et la copie (par constructeur), ou bien depuis C++11, l’affectation et la copie par move. Le concept de move est propre à la version 11 du C++. Sans s’étendre sur le sujet, la notion de move est la même chose que la copie, mais sans la garantie que l’objet d’origine est encore utilisable (ce qui est la moindre des choses dans le cas de la copie). Enfin, la classe vector est une classe template, elle a une spécialisation qui est vector<bool>, optimisant l’occupation mémoire.
std::vector<A> v_vide; //construction par défaut, vide
A a{ 0 };
std::vector<A> v_dimensionne_dft_ctor{ 5 }; // contient 5 éléments construits par défaut
std::vector<A> v_dimensionne_dft_ctor{ 5, a }; // contient 5 éléments recopies de a
std::vector<A> v_initialise { A(1), A(2) , A(3) , A(5), A(8), A(13), A(21) }; // par liste d’initialisation
std::vector<A> v_a_partir_de{ v_initialise }; // construit par copie
L’opérateur d’affectation écrase les données de l’un par l’autre.
Les accès aux données se font par l’opérateur [i], la fonction membre at(i), les fonctions membres front () et back () qui retournent les données aux extrémités.
Mais en général, on exploite les données d’un vecteur (et des autres conteneurs) et appelant begin() et end() qui retournent des itérateurs sur le début et l’après-fin du vecteur. Le parcours du vecteur se fera donc en avançant de la valeur de begin() jusqu’à ce que != end(). Les itérateurs sont les objets retournés par ces fonctions membres, qui permettent de s’abstraire de la nature du conteneur lorsqu’on réalise un algorithme sur un conteneur. Il existe aussi cbegin()/cend(), rbegin()/rend() et cdbegin()/crend() retournant respectivement un const_iterator, reverse_interator et const_reverse_iterator.
std::vector<A>::iterator it = v_initialise.begin();
while (it != v_initialise.end()) {
(*it).f();
++it;
}
Pour insérer, il vaut mieux utiliser push_back(e) que insert. On peut aussi dépiler avec pop_back() ou pop_front(). Et enfin les fonctions membres erase() et clear() permettent de nettoyer le vecteur. Quelques autres fonctions membres sont disponibles, plus anecdotiques.
v_initialise.push_back(a); //en O(1)
v_initialise.insert(v_initialise.begin()++, a); //en O(n)
Les autres conteneurs séquentiels
La classe list (include #include<list>) représente la liste doublement chaînée, elle est efficace pour les insertions et suppressions au milieu du conteneur.
La classe forward_list (include #include<forward_list>) est une liste simplement chaînée, efficace pour de petits nombres d’éléments.
std::forward_list<int> ma_liste;
ma_liste.push_front(4);
La classe deque (include #include<deque>) est comme un vector, mais peut être manipulée avec push_back comme avec push_front.
std::deque<int> ma_double_queue;
ma_double_queue.push_back(4);
ma_double_queue.push_front(5);
for (auto e : ma_double_queue) {
std::cout << e << std::endl;
}
Les conteneurs associatifs
Il s’agit de conteneurs qui rangent les valeurs en fonction de clés.
La classe map<K,V> (include #include<map>) est le tableau associatif. Les valeurs sont accessibles par accès avec l’opérateur [K]. L’implémentation typique suppose de trier les clés (par défaut avec <), mais il existe en C++11 une version basée sur la table de hashage (algorithme std ::hash<K>) qui s’appelle unordered_map (include #include<unordered_map>).
std::map<std::string, int> ma_map;
ma_map[« fabien »] = 5;
for (std::pair<std::string,int> p : ma_map){
std::cout << p.first<<« -« <<p.second << std::endl;
}
La map contient des std ::pair. L’utilisation de auto aurait grandement simplifié le code.
La classe multimap<K,V> (include #include<map>) est une map avec la possibilité de mettre plusieurs valeurs en face d’une clé. La version table de hashage s’appelle unordered_multimap.
std::multimap<std::string, int> ma_map;
ma_map.insert(std::make_pair(« fabien »,5));
ma_map.insert(std::make_pair(« fabien », 7));
auto p = ma_map.lower_bound(« fabien »);
auto d = ma_map.upper_bound(« fabien »);
std::cout << (*p).first << » : » << std::endl;
while (p != d) {
std::cout << (*p).second << std::endl;
++p;
}
Le principe du parcours est de trouver le premier itérateur et d’aller vers le dernier. La clé est dans le champ first et la valeur dans second.
Enfin, il y a les set, multiset, unordered_set, unordered_multiset qui sont comme des map, mais la clé est la valeur elle-même. Les includes sont <set> et <unordered_set>
std::set<std::string> mon_set;
mon_set.insert(« fabien »);
mon_set.insert(« fabien »); // valeur non insérée car identique
for (auto p : mon_set){
std::cout << p << std::endl;
}
Les conteneurs standards du C++11 sont donc enrichis par rapport à la version C++98. Il faut aussi rappeler que ces conteneurs sont en général manipulés via les itérateurs, et que de nombreux algorithmes sont disponibles. Ces algorithmes ont comme intérêt d’être prêts à l’emploi et leur usage améliore nettement la lisibilité du code.
