L'un des points forts des collections et algorithmes de la bibliothèque standard est qu'il est possible d'utiliser n'importe quelle collection avec n'importe quel algorithme (avec quelques restrictions, dues à la nature des algorithmes. Par exemple, binary_search ne s'applique par définition que sur des collections triées). Il est même possible d'écrire ses propres collections ou ses propres algorithmes et les utiliser avec ceux de la bibliothèque standard.

Cette flexibilité est obtenue grâce au concept d'itérateur. Le principe est très simple : un itérateur représente un élément dans n'importe quelle collection. En écrivant des algorithmes qui manipulent des itérateurs au lieu de collections particulières, il est ainsi possible d'utiliser les algorithmes sur n'importe quelle collection.

Note : créer un algorithme ne nécessite que d'apprendre la programmation générique, vous verrez cela dans la partie de ce cours “Créer ses algorithmes”. Créer une collection est un peu plus complexe, puisque cela nécessite de connaître la programmation orientée objet. Vous verrez cela plus tard dans le cours.

Même si vous n'en aviez pas conscience, vous avez déjà manipuler des itérateurs. En effet, les fonctions begin et end permettent d'obtenir un itérateur sur le début et la fin d'une collection. Jusque maintenant, vous utilisiez les itérateurs retournés par ces fonctions directement dans des algorithmes, mais rien n'interdit de créer des variables contenant ces itérateurs.

const auto first = std::begin(v);
const auto last = std::end(v);

Pour déclarer une variable de type itérateur, il est beaucoup plus simple d'utiliser l'inférence de type, comme dans le code précédent. Si vous souhaitez écrire explicitement le type d'itérateur, la syntaxe à utiliser est la suivante :

std::vector<int>::iterator first { std::begin(v) };

Vous avez déjà vu des syntaxes similaires dans le début de ce cours (par exemple std::numeric_limits<int>::max() dans le chapitre Obtenir des informations sur les types). Le code std::vector<int>::iterator signifie simplement “le type iterator provenant de la classe vector<int>”.

Notez bien qu'il faut respecter les collections de provenance des itérateurs. Si vous appeler un algorithme qui attend deux itérateurs d'une même collection, mais que vous lui donnez des itérateurs provenant de deux collections différentes, cela produira un comportement indéterminé (un crash en général dans ce cas).

std::sort(begin(v1), end(v2)); // erreur

Il existe en fait plusieurs versions des fonctions begin et end :

• les itérateurs “reverse”, qui permettent de parcourir une collection de la fin vers le début ;
• les itérateurs “constants”, qui interdisent de modifier les éléments d'une collection.

Les fonctions “reverse” commencent par “r”, les fonctions “constantes” commencent par “c” et il est possible d'avoir n'importe quelles combinaisons :

• std::begin et std::end ;
• std::rbegin et std::rend ;
• std::cbegin et std::cend ;
• std::crbegin et std::crend.

Les itérateurs “reverse” permettent de parcourir une collection depuis la fin vers le début.

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string s { "azerty" };
    std::sort(begin(s), end(s));
    std::cout << s << std::endl;
    std::sort(rbegin(s), rend(s));
    std::cout << s << std::endl;
}

affiche :

aertyz
zytrea

L'effet est le même que si vous aviez trié la collection en utilisant l'opérateur “plus grand que” (std::greater) au lieu de l'opération par défaut “plus petit que”.

std::sort(end(s), begin(s));

