Tableaux dynamiques

Vous apprendrez ici à utiliser des vector de manière un peu plus avancée : construction, accès, insertions, suppressions et recherches n’auront plus de secrets pour vous !

Pour cet exercice, vous modifierez le fichier :
- chap-05/1-vectors.cpp

La cible à compiler est c5-1-vectors.

Construction

Au chapitre précédent, nous vous avions présenté différentes syntaxes permettant d’instancier une classe. Nous vous avions en particulier indiquer qu’il était possible d’utiliser la syntaxe Class c { p1, p2 }; ou bien la syntaxe Class c(p1, p2);.

Eh bien dans le cas des vector, des array et de la plupart des autres conteneurs, ces deux syntaxes n’auront pas le même effet et nous allons voir la différence ici.

Instanciez un vector<int> en lui passant les paramètres 4 et 0 avec {}. Parcourez ensuite ce tableau à l’aide d’une boucle foreach et affichez son contenu. Remplacez ensuite les {} dans l’instanciation par (). Que constatez-vous ?

//std::vector<int> values { 4, 0 };
std::vector<int> values(4, 0);

for (const auto v: values)
{
    std::cout << v << std::endl;
}

Allez sur la page de documentation des constructeurs de la classe vector.
En lisant les descriptions de chaque surcharge, essayez d’identifier celles que vous avez appelées en utilisant (4, 0) et { 4, 0 }.

Vous allez maintenant utiliser un nouveau constructeur, qui vous permettra de convertir un tableau primitif en un vector.
Il s’agit de la surcharge n° 5 : le constructeur attend deux paramètres first et last, qui correspondent aux itérateurs de début et fin d’un autre conteneur.

Commencez par instancier un tableau primitif avec les valeurs { 0, 1, 2, 3, 4, 5 }.
Les itérateurs d’un tableau primitif sont en fait les pointeurs sur chacune de ses cases :

int  array[] = { 0, 4, 3 };
int* iterator_on_2nd_element = &array[1];

Construisez maintenant un vector en lui fournissant des itérateurs de votre tableau primitif.
Essayez dans un premier temps d’avoir dans votre vector les valeurs { 2, 3, 4 }, puis essayez ensuite d’obtenir le tableau complet.

int array[] = { 0, 1, 2, 3, 4, 5 };

std::vector<int> part(&array[2], &array[5]);
for (const auto v: part)
{
    std::cout << v << std::endl;
}

std::vector<int> full(array, array + 6);
for (const auto v: part)
{
    std::cout << v << std::endl;
}

Accès aux éléments

Pour accéder à un élément précis d’un tableau, on peut utiliser array[idx], comme sur un tableau primitif :

std::vector<int> values { 1, 2, 3 };
std::cout << "2nd element is " << v[1] << std::endl;

v[2] = 8;
std::cout << "Last element has changed to " << v[2] << std::endl;

Utilisez une boucle for (et pas foreach) de manière à inverser l’ordre des éléments du tableau de la question précédente.
Afin d’itérer sur le vector, vous devrez récupérer sa taille. Quelle fonction faut-il utiliser pour ça ?
Sachez également que vous aurez probablement besoin d’utiliser la fonction std::swap.

std::vector<int> full(array, array + 6);
for (size_t left = 0, right = full.size() - 1; left < right; ++left, --right)
{
    std::swap(full[left], full[right]);
}

Insertions

Vous avez déjà vu que l’on pouvait ajouter des éléments à la fin d’un vector avec les fonctions emplace_back ou push_back.

Qu’en est-il si vous souhaitez insérer des éléments en plein milieu de ce tableau ?
Essayez de trouver dans la documentation les deux fonctions permettant d’ajouter des éléments n’importe où dans un vector. Quelle est la différence entre ces deux fonctions ?

