4/9

4. STL

La bibliothèque standard C++ appelée STL (Standard Template Library) propose un ensemble de conteneurs (objet contenant d’autres objets: ex. liste, dictionnaire, etc.) et algorithmes génériques. L’aspect générique étant apporté par l’utilisation de template (Type générique s’adaptant automatiquement au moment de la compilation).

Exemple d’utilisation de conteneurs de la STL

#include <vector>
#include <array>
#include <map>
#include <string>
#include <iostream>


int main()
{
    std::vector<int> v = {7,8,5,1}; // Déclaration d'un vecteur de valeurs entières
    v.push_back(9);  // Ajout d'un élément en fin de vecteur, v contient [7,8,5,1,9]
    v[1]=-2;         // Accès et écriture sur une valeur, v contient maintenant [7,-2,5,1,9]


    // Affichage de l'intégralité du vecteur
    for(size_t k=0; k<v.size(); ++k)
        std::cout << v[k] << std::endl;


    // Autre approche permettant de boucler sur les éléments du vecteur
    for(int element : v)
        std::cout << element << std::endl;


    // Autre type de vecteur  de 4 nombres flottants (taille connu (et fixe) à la compilation)
    std::array<float,4> a = {-2.1f, 1.5f, 0.0f, 6.1f};
    a[1] = a[0]+8;
    std::cout << a[1] << std::endl;


    // Dictionnaire dont la clé est un mot/phrase (string), et la valeur est un nombre flottant
    std::map<std::string, float> dictionary= { {"pizza",9.5}, {"kebab",8.25} };
    dictionary["hamburger"] = 11.5; // Ajout d'une nouvelle entrée dans le dictionnaire
    dictionary["kebab"] += 2;       // Modification d'une valeur existante
    std::cout<< dictionary["kebab"] << std::endl; // Affiche le prix du kebab


    return 0;
}

Remarque sur la syntaxe:

  • std::vector<int>

    • std::vector correspond au nom du conteneur: ici un tableau de valeurs.

    • <int> correspond au paramètre template, c’est-à-dire le type de données que va contenir le std::vector. Ce type doit être connu au moment de la compilation.

De la même manière, on trouve std::map<type_clé, type_valeur> possèdant deux paramètres template, respectivement, le type de la clé et le type de la valeur.

Principe général des conteneurs de la STL

Tous les conteneurs de la STL sont définis dans l’objectif d’être générique, cohérent entre eux, et efficace sur le plan algorithmique.

  • Les éléments d’un conteneur sont des types templates, c’est-à-dire qu’ils peuvent contenir n’importe quel type à partir du moment où celui-ci est connu au moment de la compilation. (à l’inverse du typage dynamique (ex. Python), cette contrainte permet au compilateur d’implémenter spécifiquement le conteneur en fonction du type contenu, et d’obtenir une exécution sans aucun cout de calcul supplémentaire.)

  • Tous les éléments du conteneur peuvent être accédés de manière identique à partir de la notion d'iterateurs.

  • Les méthodes proposées par défaut sur un conteneur sont limitées aux algorithmes efficaces sur celui-ci (ex. pas d’ajout en tête sur un vecteur d’éléments, mais possible par défaut sur une liste chainée).

Itérateurs

Les itérateurs sont des objets définis par la STL permettant de désigner et d’accéder à un élément du conteneur, ainsi que d’itérer sur les éléments suivants.

Tous les itérateurs (it) implémentent les deux propriétés suivantes

  • *it permet d’accéder à la valeur de l’élément désigné

  • ++it permet d’accéder à l’itérateur désignant l’élément suivant

Rem. Les itérateurs ont été définis pour être compatibles avec la syntaxe des pointeurs. Ils peuvent être vus comme une généralisation des pointeurs pour des conteneurs qui ne sont pas que des tableaux contigus en mémoire.

En fonction du conteneur, certains itérateurs possèdent plus de possibilités tels que --it permettant d’aller sur l’élément précédent, it+=k permettant d’avancer k fois en avant dans le conteneur (en un seul coup).

Supposons une instance c d’un conteneur de type C

  • C::iterator corresponds au type de l’itérateur

  • c.begin() renvoie l’itérateur désignant le premier élément du conteneur

  • c.end() renvoie l’itérateur pointant après le dernier élément du conteneur (la valeur désignée par c.end() n’appartient plus au conteneur et ne devrait pas être accédée).

Exemple d’utilisation d’itérateurs pour naviguer au travers d’un conteneur (valide pour tout type de conteneur de la STL)

// iterator on the first element of c
C::iterator it     = c.begin();
// iterator following the last element of c
C::iterator it_end = c.end();


// loop over all elements
while( it != it_end )
{
   ... // get value using *it
   ++it; // iterate over the next element
}

Ou, de manière plus concise en une seule ligne

for( C::iterator it=C.begin(), it_end=C.end(); it != it_end; ++it )
{
  ... // use *it within the loop
}

Ou encore, en utilisant la syntaxe for-range utilisant de manière implicite les itérateurs

for( type& element : C )
{
  ... // use directly element
}

(voir partie suivante pour la syntaxe type& indiquant une référence).

Const_iterator

Tout comme pour les variables classiques, les itérateurs ont un comportement mutable par défaut, c-a-d que la valeur de l’élément désigné par *it peut être modifié.