La “const-correctness” (qui signifie “avoir un code qui respecte l'utilisation des constantes) est un peu plus complexe à comprendre, puisqu'il peut y avoir deux types de constances avec les itérateurs : sur l'itérateur et sur l'élément qu'il représente.

Comme vous l'avez vu, vous pouvez utiliser le mot-clé const pour indiquer d'une variable ne sera pas modifiée. Avec un itérateur, cela signifie que la variable représentera toujours le même élément dans une collection.

const auto first { begin(v); };
first = end(v);       // modification de l'itérateur : erreur
do_something(first);  // modification de l'élément : ok

Dans ce code, first représente toujours le premier élément, il n'est pas possible de changer cette variable pour affecter un autre itérateur. Par contre, l'élément de la collection peut être modifié si vous souhaitez.

Un itérateur constant représente un élément d'une collection, mais interdit de modifier cet élément. Il est possible de changer l'itérateur, mais pas la valeur de l'élément.

auto first { cbegin(v); };
first = cend(v);      // modification de l'itérateur : ok
do_something(first);  // modification de l'élément : erreur

Pour garantir un maximum la qualité du code, il faut utiliser les constantes dès que possible. Par exemple, vous avez vu dans le chapitre précédent le code suivant :

const std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
std::string s2       { "........................................" };
std::copy(cbegin(s1), cend(s1), begin(s2));

Pour rappel, ce code copie les éléments de la première collection (s1) dans la seconde (s2). La première collection n'est pas modifiée, elle est donc constante. Dans le code, cette constance est exprimée par le mot-clé const dans la déclaration de la collection s1 et dans l'utilisation des fonctions retournant des itérateurs constants cbegin et cend.

La seconde collection est modifiée, elle n'est donc pas déclarée comme constante et la fonction begin est utilisée.

L'utilisation des itérateurs ne se limite pas aux algorithmes, il est également possible de les utiliser dans d'autres contexte. Par exemple, beaucoup de collections (en particulier std::vector et std::string) peuvent être initialisées en utilisant une paire d'itérateurs. La nouvelle collection créés contiendra une copie des éléments contenus entre ces deux itérateurs.

#include <iostream>
#include <string>
 
int main() {
    std::string s1 { "azerty" };
 
    std::string s2(begin(s1), end(s1)); 
    std::cout << s2 << std::endl;
 
    std::string s3(begin(s1), begin(s1) + 3); 
    std::cout << s3 << std::endl;
}

affiche :

azerty
aze

La variable s2 correspond à une copie complète de la variable s1. Pour un code aussi simple que celui-là, cette syntaxe est équivalente à une initialisation directe :

std::string s2(s1);

Pour rappel, ce type d'initialisation peut poser des problèmes, par exemple lorsque les deux collections ne sont pas strictement identiques (par exemple vector<float> et vector<double>, voir Introduction aux algorithmes standards). L'utilisation de std::copy peut résoudre ce problème, mais il faut d'abord initialiser la seconde collection avec une taille correcte, puis utiliser la copie.

std::string s2(s1.size());
std::copy(begin(s1), end(s1), begin(s2));

L'initialisation avec une paire d'itérateurs permet de simplifier le code et d'utiliser const plus facilement dans ce cas.

La déclaration de la variable s3 utilise une opération arithmétique sur un itérateur : begin(s1) + 3. Vous allez voir plus en détail cette syntaxe par la suite, mais il suffit simplement de comprendre pour le moment que la syntaxe begin(s1), begin(s1) + 3 permet de prendre les trois premiers éléments.

Pourquoi cette façon de faire ? Avec find, si aucun élément n'est trouvé, comment indiquer que la recherche a échoué ? Une solution serait que find retourne un booléen en plus. Mais ce serait compliqué à gérer. La solution choisie est qu'elle retourne end() si la recherche échoue.

Donc tester le résultat de find :

auto p = std::find(begin(v), end(v), 3);
std::cout << boolalpha << (p == end(v)) << endl;
p = std::find(begin(v), end(v), 10);
std::cout << boolalpha << (p == end(v)) << endl;

Comme end(v) ne représente pas un élément dans une collection, il est interdit de le manipuler comme les autres positions. Ainsi, il est légal d'écrire begin(v)+1, puisque begin(v) est une position correspondante à un élément dans la collection (s'il y a au moins un élément dans la collection), on a le droit de le manipuler. Au contraire, end(v)+1 est interdit. C'est pour cela que la notion begin(v)+n est dangereuse, puisque l'on peut accéder à une position invalide, si n > size().

advance ? next ?

Supposons que l'on ait plusieurs fois la même valeur dans une collection. Comment toutes les trouver avec find ?

On recherche d'abord sur l'intervalle qui nous intéresse avec begin et end. Puis, si on trouve un élément (donc si p != end), alors on peut refaire la recherche entre p+1 et end pour trouver un deuxième élément. Et ainsi de suite, jusqu'à trouver tous les éléments.

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s { "azertyazerty" };
    auto position = std::find(std::begin(s), std::end(s), 'e');
    auto const first = std::string(std::begin(s), position);
    auto const second = std::string(position, std::end(s));
    std::cout << first << std::endl;
    std::cout << second << std::endl;
 
    position = std::find(position+1, std::end(s), 'e');
    std::cout << std::string(std::begin(s), position) << std::endl;
    std::cout << std::string(position, std::end(s)) << std::endl;
}

