C++ Vue d'ensemble


Exemple

Les itérateurs sont des positions

Les itérateurs sont un moyen de naviguer et d'opérer sur une séquence d'éléments et constituent une extension généralisée des pointeurs. Conceptuellement, il est important de se rappeler que les itérateurs sont des positions et non des éléments. Par exemple, prenez la séquence suivante:

A B C

La séquence contient trois éléments et quatre positions

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Les éléments sont des choses dans une séquence. Les positions sont des endroits où des opérations significatives peuvent avoir lieu dans la séquence. Par exemple, on insère dans une position, avant ou après l' élément A, pas dans un élément. Même la suppression d'un élément ( erase(A) ) se fait en trouvant d'abord sa position, puis en la supprimant.

Des itérateurs aux valeurs

Pour convertir une position en une valeur, un itérateur est déréférencé :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

On peut penser à un itérateur en tant que déréférencement à la valeur à laquelle il fait référence dans la séquence. Ceci est particulièrement utile pour comprendre pourquoi vous ne devriez jamais déréférencer l'itérateur end() dans une séquence:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

Dans toutes les séquences et tous les conteneurs trouvés dans la bibliothèque standard C ++, begin() renvoie un itérateur à la première position et end() renvoie un itérateur à un autre après la dernière position ( pas la dernière!). Par conséquent, les noms de ces itérateurs dans les algorithmes sont souvent étiquetés en first et en last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

Il est également possible d'obtenir un itérateur à n'importe quelle séquence , car même une séquence vide contient au moins une position:

+---+
|   |
+---+

Dans une séquence vide, begin() et end() auront la même position et aucune des deux ne pourra être déréférencée:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

La visualisation alternative des itérateurs est qu'ils marquent les positions entre les éléments:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

et déréférencer un itérateur renvoie une référence à l'élément venant après l'itérateur. Certaines situations où cette vue est particulièrement utile sont les suivantes:

  • insert opérations d'insertion insèrent des éléments dans la position indiquée par l'itérateur,
  • erase opérations d' erase renverront un itérateur correspondant à la même position que celle passée,
  • un itérateur et son itérateur inverse correspondant sont situés dans la même position entre les éléments

Itérateurs non valides

Un itérateur devient invalidé si (par exemple, au cours d'une opération) sa position ne fait plus partie d'une séquence. Un itérateur invalidé ne peut pas être déréférencé tant qu'il n'a pas été réaffecté à une position valide. Par exemple:

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

Les nombreux algorithmes et fonctions de membre de la séquence dans la bibliothèque standard C ++ ont des règles régissant le moment où les itérateurs sont invalidés. Chaque algorithme est différent dans la manière dont il traite (et invalide) les itérateurs.

Naviguer avec les itérateurs

Comme nous le savons, les itérateurs servent à naviguer dans les séquences. Pour ce faire, un itérateur doit migrer sa position tout au long de la séquence. Les itérateurs peuvent avancer dans la séquence et certains peuvent reculer:

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Notez que le second argument de std :: distance devrait être accessible depuis le premier (ou, en d’autres termes, first devrait être inférieur ou égal à la second ).

Même si vous pouvez exécuter des opérateurs arithmétiques avec des itérateurs, toutes les opérations ne sont pas définies pour tous les types d'itérateurs. a = b + 3; fonctionnerait pour les itérateurs à accès aléatoire, mais ne fonctionnerait pas pour les itérateurs directs ou bidirectionnels, qui peuvent toujours être avancés de 3 positions avec quelque chose comme b = a; ++b; ++b; ++b; . Il est donc recommandé d'utiliser des fonctions spéciales si vous n'êtes pas sûr du type d'itérateur (par exemple, dans une fonction de modèle acceptant un itérateur).

Concepts d'itérateur

Le standard C ++ décrit plusieurs concepts d'itérateurs différents. Ceux-ci sont regroupés en fonction de leur comportement dans les séquences auxquelles ils se réfèrent. Si vous connaissez le concept d'un modèle d' itérateur (se comporte comme), vous pouvez être assuré du comportement de cet itérateur indépendamment de la séquence à laquelle il appartient . Ils sont souvent décrits dans l'ordre, du plus restrictif au moins restrictif (car le concept d'itérateur suivant est un pas meilleur que son prédécesseur):

  • Les itérateurs d'entrée: peuvent être déréférencés seulement une fois par position. Ne peut avancer que d'une seule position à la fois.
  • Itérateurs directs: un itérateur d'entrée pouvant être déréférencé un nombre illimité de fois.
  • Itérateurs: Un Bidirectionnel iterator avant qui peut également avancer en arrière une position à la fois.
  • Randator Access Iterators: Un itérateur bidirectionnel qui peut avancer ou reculer d'un nombre quelconque de positions à la fois.
  • Itérateurs contigus (depuis C ++ 17): itérateur à accès aléatoire garantissant que les données sous-jacentes sont contiguës en mémoire.

Les algorithmes peuvent varier en fonction du concept modélisé par les itérateurs. Par exemple, bien que random_shuffle puisse être implémenté pour les itérateurs avant, une variante plus efficace nécessitant des itérateurs à accès aléatoire pourrait être fournie.

Traits d'itérateur

Les traits d'itérateur fournissent une interface uniforme aux propriétés des itérateurs. Ils permettent de récupérer la valeur, la différence, le pointeur, les types de référence et également la catégorie d'itérateur:

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

La catégorie d'itérateur peut être utilisée pour spécialiser des algorithmes:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Les catégories d'itérateurs sont essentiellement des concepts d'itérateurs, sauf que les itérateurs contigus ne disposent pas de leur propre balise, car il a été trouvé que le code est cassé.