Dans le cas où l’on souhaite uniquement accéder en lecture, et non en écriture, sur les éléments, il est possible d’utiliser des const_iterator qui empêchent l’écriture involontaire au niveau de la compilation.

La syntaxe correspondant aux const_iterator est la suivante:

  • C::const_iterator correspond au type

  • c.cbegin() renvoie un const_iterator sur le premier élément du conteneur

  • c.cend() renvoie un const_iterator pointant après le denier élément du conteneur

Notez qu’il est toujours possible d’itérer (ex. ++it) sur un const_iterator, seul la valeur désignée ne peut pas être modifiée. En particulier, ne pas confondre

  • const C::iterator it; : iterateur dont la valeur désignée (*it) peut être modifié, mais ne peut pas être itéré (ex. ++it n’est pas possible)

  • C::const_iterator it; : itérateur dont la valeur pointée (*it) n’est pas modifiable, mais qui peut être itéré (++it est valide).

De manière générale, une bonne pratique consiste à utiliser par défaut des const_iterator, sauf dans le cas où vous souhaitez explicitement modifier les valeurs pointées.

Conteneurs principaux

Vector

std::vector correspond à un tableau dont la taille peut s’adapter dynamiquement. Il s’agit de la structure basique que nous allons utiliser pour stocker des buffers de données de grande taille.

Les std::vector possèdent les propriétés suivantes

  • Les éléments sont placés de manière contigüe en mémoire (important pour les buffers de données en OpenGL)

    • Compatible avec les pointeurs C

    • Accès rapide à n’importe quel élément du conteneur en O(1).

  • Les éléments sont placés dans la mémoire du tas (heap memory)

    • Allocation et désallocation des données gérée automatiquement par le conteneur (resize et ajout d’élément en fin).

    • Les vecteurs peuvent stocker de grandes quantités de données (tant que vous avez de la mémoire RAM)

  • Les éléments peuvent être ajoutés efficacement en fin de vecteur

    • Généralement en O(1), et au pire de manière exceptionnelle en O(N)

Rem. Les std::vector remplacent les tableaux dynamiques alloués manuellement que l’on pouvait rencontrer autrefois (en utilisant malloc ou new) de manière plus robuste et sécurisée tout en étant aussi efficace.

Array

std::array correspond à un tableau dont la taille est fixe (et connue à la compilation).

Les std::array possèdent les propriétés suivantes

  • Les éléments sont stockés de manière contigüe en mémoire

  • Les éléments sont placés sur la pile (stack memory).

    • Création et accès très rapide.

    • Limité en taille (quelques Mo) dans la limite de la pile allouée par l’OS

  • La taille du tableau doit être connue à la compilation

Rem. Les std::array remplacent de manière plus sécurisée les tableaux C statiques T[N], sans ajouter de surcout en temps d’exécution.

Dictionnaires

std::map correspond à un dictionnaire stockant une paire clé/valeur. Chaque clé doit être unique. Les map peuvent être utilisées en tant que conteneur associatif entre une clé et une valeur.

Les std::map possèdent les propriétés suivantes

  • Chaque élément est trié par sa clé en utilisant l’opérateur <

  • La recherche, l’ajout et la suppression d’élément dans le conteneur (à partir de la clé) est en O(log(N))

Autres conteneurs

Il sera possible également de rencontrer d’autres conteneurs de la STL tels que les listes chainées (std::list), dictionnaires à entrées multiples (std::multimap), les piles (std::stack), files (std::queue), files à priorités (std::priority_queue), ensemble de valeurs uniques triés (std::set), table de hachage (std::unordered_map, et std::unordered_multimap), etc.

String

La STL propose également l’objet std::string permettant de gérer aisément des chaines de caractères. Les std::string peuvent être déclarés en prenant du texte écrit entre guillemets

std::string ma_phrase = "Initialisation d'une std::string";

L’opérateur = entre deux std::string réalise la copie de l’une sur l’autre. L’opérateur + entre deux std::string réalise la concaténation de leur contenu.

std::string word_1 = "Hello ";
std::string word_2 = "world";
std::string full_sentance = word_1+word_2;

Rem. Un texte écrit entre guillemets correspond, par compatibilité avec le C, à un tableau statique C contenant une suite de char. Ces tableaux sont gérés sous forme de pointeur, et il est généralement conseillé de passer sous la forme d’une std::string lorsque vous souhaitez manipuler ces chaines de caractères. En particulier, dans ce cas, la syntaxe "Hello "+"world" ne serait pas valide.

Remarque sur l’utilisation de la STL

Notons qu’au début du langage C++ , la STL était limitée et pas toujours disponible. Ainsi de nombreuses implémentations de conteneurs et algorithmes ont été définies et peuvent être trouvées sur internet.

Aujourd’hui la STL est largement disponible, implémentée de manière efficace, et couvre les principaux besoins de structures de données (vecteurs, listes chainées, dictionnaires, table de hachage, etc.) Il est ainsi fortement recommandé d’utiliser de manière privilégiée la STL avant d’utiliser des bibliothèques tierces, ou de refaire soit même des conteneurs basiques.

Exercice

  • Créez une fonction calculant la norme d’un vecteur de type std::array contenant 3 flottants (std::array<float,3>)

Cette fois, l’appel à cette fonction pourra être sous la forme suivante

std::array<float,3> v = {1.0f, 1.0f, 1.0f};
float n = norm(v);
std::cout<< n <<std::endl; // devrait afficher ~1.7321