Array, vector & map

Array

Rôle

Un std::array contient un nombre fixe d’éléments de même type.

Pourquoi utiliser un std::array plutôt qu’un tableau (int T[10]) :

Les arrays sont des objets, ils peuvent donc être passés par copie ou par référence.

La fonction membre at(i) permet de vérifier la validité de l’indice avant d’accéder au i-ème élément.

Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche…

Pour instancier un array, vous devez :

Ecrire une directive #include <array> en début de programme

En l’absence de : using namespace std, vous devez écrire std::array

Présentation rapide

Opérations sur les arrays
Type	Exemple
Initialisation	array<int, 3> a = {1, 2, 3};
Initialisation	array<int, 3> a {1, 2, 3};
Initialisation	array<int, 3> a({1, 2, 3});
Initialisation	array<int, 3> a = {};	Avec initialisation des valeurs : les numériques sont mis à zéro !
Initialisation	array<int, 3> a;	Sans initialisation
Méthode	a.fill(value)	Initialise tous les éléments à la valeur donnée
Méthode	a.at(i)	Retourne une référence vers le i-ème élément AVEC bound-checking
Méthode	a[i]	Retourne une référence vers le i-ème élément SANS bound-checking
Méthode	a.size()	Retourne le nombre d’éléments
Méthode	a.swap(b)	Permute les éléments des deux arrays

Quizzz

La fonction length retourne le nombre d’éléments.
La syntaxe at(i) ou [i] sont identiques en tout point.
La syntaxe : array<int, 3> a {1, 2, 3}; est valide.
Il est possible d’instancier un array sans initialiser ses valeurs.
Quel est le nom de la fonction initialisant l’ensemble des éléments à une valeur donnée.

Vector

Rôle

Un std::vector représente une liste de taille dynamique d’éléments de même type.

Pourquoi utiliser un std::vector :

Classe modèle pouvant s’adapter à tout type.

Les vectors sont des objets, ils peuvent donc être passés par copie ou par référence.

Pas de limite de taille.

Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche…

La fonction membre at(i) permet de vérifier la validité de l’indice avant d’accéder au i-ème élément

Gestion automatisée de la mémoire : allocation, libération.

Présentation rapide

Pour instancier un objet vector, vous devez :

Mettre une directive #include <vector> en début de programme

En l’absence de : using namespace std, vous devez écrire std::array

Opérations sur les vectors
Type	Exemple
Initialisation	vector<int> L;	Vector vide ; pas d’éléments dans la liste
Initialisation	vector<int> L = {};	Idem
Initialisation	vector<int> L = {1,2,3,4};
Initialisation	vector<int> L( {1,2,3,4} )
Initialisation	vector<int> L( );	Confusion => Déclaration d’une fonction retournant un vector
Initialisation	vector<int> v1(10);	Taille fixée à 10 éléments + INITIALISATION à zéro
Initialisation	vector<int> v1(10,5);	Taille fixée à 10 éléments initialisés à la valeur 5
Initialisation	vector<int> v2(v1);	Initialisation par copie
Méthode	L.at(i)	Retourne une référence vers le i-ème élément AVEC bound-checking
Méthode	L[i]	Retourne une référence vers le i-ème élément SANS bound-checking
Méthode	L.size()	Retourne le nombre d’éléments
Méthode	L.empty()	Indique si la liste est vide
Méthode	L.clear()	Retire et détruit tous les éléments de la liste
Méthode	L.resize(n)	Force le nombre d’éléments à n
Méthode	L.push_back(v)	Insère une copie de l’élément v en fin de liste
Méthode	L.pop_back()	Retire et détruit le dernier élément de la liste
Méthode	L.back()	Retourne une référence vers le dernier élément de la liste
Méthode	L.erase(iter)	Supprime l’élément désigné par l’itérateur iter
Méthode	L.insert(iter,v)	Insère une copie de l’élément v à la position désignée par l’itérateur iter

Avertissement

Tous les éléments dans une liste de type vector sont de même type. Ainsi, si vous stockez un double dans une liste de type vector<int>, alors il sera implicitement converti en entier.

La fonction resize(n) fixe le nombre d’éléments :

