Une grande partie des tâches en programmation se ramène à stocker des ensembles de données et à les traiter. Le conteneur le plus couramment utilisés est le tableau. Cependant d'autres conteneurs peuvent être choisis en fonction de l'utilisation et des performances souhaitées. L'acccès à un élément donné est très efficace, mais l'insertion ou la suppression ne le sont pas du tout. Si ces deux opérations sont prépondérantes, on pourra par exemple utiliser des listes chaînées.

La bibliothèque standard du C++ propose plusieurs types de conteneurs génériques (ils peuvent contenir n'importe quel type de données), et qui présentent tous une interface similaire. On touve notamment :

• vector : performances et utilisation comparable à un tableau,
• list : liste chaînée,
• map : tableau associatif.

Pour utiliser un conteneur, il faut pouvoir le parcourir et accéder à ses éléments. Cette notion mène au concept d'itérateur. Un itérateur est un petit objet qui va indiquer une position dans un conteneur et permettre d'accéder à l'élément présent à cette position. Un itérateur peut également se déplacer dans un conteneur. Vous connaissez déjà un itérateur : le pointeur.

float tab[10];
for(float* it = tab; it != tab+10; ++it)
{
    *it = rand();
}

Dans ce programme, le pointeur it indique la position courante, l'opération ++it permet de passer à l'élément suivant, et l'opération *it permet d'accéder à l'élément pointé.

Les itérateurs de la bibliothèque standard ont conservé l'interface des pointeurs. Chaque conteneur possède un itérateur, défini comme un type imbriqué : l'itérateur sur un std::vector<int> est de type std::vector<int>::iterator. De façon similaire, un itérateur sur une std::list<float> est de type std::list<float>::iterator.

Les conteneurs peuvent fournir des itérateurs positionnés au début du conteneur grâce à la fonction membre begin, et des itérateurs positionnés à la fin (juste après le dernier élément) grâce à la fonction membre end. Le parcours d'une liste se fera alors de la façon suivante :

std::list<float> l;
// ...
for(std::list<float>::iterator it = l.begin(); it != l.end(); ++it)
{
    *it = rand();
}

Exercices

La fonction insert de la classe std::vector permet d'insérer une valeur dans un std::vector. Combien d'opérations en moyenne sont nécessaires pour insérer un élément dans un vecteur de taille n ? Même question pour la classe std::list qui est une liste doublement chaînée. Quelle conclusion pouvez-vous en tirer ?

La documentation de la classe std::vector inclut la fonction membre suivante :

• iterator insert(iterator pos, const T &x) : insère la valeur x avant pos.

Comment insérer une valeur à la troisème place d'un vecteur ?

On dispose d'un std::vector<float> nommé v et d'une std::list<float> nommée l. écrivez le code nécessaire pour échanger les éléments de v et de l. Quelles sont les préconditions pour que votre code fonctionne correctement ?

La fonction std::copy a le prototype suivant :

template<typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);

Copiez v dans l à l'aide de cette fonction.

La fonction std::sort à le prototype suivant :

template<typename RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

Triez le vecteur v à l'aide de cette fonction, et affichez le vecteur trié.

Un std::map est un conteneur associatif : il permet d'avoir un tableau indexé par un type non entier, par exemple par une chaine de caractères :

std::map<std::string, int> ages;
ages["alain"]=20;
ages["bernard"]=25;

De plus, les éléments d'un map sont stockés triés. En interne le map utilise une structure de type arborescente semblable à celle que nous avons vu en TD. La seule restriction sur l'index est qu'il doit être comparable : l'opérateur < doit être redéfini pour ce type.

Chaque élément d'un map est une paire (std::pair) dont le premier élément est la clef servant à indexer (ici un string) et le deuxième élément est la valeur (ici un int). Donc si it est un itérateur sur un map, it→first sera la clef de l'élément et it→second sera sa valeur.

Écrivez un programme qui copie les clefs et les valeurs d'un std::map<std::string, int> dans deux std::vector.