Question sur la librairie algorithm

Bonjour,

Je suis un ancien du C qui refuse de ce conformer à C++ .NET de Microsh.t et qui préfère la méthode dure à la Linux Slackware!!! Donc compilateur g++ et éditeur de texte (Code::Block dans mon cas).

Je n’ai pas suivis l’évolution du C++11, encore moins la 14 donc vous imaginez que ma connaissance de la STL est Null.

J’ai décidé de m’y remettre sérieusement et j’ai trouvé votre tutoriel https://zestedesavoir.com/tutoriels/822/la-programmation-en-c-moderne

C’est vraiment super, je suis vos exemples, fait des tests et ça fonctionne. Mais il me manque quelque chose à ma compréhension et j’espère que vous allez pouvoir m’aligner.

Aussi, toutes mes questions sont en lien avec ce tuto.

Voici mes questions:

1. Je m’interroge sur le "contenu", le type, d’un itérateur. Partout, on indique que l’itérateur est de type auto, mais dans les fait, quel est le type d’un itérateur?

À ma compréhension, un itérateur est un conteneur qui détient un ou des résultat. Donc c’est un array? un array de pointeurs?

    //Phrase clé
    string const str_Text { "Un exemple de phrase avec plusieurs mots." };

    //Création des itérateurs
    auto const it_Begin { begin(str_Text) };

    cout << *it_Begin << endl;

On m’affiche içi "U" donc j’assume que l’itérateur it_Begin est un pointeur de type char, ou encore mieux, un indice à incrémenter pour l’élément 0 du tableau de char str_Text (str_Text[0])?

    cout << *it_Begin << endl;
    it_Begin++;
    cout << *it_Begin << endl;

Ceci m’affiche U et n. Donc l’itérateur semble bien être un pointeur ou un array de pointeurs.

Mais dans le tuto, il est inscrit:

Grâce aux itérateurs, nous pouvons facilement créer des sous-ensembles à partir d’une collection d’éléments, comme un tableau qui ne contiendrait que les éléments 2 à 5 d’un autre tableau.

Je lis içi (comprend) que les itérateurs peuvent contenir des tableaux de types array? Je suis un peu perdu sur le type. Vous allez me dire "voilà pourquoi utiliser auto" mais une explication serait appréciée s.v.p.

2. Toujours dans le même tuto, l’exemple qui compte le nombre de "e" de chaque mot dans une phrase est une vraie source … de questionnement.

Dans l’exemple, on définit un l’itérateur

std::string const phrase { "Exemple illustrant le tutoriel C++ de Zeste de Savoir, mais un peu plus long." };
auto iterateur_espace { std::find(std::begin(phrase), std::end(phrase), ' ') };