Si n < size() alors les derniers éléments sont détruits.

Si n = size() aucun effet.

Si n > size() il y a création de nouveaux éléments par appel au constructeur par défaut.

Note

Certaines méthodes des vectors portent des noms similaires ce qui prête à confusion. On pense ici aux fonctions membres resize() et reserve() ainsi que size() et capacity(). Une clarification s’impose ! Un objet vector alloue une zone mémoire servant de buffer. La mécanique interne du vector fait en sorte que la taille de ce buffer soit supérieure au nombre d’éléments stockés. La méthode reserve() permet de fixer la taille de ce buffer et capacity() retourne sa taille. Par exemple, si vous savez que 10 000 000 d’éléments vont être stockés, alors, il peut être utile de fixer directement la taille du buffer à cette grandeur ce qui évite de multiples redimensionnements et permet de gagner en efficacité. Ainsi, Ces deux fonctions permettent une optimisation fine des objets vector.

Quizzz

La fonction pop_back insère un élément en fin.
La syntaxe at(i) ou [i] sont identiques en tout point.
La fonction size retourne le nombre d’éléments.
La syntaxe : vector<int> v(10); crée une liste et initialise ses éléments à la valeur 10.
Quel est le nom de la fonction initialisant l’ensemble des éléments à une valeur donnée ?
Quel est le nom de la fonction retirant tous les éléments ?
Quel est le nom de la fonction indiquant si la liste est vide ?
Quel est le nom de la fonction permettant de fixer le nombre d’éléments dans la liste.

Map

Un std::map représente un dictionnaire permettant d’associer une valeur (value) à une clé (key) pouvant être un entier comme un string !

Note

Si les dictionnaires sont si souples et si pratiques, pourquoi ne pas utiliser que des dictionnaires ? Oui cette question peut être posée ! En fait ils sont plus souples, mais chaque opération sur un dictionnaire est plus longue que sur un vector, il y a donc un surcoût à cette souplesse.

Présentation rapide

Opérations sur les maps
Type	Exemple
Initialisation	map<string,int> m = { {"one",1}, {"two",2} };
Affectation	m["trois"] = 3;	Associe la valeur 3 à la clé "trois"
Opérateur[]	cout << m["deux"]	Retourne la valeur associée à la clé "deux"
Méthode	m.count(key) > 0	Teste si la clé existe dans ce dictionnaire
Méthode	m.erase("trois")	Supprime la paire clé/valeur correspondant à la clé "trois"
Méthode	m.size()	Nombre de paires clé/valeur dans le dictionnaire

Parcours

Avertissement

Les présentations ci-dessous sont valables pour un array comme pour un vector

En mode read-only

#include <iostream>
#include <array>

int main()
{
        std::array<int, 3> a = {1, 2, 3};
        for (int v : a)  std::cout << v << " ";
        for (int v : a)  v = 4;  // attention v est une variable locale
        for (int v : a)  std::cout << v << " ";
}

>> 1 2 3
>> 1 2 3

En mode read-write

#include <iostream>
#include <array>

int main()
{
        std::array<int, 3> a = {1, 2, 3};
        for (int v  : a)  std::cout << v << " ";
        for (int &v : a)  v = 4;  // cette fois v est une référence
        for (int v  : a)  std::cout << v << " ";
}

>> 1 2 3
>> 4 4 4

Avertissement

Un vector ne peut gérer le retrait ou l’ajout d’élément durant un parcours.

Map

Pour les dictionnaires, il y a une légère différence car la boucle for retourne un objet dont :

La variable first correspond à la clé

La variable second correspond à la valeur

#include <iostream>
#include <map>
using namespace std;

int main()
{
        map<string,int> myMap = {{"one",1}, {"two",2}, {"three",3}};

        for ( auto couple : myMap)
                cout << couple.first << " => " << couple.second << endl;
}

>> one => 1
>> three => 3
>> two => 2

Les itérateurs

Présentation

Avertissement

Les présentations ci-dessous sont valables pour un array comme pour un vector