affiche :

az
ertyazerty
azertyaz
erty

second find : recherche à partir du 'e' trouvé

Pour effectuer une recherche dans une collection, on peut utiliser find. Si on regarde la documentation, elle indique que cette fonction prend un range et un élément à chercher, elle retourne l'itérateur (donc une position) de l'élément dans la collection s'il a été trouvé, sinon l'itérateur end.

std::vector<int> v1 { 1, 2, 3, 4, 5 };
auto position = std::find(std::begin(v), std::end(v), 3);

On peut alors utiliser cette position pour créer deux sous-collections :

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    std::vector<int> v1 { 1, 2, 3, 4, 5 };
    auto p = std::find(std::begin(v1), std::end(v1), 3);
 
    std::vector<float> v2(std::begin(v1), p);
    for (auto i: v2) std::cout << i << ' ';
    std::cout << std::endl;
 
    std::vector<float> v3(p, std::end(v1));
    for (auto i: v3) std::cout << i << ' ';
    std::cout << endl;
}

affiche :

1 2 
3 4 5 

On voit ici une particularité importante des ranges. La variable p correspond à la position de la valeur 3 dans la collection. On pourrait croire que la collection v2 qui est créée à partir de begin(v1) et p allait contenir les éléments { 1, 2, 3 }, mais ce n'est pas le cas.

En effet, un range est une paire d'itérateurs dont le premier est inclus et le second exclu.

Revenons sur un code précédent. Lorsque l'on écrit :

std::vector<int> v1 { 1, 2, 3, 4, 5 };
std::vector<int> v2(std::begin(v1), std::end(v1));

On a bien une copie complète de v1. Est-ce que cela est compatible avec l'exclusion de la borne supérieure du range ? En fait, oui, tout simplement parce que end(v1) correspond à la fin de la collection, et non au dernier élément de cette collection. Si on crée des sous-collections depuis les premiers et derniers éléments :

std::vector<int> v1 { 1, 2, 3, 4, 5 };
 
// premier élément ?
std::vector<int> v2(std::begin(v1), std::begin(v1));
std::cout << boolalpha << v2.empty() << std::endl; // vide
 
// premier élément
std::vector<int> v3(std::begin(v1), std::begin(v1)+1);
for (auto i: v3) std::cout << i << ' '; // ok, contient {1}
 
// dernier élément ?
std::vector<int> v4(std::end(v1), std::end(v1));
std::cout << boolalpha << v4.empty() << std::endl; // vide
 
// dernier élément
std::vector<int> v5(std::end(v1)-1, std::end(v1));
for (auto i: v5) std::cout << i << ' '; // ok, contient {5}

En pratique, cela signifie que end(v) ne représente pas le dernier élément d'une collection, mais un élément supplémentaire et imaginaire qui se trouverait après le dernier élément.

Lorsque un itérateur correspond à une position valide dans une collection (donc pas end), il est possible d'accéder à l'élément en utilisant l'opérateur * devant l'itérateur :

vector<int> v { 1, 2, 3, 4, 5 };
auto p = begin(v);
cout << (*p) << endl;

affiche 1

Egalement accessible en modification (si non const) :

auto p = begin(v) + 3;
*p = 0;
for (auto value: v) 
    cout << value << endl;

Si fonction template :

template<class Iterator>
void foo(Iterator it) {
    auto value = *it;
}

it est un itérateur sur un élément d'un conteneur, donc *it correspond à un élément d'un conteneur. Le type déduit par auto est le type de cet élément

std::vector<int> v {};
foo(begin(v)); // dans foo, it est de type vector<int>::iterator et *it est de type int

template<class Iterator>
void foo(Iterator it) {
    typename iterator_traits<Iterator>::value_type value = *it;
}

Iterateur, bidirectional, random. Possibilité de manipuler directement les éléments d'une collection. Via itérateur (le plus générique) et pour certains types de collection par [] ou at(). next, prev, advance, distance

Vu comment accéder séquentiellement dans un conteneur (du début à la fin). Méthode la plus simple et la plus performante. Autre méthode : accéder directement à un élément dans le conteneur. Faisable sur certain type de conteneur, dont array et vector.

Utilisation de at() et []

Vérification des limites d'accès

Adaptateur : back_inserter, front_inserter, inserter etc