Donc, je comprend que la variable iterateur_espace sera un itérateur spécifiquement sur les espaces. Mais non, à ma grande surprise, il faut le redéfinir à chaque fois à partir d’un nouvel indice.

    // Tant qu'on est pas à la fin de la phrase.
    while (iterateur_espace != std::end(phrase))
    {
        std::string const mot { iterateur_precedent, iterateur_espace };
        auto const total_e { std::count(std::begin(mot), std::end(mot), 'e') };

        std::cout << "Dans le mot '" << mot << "', il y a " << total_e << " fois la lettre 'e'." << std::endl;

        // On incrémente pour ne pas garder l'espace au début, car iterateur_espace pointe déjà sur un espace.
        ++iterateur_espace;

        // On met à jour notre itérateur de sauvegarde.
        iterateur_precedent = iterateur_espace;

        // On cherche la première occurrence dans le nouveau sous-ensemble.
        iterateur_espace = std::find(iterateur_espace, std::end(phrase), ' ');

Je suis cassé. Pourquoi faut-il redéfinir l’itérateur 'iterateur_espace’, si on l’incrémente de +1 précédemment et qu’en entré de boucle, on définit que cet itérateur pointe sur une recherche des Espaces. Ne devrait-il pas déjà pointer sur le second espace? C’est un itérateur après tout et on le définit comme itération sur les ' '.

J’ai tenté d’expliquer au mieux mes questions, n’hésitez pas à me demander des précisions au besoin, mais là, vous m’avez eu.

Merci de votre aide.

Salut @Seaquest45. Sois le bienvenu sur Zeste de Savoir.

Comme tu l’as déjà intuitivement deviné, on peut voir un itérateur comme un pointeur sur un tableau, mais en plus complet et plus sûr.

Il faut savoir que tous les conteneurs n’offrent pas les mêmes possibilités.

• Pour certains, on ne peut accéder à un élément que en partant depuis le premier et en incrémentant de un.
• Pour d’autres, on peut accéder directement à l’élément voulu.
• Des fois, on peut avancer ou reculer. D’autres fois, on ne peut qu’avancer depuis le début vers la fin.

En bref, des situations différentes et donc des façons d’itérer différentes.

En interne, l’implémentation varie en fonction du compilateur, du conteneur, etc. Mais en externe, tous les itérateurs présentent les mêmes caractéristiques. Du coup, on peut utiliser ces itérateurs comme des abstractions.

Le vrai type d’un itérateur dépend du conteneur auquel il est associé. Mais le type complet est long à écrire. D’où le auto qui permet de gagner de la place et de rendre le code plus lisible.

Pour répondre à la deuxième question, comme un itérateur pointe sur un élément d’un conteneur en particulier, il est possible, avec deux itérateurs, de définir un sous-ensemble. Si mon premier intérateur pointe sur le troisième élément de mon tableau et si le deuxième pointe sur le quinzième élément, alors je peux créer un nouveau tableau en lui donnant ces deux itérateurs. Il sera initialisé avec toutes les valeurs comprises entre le premier et le deuxième itérateur.

Enfin, pour ta troisième question, la fonction std::find retourne un itérateur sur la première occurrence trouvée. Elle ne retourne aucun tableau. Donc au premier tour, on a un itérateur sur le premier espace. Mais au tour d’après, si on ne fait rien, cet itérateur ne bouge pas. Il pointe toujours sur le premier espace. Essaie de te faire un schéma de l’exécution du code, ça t’aidera à mieux voir ce qui se passe.

J’espère avoir pu t’éclairer déjà un peu plus. Je suis sur téléphone, donc pas pratique de répondre un long pavé.

Si tu as encore d’autres questions, n’hésite pas.

Salut,

Un itérateur est juste un objet de type générique qui se consomme pour parcourir un ensemble d’éléments. Son type dépend du type de l’ensemble (d’où le auto pour faciliter les choses), sur un std::vector<T> je crois qu’il s’agit d’un std::vector<T>::iterator.

Sur des séquences, l’itérateur peut simple être vu comme un entier (l’index dans la séquence), qui contient de plus une référence vers la séquence. Ce qui permet de transformer les *it en vec[i].

Mais l’itérateur n’est lié à aucun algorithme : ++it le fera avancer d’un pas sur la collection, en passant juste sur le caractère suivant dans le cas d’une chaîne.

std::find renvoie donc un itérateur sur le premier espace trouvé, mais incrémenter cet itérateur ne fera qu’avancer sur le caractère suivant.

En revanche il serait parfaitement possible d’implémenter ton propre type d’itérateur qui avancerait d’espace en espace sur la chaîne.

Salut entwanne,

Mais littérateur n’est lié à aucun algorithme : ++it le fera avancer d’un pas sur la collection, en passant juste sur le caractère suivant dans le cas d’une chaîne.

std::find renvoie donc un littérateur sur le premier espace trouvé, mais incrémenter cet littérateur ne fera qu’avancer sur le caractère suivant.

Ok, je me lance dans une explication pour voir si j’ai bien compris.

Un littérateur est un pointeur (pour faire simple) et les fonctions std::find, std::count, etc… utilise les pointeurs de début et de fin (std::begin(phrase) et std::end(phrase)) pour positionner son vecteur de recherche entre les deux valeurs d’ittérateur. Ainsi std::find, ne fait que retourner un nouveau pointeur à l’emplacement du caractère trouvé entre les deux pointeurs de position utilisés, d’ou la nécessité de réassigner un nouveau pointeur de position via std::find.

Ce qui est mélangeant dans les lectures, c’est qu’on parle toujours d’itérations dans les collections d’éléments. Donc ma compréhension, à tord, est que littérateur EST un résultat obtenus d’une collection d’éléments et non un pointeur à une position définit dans la collection.

Est-ce que je résume bien ton explication?

Je vais tenter de reproduire la fonction vector<string> explode(char delimiter,string StringToSplit){} de PHP, qui retourne un tableau contenant tous les objets. Du plaisir en vue les amis

Merci de ton aide.

J’ai l’impression que tu as plutôt bien compris cette définition. Par contre, quand tu écris

Un itérateur est un pointeur (pour faire simple)…

J’imagine que tu parles d’un pointeur au sens large (un objet référençant un autre comme le fait un pointeur nu T* mais aussi un pointeur intelligent std::unique_ptr<T> ou encore une référence T& ou T&&). Si ce n’est pas le cas, sache qu’un pointeur au sens restreint (T*) peut être un itérateur (notamment dans un vector<T> pour tout T différent de bool) mais pas forcément.

d’où la nécessité de réassigner un nouveau pointeur de position via std::find.

Par contre je n’ai pas vraiment compris ça. Une fois que std::find a renvoyé un pointeur différent de std::end, il est directement utilisable comme dans le code (non-testé) ci-dessous

std::vector<int> vec { 0, 2, 2, 3, 4, 5 };

auto iter = std::find(vec.begin(), vec.end(), 2);
if (iter != vec.end())
    *iter = 1;

// vec contient maintenant { 0, 1, 2, 3, 4, 5 };

Comme tu peux le voir, il n’y a pas besoin d’utiliser std::find de nouveau.

Salut BorisD,

Merci pour ton explication. En fait, quand j’ai dit:

d’où la nécessité de réassigner un nouveau pointeur de position via std::find.

je fais référence à la position du pointeur actuel. J’avais pour impression, à tord, que l’itérateur était ni plus ni moins la collection trouvé, et non une "position" dans une collection.

Donc, à mon sens, une fois que nous avons utilisé la position de l’itérateur, celle-ci doit être réassigné avec la nouvelle valeur, donc c’est un nouveau pointeur de position. Tu illustres bien ce que je veux dire dans ton code à savoir:

auto iter = std::find(vec.begin(), vec.end(), 2);
if (iter != vec.end())
    *iter = 1;

Tu recherches le premier 2 trouvé et n’impacte en rien le second 2 de ton vecteur, à moins que je lui fasse une seconde fois un find, comme ce code (et s.v.p., ne me lancez pas de tomates, c’est pour explication seulement et très laid)

auto iter = std::find(vec.begin(), vec.end(), 2);
if (iter != vec.end())
    *iter = 1;

iter++;
iter = std::find(iter, vec.end(), 2);
if (iter != vec.end())
    *iter = 6789;

// vec contient maintenant { 0, 1, 6789, 3, 4, 5 };

Cela dit, je m’interroge sur l’appellation "ittérateur" de cet élément. Je comprend que c’est fait comme ça, mais merde, quel cauchemard de sémantique…

Merci beaucoup à tous pour votre aide et n’hésitez pas à commenter si vous avez d’autres pistes. Je continue le tuto.

Un itérateur est un machin que l’on déplace à l’intérieur d’une séquence d’éléments pour itérer à l’intérieur de cette séquence. La séquence peut être liée à un conteneur (qui contient, possède), comme aussi un tableau, ou même des choses plus abstraites que l’on peut voir comme une séquence (genre les mots d’un fichier).

Le machin qui permet d’itérer dans une séquence exprime bien une position comme tu l’as compris. Mais c’est plus qu’une simple position car on veut permettre aussi de se déplacer (avec ++ et/ou --), et de consulter et/ou altérer le truc pointé par la position. Selon les fonctionnalités exactes supportées, on donnera des noms plus précis.

Les pointeurs (1) sont un cas particulier d’itérateur. A une époque on les nommait itérateurs triviaux — j’ai l’impression que c’est passé de mode, on se contente juste de dire itérateur à accès direct (Random Access Iterator)

(1) Pas la partie allocation, mais la partie arithmétique des pointeurs.

Les itérateurs sont un des 3 axes de la STL historique. Les 2 autres sont les conteneurs desquels on peut extraire des itérateurs, et les algorithmes qui travaillent tous sur des itérateurs. L’itérateur est l’abstraction qui sera disponible sur toutes les séquences, à contrario des indices qui ne sont disponibles que sur les séquences à accès direct. P.ex. un indice sur une liste chaînée, ça n’existe pas, et on ne veut pas que cela existe car cela serait totalement inefficace (genre pour itérer entre 0 et size(), il faudrait compter 0 éléments, puis 1 éléments, puis 2 éléments, jusqu’à compter n éléments? Au final on aurait parcouru la liste size*(size+1) fois).

A noter que grâce à une paire d’itérateurs, on peut exprimer une vue à l’intérieur d’un conteneur, sans pour autant extraire un autre conteneur.

Dans la prochaine norme (C++20), arrivent les ranges (séquences, plages) qui veulent simplifier la manipulation des séquences au travers d’algorithmes. Parce que les itérateurs, c’est cool, mais c’est quand même un peu lourdingue à manipuler.

PS: La seule bibliothèque dans l’histoire, c’est "la bibliothèque standard du C++". <algorithm> n’est qu’un de ses fichiers d’en-tête.

Bon matin lmghs,

Excuse moi de te lire si tard, j’ai pris une pause du temps des fêtes. Merci d’avoir pris le temps de me répondre.

Mais c’est plus qu’une simple position car on veut permettre aussi de se déplacer (avec ++ et/ou —), et de consulter et/ou altérer le truc pointé par la position. Selon les fonctionnalités exactes supportées, on donnera des noms plus précis.

C’est justement ça le truc, on dit partout que c’est plus qu’une simple position, mais même ton explication démontre que l’itérateur à tout d’un pointeur de position opérant entre les balises du range, totalement arbitraire, de conteneur.begin() et conteneur.end(). Donc plus je lis, et plus tout ça n’est que sémantique.

Bon, maintenant tu me parles de la norme C++20 et je viens juste de terminer mon rattrapage sur C++14.

PS: La seule bibliothèque dans l’histoire, c’est "la bibliothèque standard du C++". <algorithm> n’est qu’un de ses fichiers d’en-tête.

, J’avais compris car le namespace valide demeure pour tout le std:: via le using namespace std; ou using std::cout par exemple.

Personellement, je trouve que ça ajoute une difficulté le plus à l’utilisation de la librairie standard puisqu’en plus de savoir tout son contenue, il faut savoir quels sont les bons fichiers d’entête à inclure pour l’utiliser. Mais bon, ça doit venir avec l’expérience j’imagine…

Merci de tes réponses et bonne année 2020