La norme de la STL n’impose aucun choix d’implémentation. Elle décrit juste les fonctions membres et éventuellement impose leur complexité : temps constant, logarithmique ou linéaire amortie. Ainsi, les containers de la STL peuvent aussi bien utiliser en interne des indices ou des adresses pour classer leurs données. De plus, il ne faut pas oublier qu’il existe plusieurs implémentations de la STL qui peuvent entraîner des choix d’implémentation différents :

libstdc++ : fournie avec GCC et utilisée pour sa large compatibilité avec différentes architectures.
LLVM libc++ : fournie avec Clang et conçue pour être légère.
Microsoft STL : fournie avec Microsoft Visual Studio et optimisée pour les systèmes Windows.
STL personnalisée : certaines entreprises créent leurs propres versions ou modifications de la STL pour répondre à des besoins spécifiques.

Il a donc fallu choisir une abstraction pour fournir une syntaxe indépendante de l’implémentation choisie pour le container. L’abstraction mise en place s’appelle un itérateur (iterator). Ce choix est judicieux, mais la syntaxe des itérateurs peut parfois donner des cheveux blancs. On aime ou on aime pas, mais, c’est le choix de la STL et on doit savoir travailler avec.

Les itérateurs remplacent ainsi les indices, il faut éviter d’utiliser la valeur 0 ou le paramètre size() :

begin() : retourne un itérateur positionné sur le premier élément.

end() : retourne un itérateur positionné a fin du container : un élément fictif placé après le dernier élément.

*it : avec it un itérateur ; retourne une référence vers l’élément désigné par cet itérateur.

#include <iostream>
#include <array>

int main()
{
        std::array<int, 5> arr = {1, 2, 3, 4, 5};

        std::cout << *arr.begin() << std::endl;   // affiche le premier élément
        *arr.begin() = 9;                         // modifie le premier élément
        for(int v : arr) std::cout << v << " ";   // affiche la liste
}

>> 1
>> 9 2 3 4 5

Note

Un itérateur permet un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator ainsi que les méthodes cbegin() et cend().

Le mot-clef auto

Le type des itérateurs est assez long à écrire : array<T, N>::iterator, pour cela, on préfère utiliser le mot-clef auto qui force le langage a déduire automatiquement le type.

#include <iostream>
#include <array>

int main()
{
        std::array<int, 5> arr = {1, 2, 3, 4, 5};
        auto it = arr.begin();
}

Exemple avec les vectors

Il existe une arithmétique sur les itérateur. Ainsi l’expression begin()+1 désigne un itérateur associé au deuxième élément de la liste. Voici quelques exemples :

#include <iostream>
#include <vector>
using namespace std;

int main()
{
        vector<int>  L = {2,3,4};
        for (int v : L) cout << v << endl;

        L.erase(L.begin()+1);  // supprimme le 2ième élément
        for (int v : L) cout << v << endl;

        L.insert(L.begin()+1,8); // insére 8 à la deuxième place
        for (int v : L) cout << v << endl;
}
>> 2 3 4
>> 2 4                  // L.erase(L.begin()+1);
>> 2 8 4                // L.insert(L.begin()+1,8);

Les algorithmes

Avertissement

Les présentations ci-dessous sont valables pour un array comme pour un vector

Exemples

Voici quelques exemples des algorithmes fournis dans la STL :

#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

int main()
{
        array<int, 10> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

        // FIND
        auto it = find(arr.begin(), arr.end(),9);
        *it = 0;
        for (int v : arr) cout << v << " ";
        cout << endl;

        // SORT
        sort(arr.begin(), arr.end());
        for (int v : arr) cout << v << " ";
        cout << endl;

        // REVERSE
        reverse(arr.begin(), arr.end());
        for (int v : arr) cout << v << " ";
        cout << endl;
}

>> 3 1 4 1 5 0 2 6 5 3  FIND
>> 0 1 1 2 3 3 4 5 5 6  SORT
>> 6 5 5 4 3 3 2 1 1 0  REVERSE

Note

Un effort de simplification a été fait dans ce cours relativement aux syntaxes présentées pour les itérateurs. Cependant, lorsque vous trouverez des informations sur internet, certains auteurs pourront fournir un code beaucoup plus difficile à lire, il faut le savoir.