Vous ne l’avez peut-être pas remarqué, mais ces fonctions attendent un itérateur, et non un indice, pour indiquer où insérer le nouvel élément.
Pour obtenir un itérateur sur le début d’un vector, il faut utiliser la fonction begin(), pour obtenir l’itérateur de fin, il faut utiliser end(), et pour incrémenter l’itérateur, vous pouvez utiliser ++it ou it += step. Enfin, si vous voulez récupérer l’élément pointé, vous pouvez écrire *it :

// Display the content of values.
for (auto it = values.begin(); it != values.end(); ++it)
{
    std::cout << *it << std::endl;
}

En utilisant une fonction d’insertion, faites en sorte de dupliquer chacun des éléments de votre tableau. Par exemple, { 1, 2, 3 } devrait devenir { 1, 1, 2, 2, 3, 3 }.
Prenez garde à l’invalidation des itérateurs !

for (auto it = full.begin(); it != full.end(); it += 2)
{
    it = full.insert(it, *it);
}

Suppressions

Vous allez maintenant apprendre à supprimer des éléments d’un vector.

La fonction la plus simple à utiliser est celle permettant de retirer le dernier élément du tableau.
Cherchez de quelle fonction il s’agit, et utilisez-la sur votre tableau à l’intérieur d’une boucle while jusqu’à ce que celui-ci soit vide.
Quelle fonction allez-vous utiliser dans la condition du while pour savoir si le tableau est vide ?

while (!full.empty())
{
    full.pop_back();
}

Ca, c’était la partie façile. Pour supprimer des éléments à une position bien particulière, c’est un tout petit peu plus compliqué.
Pour cela, il faut utiliser la fonction erase. A priori, on pourrait penser que l’on peut écrire v.erase(3) pour supprimer le 3e élément du tableau, sauf que cela ne va pas marcher.
Consultez la documentation pour comprendre ce qui ne va pas et trouvez-y ce qu’il faut écrire à la place.

v.erase(v.begin() + 3);

Utilisez maintenant erase pour supprimer les éléments allant de l’indice 2 à l’indice 6 inclus d’un tableau contenant initialement { 0, 1, ..., 10 }.
Faites le nécessaire pour que erase ne soit appelé qu’une seule fois par votre programme (=> pas le droit de faire de boucles).

v.erase(v.begin() + 2, v.begin() + 7);

Supposons maintenant que vous souhaitez retirer un élément du tableau en fonction de sa valeur, et non plus de sa position.
Voici du code permettant de retirer le premier 9 rencontré dans un tableau v :

auto it = v.begin();

for (; it != v.end(); ++it)
{
    if (*it == 9)
    {
        break;
    }
}

if (it != v.end())
{
    v.erase(it);
}

Ca fonctionne, mais bon, ce n’est pas très concis…
Afin de pouvoir supprimer la boucle qui se charge de la recherche, il est possible d’utiliser la fonction std::find. Attention, il s’agit d’une fonction libre, et non pas d’une fonction-membre de vector.
Modifiez le code ci-dessus afin d’utiliser std::find.

const auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end())
{
    v.erase(it);
}

Opérations globales

Pour terminer, nous allons voir comment réinitialiser complètement un vector.

Si vous souhaitez simplement vider le vector, vous pouvez utiliser la fonction clear.
Et si vous voulez réinitialiser son contenu pour qu’il contienne de nouvelles valeurs, vous pouvez utiliser assign, qui dispose des mêmes surcharges que celles proposées par le constructeur de vector.

Essayez de remplacer le contenu d’un vector existant par un tableau contenant 5 fois la valeur 2, sans utiliser l’opérateur d’assignation (= pas le droit d’utiliser v = ...).
Faites de même, mais en lui attribuant cette fois-ci les valeurs { 0, 2, 32, -4, 3 }.
Enfin, arrangez-vous pour supprimer tout le contenu du tableau.

std::vector<int> v;
v.assign(5, 2);
v.assign({ 0, 2, 32, -4, 3 });
v.clear();