Il existe plusieurs types de conteneurs de données dans la
bibliothèque standard du C++. On peut penser rapidement au std::vector à la std::list ou au std::map mais il en existe plusieurs autres et il important de choisir le bon type de conteneur selon l'utilisation que l'on en fera. Nous allons voir ci-dessous chaque type de conteneur et leurs particularités.
tableau style-C
Le tableau style-C comme son nom l'indique est un tableau d'éléments provenant du langage C. Le nombre d'éléments d'un tableau est statique cela veut donc dire que la taille du tableau est fixe une fois créé. Si on veut ajouter ou retirer un élément, on devra recréer un nouveau tableau avec la nouvelle taille puis copier les éléments qu'on souhaite conserver. Les éléments d'un tableau sont contigus en mémoire. On peut donc accéder directement à un élément à partir de son index, c'est-à-dire sa position dans le conteneur. Lorsqu'on initialise un tableau, c'est en fait un pointeur vers le premier élément du tableau qui nous est retourné.
Exemple 1 : Création d'un tableau dont la taille est connue au moment de la compilation
int myNumbers[] { 3, 5, 7, 12, 18, 21 };
cout << "Premier élément: " << myNumbers[0] << " Dernier élément: " << myNumbers[5] << "\n";
// Output : Premier élément: 3 Dernier élément: 21
Exemple 2: Création d'un tableau dont la taille est connu au moment de l'exécution
size_t nbElements;
cout << "Entrer le nombre d'éléments du tableau: ";
cin >> nbElements;
unique_ptr<int[]> myNumbers (new int[nbElements]);
for(size_t i=0; i<nbElements; i++) {
myNumbers[i] = i;
}
cout << "Premier élément: " << myNumbers[0] << " "
"Dernier élément: " << myNumbers[nbElements-1] << "\n";
// Input : 8
// Output : Premier élément: 0 Dernier élément: 7
On peut voir dans les exemples ci-dessus que les éléments sont accéder via l'opérateur d'indexation, mais il est également possible d'utiliser l'arithmétique des pointeurs pour accéder aux éléments. Tel qu'énoncé au départ, la variable utilisée pour accéder au tableau ne contient pas les éléments du tableau mais elle contient un pointeur sur le premier élément du tableau.
Repartons l'exemple du code précédent en utilisant l'arithmétique des pointeurs pour afficher le premier et le troisième élément, c'est-à-dire les éléments aux index 0 et 2.
Exemple 3: Accès à un élément via l'arithmétique des pointeurs
int *ptrThirdElement = myNumbers.get() + 2;
cout << "Premier élément: " << myNumbers[0] << " "
"Troisième élément: " << *ptrThirdElement << "\n";
On peut voir dans l'image ci-dessous que la variable myNumbers est en fait un pointeur qui pointe à l'adresse mémoire 0x4176d0 et sachant que la taille d'un int sur mon système est de 4 octets alors on se déplace de 4 octets pour le deuxième élément donc 0x4176d4 puis encore de 4 octets pour le troisième élément alors 0x4176d8. Il faut bien sûr déréférencer le pointeur à l'aide l'opérateur de déréférencement (*) pour pouvoir afficher son contenu.
L'opérateur ++ sur un pointeur n'incrémente pas l'adresse du pointeur de 1 mais bien d'une fois la taille de l'élément pointé.
En ce qui concerne la taille, c'est la responsabilité du développeur de connaitre et conserver la taille du tableau tout au long de son existence. Si par exemple on veut passer un tableau style-C dans une fonction il faut passer le pointeur du premier élément puis la taille du tableau.
Exemple 4: Passage d'un tableau style-C à une fonction
void printArray(const unique_ptr<int[]> &p_MyNumbers, size_t p_NbElements)
{
cout << "Premier élément: " << p_MyNumbers[0] << " "
"Dernier élément: " << p_MyNumbers[p_NbElements-1] << "\n";
}
int main(int argc, char *argv[])
{
size_t nbElements;
cout << "Entrer le nombre d'éléments du tableau: ";
cin >> nbElements;
unique_ptr<int[]> myNumbers (new int[nbElements]);
for(size_t i=0; i<nbElements; i++) {
myNumbers[i] = i;
}
printArray(myNumbers, nbElements);
return EXIT_SUCCESS;
}
Le fait de passer un pointeur et une taille comporte un risque d'erreur de la part du développeur alors pour les tableaux dont la taille est connue à la compilation il est conseillé d'utiliser un span. Vous pouvez utiliser la classe span de la bibliothèque GSL (
Guidelines Support Library) si le standard que vous utilisez est antérieur à C++20 et directement la classe std::span si vous utilisez le standard C++20.
Exemple 5: Utilisation d'un gsl::span
void printArray(gsl::span<int> &p_MyNumbers)
{
cout << "Premier élément: " << p_MyNumbers[0] << " "
"Dernier élément: " << p_MyNumbers[p_MyNumbers.size()-1] << "\n";
}
int main(int argc, char *argv[]){
int myNumbers[] { 3, 5, 7, 12, 18, 21 };
gsl::span<int> spanMyNumbers(myNumbers);
printArray(spanMyNumbers);
return EXIT_SUCCESS;
}
Tel qu'indiqué dans les C++ Core Guidelines il est préférable d'utiliser le std::array pour les conteneurs dont la taille est fixe plutôt qu'un tableau style-C. Nous verrons les avantages qu'offre le std::array dans la prochaine section.
Temps d'accès à un élément : O(1)
Temps d'insertion/retrait d'un élément : O(n)
std::array
#include <array>
Le nombre d'éléments d'un array est fixe, c'est-à-dire qu'il ne peut pas être changé une fois créé. Le std::array a l'avantage de connaître sa taille comparativement au tableau de style-C donc on n'a pas à passer un pointeur et une taille lors d'un appel de fonction, on peut simplement passer le tableau en question comme dans l'exemple ci-dessous :
Exemple 6: Passage d'un std::array par référence constante à une fonction
void printArray(const array<int, 6> &p_MyNumbers)
{
try {
cout << "Premier élément: " << p_MyNumbers.at(0) << " "
"Dernier élément: " << p_MyNumbers.at(p_MyNumbers.size()-1) << '\n';
}
catch(out_of_range const& err) {
cerr << "Élément out_of_range." << '\n';
}
}
int main()
{
array<int, 6> myNumbers { 3, 5, 7, 12, 18, 21 };
printArray(myNumbers);
return EXIT_SUCCESS;
}
Comme vous pouvez voir dans l'exemple ci-dessus, un des avantages qu'offre le std::array est la vérification des bornes via la méthode at. Si on tente d'accéder à un élément qui se trouve en dehors du tableau une exception de type std::out_of_range sera déclenchée.
Il est également possible d'utiliser les itérateurs de la bibliothèque standard pour accéder aux différents éléments.
Exemple 7: Utilisation des itérateurs de la bibliothèque standard
void printArray(const array<int, 6> &p_MyNumbers)
{
//Afficher tous les éléments
for(const auto &item : p_MyNumbers) {
cout << item << '\n';
}
}
int main()
{
array<int, 6> myNumbers { 3, 5, 7, 12, 18, 21 };
printArray(myNumbers);
return EXIT_SUCCESS;
}
Temps d'accès à un élément : O(1)
Temps d'insertion/retrait d'un élément : O(n)
std::vector
#include <vector>
Le vector est un conteneur dont les éléments sont contigus en mémoire. Il est donc possible d'accéder directement à un élément selon son index via l'opérateur d'indexation ou via la méthode at vérifie du même coup les limites tel que démontré dans la classe std::array.
Le nombre d'éléments d'un vecteur est dynamique autrement dit sa taille peut varier. Le vecteur a une taille et une capacité. La taille retournée par la méthode size() représente le nombre d'éléments présents dans le vecteur. La capacité quant à elle est retournée par la méthode capacity() et représente le nombre d'éléments que le vecteur pourra contenir avant d'être de nouveau redimensionné. Lorsque le vecteur doit être redimensionné pour y inclure un nouvel élément, la capacité est doublée.
vector<int> myNumbers { 3, 5, 7, 12, 18, 21 };
// myNumbers.size() égal 6 et myNumbers.capacity() égal 6
myNumbers.emplace_back(24);
// myNumbers.size() égal maintenant 7 et
// myNumbers.capacity() égal maintenant 12, car la capacité a été doublée.
Dans les versions antérieures à C++11, les méthodes ajouter/insérer des éléments étaient insert et push_back. Il suffisait de construire l'élément à ajouter puis appeler la méthode. L'objet était donc créé puis déplacé ou copié dans le vecteur. Cela représente donc deux opérations. Avec les nouvelles méthodes emplace et emplace_back, il suffit de passer les arguments pour créer l'objet et le vecteur s'occupera lui-même d'appeler le constructeur et de créer l'objet directement en place. C'est plus efficace ainsi.
Exemple 8: Démonstration des méthodes push_back vs emplace_back
class Student {
public:
Student(string firstName, string lastName)
: firstName(firstName), lastName(lastName)
{
cout << "L'objet est créé.\n";
}
Student(Student&& other)
: firstName(std::move(other.firstName)), lastName(std::move(other.lastName))
{
std::cout << "L'objet est déplacé.\n";
}
Student& operator=(const Student& other) = default;
const string &getFirstName() const { return firstName; }
const string &getLastName() const { return lastName; }
private:
string firstName;
string lastName;
};
int main()
{
vector<Student> students;
students.reserve(2);
cout << "Ajout de l'étudiant Joe Blow\n";
students.push_back(Student("Joe", "Blow"));
cout << "Ajout de l'étudiante Jane Doe\n";
students.emplace_back("Jane", "Doe");
return EXIT_SUCCESS;
}
// Output:
// Ajout de l'étudiant Joe Blow
// L'objet est créé.
// L'objet est déplacé.
// Ajout de l'étudiante Jane Doe
// L'objet est créé.
Comme on a pu le voir dans l'exemple précédent, le mot clé reserve permet d'augmenter la capacité d'un vecteur sans pour autant y ajouter d'éléments. Les emplacements pour les futurs sont donc réservés, mais non utilisés. Cela permet d'éviter de multiples redimensionnement, donc des coûts de copie en mémoire, lorsqu'on sait à l'avance quel sera le nombre d'éléments requis.
Les conteneurs dont les éléments sont contigus en mémoire peuvent bénéficier de la rapiditidé de la mémoire cache. Lorsqu'on demande à lire/écrire une donnée en mémoire, le processeur chargera non seulement le contenu de l'adresse mémoire dans ses différents niveaux de mémoire cache, mais également un bloc de données plus grand sachant fort bien que le logiciel risque d'avoir besoin de ces éléments connexes au cours des prochaines instructions. Cela peut avoir un très grand impact sur les performances d'un conteneur de données.
Comme le temps d'ajout/suppression d'un élément est en O(n) on sera alors tenté de regarder vers la std::list si on a vraiment beaucoup d'opérations de ce genre.
Comme l'indique Bjarne Stroupstrup dans son livre "
A Tour of C++", le vecteur devrait être votre choix de conteneur par défaut à moins d'avoir de solide raison d'utiliser un autre type de conteneur.
Temps d'accès à un élément : O(1)
Temps d'insertion/retrait d'un élément : O(n)
std::list
#include <list>
La std::list comme son nom l'indique est une liste d'éléments doublement chainée. Cela veut dire qu'on peut parcourir la liste dans les deux sens : du début vers la fin et de la fin vers le début, mais contrairement aux conteneurs précédents, on ne peut pas accéder à un élément directement.
Le temps d'insertion/suppression d'un élément est de O(1) ce qui est donc est un très gros avantage si la taille du conteneur est fréquemment modifiée.
Exemple 9: Démonstration de l'utilisation d'une liste (ajout au début, ajout à la fin et parcours)
int main(int argc, char *argv[])
{
list<string> countries { "Canada", "France", "United States" };
countries.emplace_front("Belgium");
countries.emplace_back("Vanuatu");
//Affichage des pays dans l'ordre
for(const auto &country : countries) {
cout << country << '\n';
}
//Affichage des pays den ordre inverse
for(auto iter=countries.rbegin(); iter != countries.rend(); iter++) {
cout << *iter << '\n';
}
//Affichage du troisième pays de la liste (France)
size_t i {0};
for(const auto &country : countries) {
if (i == 2) {
cout << country << '\n';
break;
}
i++;
}
return EXIT_SUCCESS;
}
L'empreinte mémoire de chaque élément sera donc plus grande, car pour chaque élément on aura un pointeur vers l'élément précédent ainsi qu'un pointeur vers l'élément suivant.
Les éléments n'étant pas contigus en mémoire nous ne pourront pas profiter des différentes optimisations liées aux mémoires caches. Voir
Principe de localité pour plus d'infos.
Temps d'accès à un élément : O(n)
Temps d'insertion/retrait d'un élément : O(1)
std::forward_list
#include <forward_list>
La std::forward_list est exactement comme la std::list à l'exception près qu'on peut seulement parcourir la liste en ordre. Chaque élément a seulement un pointeur vers l'élément suivant, mais pas vers l'élément précédent. La forward_list a donc une empreinte mémoire plus légère que la list.
Temps d'accès à un élément : O(n)
Temps d'insertion/retrait d'un élément : O(1)
std::map
#include <map>
Le std::map est un conteneur d'association entre une clé et une valeur. Ce conteneur est normalement implanté sous forme d'arbre binaire rouge et noir. Les éléments du conteneur sont triés selon la clé alors si votre clé est une classe personnalisée vous devrez implémenter les opérateurs comparaisons. La clé dans un std::map doit pas contre être unique. Si on tente d'ajouter un élément avec la même clé, l'ajout sera ignoré sans retourner d'erreur.
Exemple 10: Démonstration de l'utilisation d'un std::map
int main(int argc, char *argv[])
{
map<int, string> employees
{
{320, "Joe Blow"},
{543, "Jane Doe"},
{735, "Aaron Black"}
};
employees.emplace(pair<int, string>(355, "John McClean"));
//Affichage des employés dans l'ordre de la clé
for(const auto &employee : employees) {
cout << "ID: " << employee.first << " Name: " << employee.second << '\n';
} //Output:
//ID: 320 Name: Joe Blow
//ID: 355 Name: John McClean
//ID: 543 Name: Jane Doe
//ID: 735 Name: Aaron Black
//Trouver l'employé 543
cout << "Employé 543: " << employees.at(543) << '\n';
//Output:
//Employé 543: Jane Doe
//Ajouter un employé via l'opérateur d'indexation.
employees[777] = "Byron Joe";
//Vérifier si un employé existe
auto iter = employees.find(777);
if (iter != employees.end()) {
cout << "Employé 777: " << employees.at(777) << '\n'; }
//Output:
//Employé 777: Byron Joe
return EXIT_SUCCESS;
}
Les conteneurs d'association sont très performants lors de la recherche par clé.
Temps d'accès à un élément : O(log n)
Temps d'insertion/retrait d'un élément : O(log n)
std::multimap
#include <map>
Le std::multimap est pratiquement identique au std::map au détail près qu'on peut stocker plusieurs fois la même clé.
Exemple 11: Démonstration de recherche dans un std::multimap de tous les éléments d'une même clé
int main()
{
multimap<unsigned int, string> studentsByAge {
{12, "Joe Blow"},
{13, "Jane Doe"},
{12, "Aaron Black"}
};
const int AGETOFIND { 12 };
auto iter = studentsByAge.find(AGETOFIND); cout << "Voici la liste de tous les étudiants de 12 ans:" << '\n';
while(iter != studentsByAge.end() &&
iter->first == AGETOFIND) {
cout << iter->second << '\n';
iter++;
}
return EXIT_SUCCESS;
}
//Output:
//Joe Blow
//Aaron Black
Temps d'accès à un élément : O(log n)
Temps d'insertion/retrait d'un élément : O(log n)
std::set
#include <set>
Le std::set est également un conteneur d'association, mais il contient seulement une clé et non une clé et une valeur comme le std::map. Dans l'exemple ci-dessous, nous allons simuler un tirage de 6 numéros au hasard entre 1 et 49 à l'aide d'un set.
Exemple 12: Démonstration de l'utilisation d'un std::set
int main()
{
set<int> randomNumbers;
srand(static_cast<unsigned int>(time(nullptr)));
while(randomNumbers.size() != 6) {
//Choose a random number between 1 and 49
auto number = rand() % 49 + 1;
if (randomNumbers.find(number) == randomNumbers.end()) {
randomNumbers.emplace(number);
}
}
for(const auto number : randomNumbers) {
cout << number << " ";
}
cout << '\n';
return EXIT_SUCCESS;
}
//Output example:
//2 10 17 24 34 40
Temps d'accès à un élément : O(log n)
Temps d'insertion/retrait d'un élément : O(log n)
std::multiset
#include <set>
Le std::multiset est pratiquement identique au std::set au détail près qu'on peut stocker plusieurs fois la même clé.
Temps d'accès à un élément : O(log n)
Temps d'insertion/retrait d'un élément : O(log n)
std::unordered_map, std::unordered_multimap, std::unordered_set et std::unordered_multiset
#include <unordered_map> et #include <unordered_set>
Il est important de choisir une bonne fonction de hachage afin de ne pas causer trop de collisions sinon on perd vraiment l'avantage des tables de hachage.
Exemple 13: Démonstration de l'utilisation d'un std::unordered_set en utilisation une fonction de hachage disponible dans la bibliothèque standard. La fonction de hachage calculera la position en fonction du prénom et nom de l'étudiant.
class Student {
public:
Student(string firstName, string lastName)
: firstName(firstName), lastName(lastName) {}
bool operator==(const Student& rhs) const
{
return this->firstName == rhs.firstName &&
this->lastName == rhs.lastName;
}
const string &getFirstName() const { return firstName; }
const string &getLastName() const { return lastName; }
private:
string firstName;
string lastName;
};
class StudentHash
{
public:
size_t operator()(const Student &item) const
{
static hash<string> hashFunction;
return hashFunction(item.getFirstName() + item.getLastName());
}
};
int main()
{
unordered_set<Student, StudentHash> students;
students.emplace("Joe", "Blow");
students.emplace("Jane", "Doe");
students.emplace("Aaron", "Black");
for(const auto &student : students) {
cout << student.getFirstName() << " " << student.getLastName() << '\n';
}
return EXIT_SUCCESS;
}
Temps d'accès à un élément : O(1) à O(n)
Temps d'insertion/retrait d'un élément : O(1) à O(n)
std::stack
#include <stack>
Le std::stack est un conteneur qui permet d'ajouter des éléments sur une pile et de les dépiler dans l'ordre inverse où ils ont été ajoutés. C'est une structure de données LIFO (last-in, first-out). Un exemple vaut mille mots.
Exemple 14: Démonstration de l'utilisation d'une std::stack
int main()
{
stack<int> myNumbers;
//On empiles les nombres 1, 2, 3, 4 et 5 dans l'ordre.
for(int i=1; i<=5; i++) {
myNumbers.emplace(i);
}
//On dépile!
while(!myNumbers.empty()) {
cout << myNumbers.top() << '\n';
myNumbers.pop();
}
return EXIT_SUCCESS;
}
//Output:
//5
//4
//3
//2
//1
La méthode top() retourne l'élément sur le dessus de la pile tandis que la méthode pop() retire ce même élément de la pile.
Temps d'ajout/retrait d'un élément : O(1)
std::queue
#include <queue>
Le std::queue est un conteneur qui permet d'ajouter des éléments dans une file et de les retirer dans l'ordre où ils ont été ajoutés. C'est une structure de données FIFO (first-in, first-out). Reprenons l'exemple du std::stack mais en utilisant une std::queue.
Exemple 15: Démonstration de l'utilisation d'une std::queue
int main()
{
queue<int> myNumbers;
//On empiles les nombres 1, 2, 3, 4 et 5 dans l'ordre.
for(int i=1; i<=5; i++) {
myNumbers.emplace(i);
}
//On dépile!
while(!myNumbers.empty()) {
cout << myNumbers.front() << '\n';
myNumbers.pop();
}
return EXIT_SUCCESS;
}
//Output:
//1
//2
//3
//4
//5
Temps d'ajout/retrait d'un élément : O(1)
std::priority_queue
#include <queue>
Le std::priority_queue est un conteneur place les éléments ajoutés selon la fonction de comparaison sélectionnée. Par défaut, si on ne spécifie aucune fonction de comparaison, les valeurs seront triées selon la fonction de comparaison
std::greater ce qui placera la plus petite valeur en première position.
Exemple 16: Démonstration de l'utilisation d'une std::priority_queue avec la fonction de comparaison
less.
int main()
{
priority_queue<int, vector<int>, less<int>> myNumbers;
for(int i : {12, 47, 55, 24, 36}) {
myNumbers.emplace(i);
}
//On vide la file
while(!myNumbers.empty()) {
cout << myNumbers.top() << '\n';
myNumbers.pop();
}
return EXIT_SUCCESS;
}
//Output:
//55
//47
//36
//24
//12
Temps d'accès à un élément : O(1)
Temps d'insertion/retrait d'un élément : O(log n)
std::deque
#include <deque>
Le std::deque est une file qui peut grandir dans les 2 directions. Elle a l'avantage d'offrir des performances O(1) à l'insertion/suppression à ses 2 extrémités et un temps d'accès d'O(1) à ses éléments. Les éléments du deque ne sont pas nécessairement stockés de façon contiguë en mémoire, mais sont plutôt stockés sous forme de segments contigus de taille fixe.
Dû à la gestion de ces différents segments de mémoire, le deque a le désavantage d'avoir une plus grande empreinte mémoire.
Temps d'accès à un élément : O(1)
Temps d'insertion/retrait d'un élément (tête et queue) : O(1)
Temps d'insertion/retrait d'un élément (intérieur du deque) : O(n)
Conclusion
En conclusion, il est important de bien comprendre les différents conteneurs avant de faire son choix. Chaque conteneur a ses avantages et ses désavantages. Plusieurs points sont à prendre en considération :
- Est-ce que la taille du conteneur sera fixe ou variable?
- Est-ce que l'ordre des éléments est important?
- Quel sera le moyen d'accéder aux éléments? Par leur position? Par leur clé?
- Quel sera le taux d'accès versus le taux d'insertion/suppression? Grande fréquence de modification?
- Les insertions/suppressions se feront au début, à la fin ou ailleurs dans le conteneur?
En espérant que cet article vous aide à faire les bons choix de conteneur dans vos prochains projets. :)
