C++
Les itérateurs

C itérateurs (pointeurs)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Ce code afficherait les nombres 1 à 5, un sur chaque ligne comme ceci:

1
2
3
4
5

Le briser

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

Cette ligne crée un nouveau tableau d'entiers avec 5 valeurs. Les tableaux C ne sont que des pointeurs vers la mémoire où chaque valeur est stockée ensemble dans un bloc contigu.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Ces lignes créent deux pointeurs. Le premier pointeur reçoit la valeur du pointeur de tableau, qui est l'adresse du premier élément du tableau. L'opérateur sizeof utilisé sur un tableau C renvoie la taille du tableau en octets. Divisé par la taille d'un élément, cela donne le nombre d'éléments dans le tableau. Nous pouvons l'utiliser pour trouver l'adresse du bloc après le tableau.

for (const int* i = first; i < afterLast; ++i) {

Nous créons ici un pointeur que nous utiliserons comme itérateur. Il est initialisé avec l'adresse du premier élément que nous voulons parcourir, et nous allons continuer à itérer tant que i est inférieur à afterLast , ce qui signifie aussi longtemps que i pointe vers une adresse dans array .

    std::cout << *i << std::endl;

Enfin, dans la boucle , nous pouvons accéder à la valeur de notre itérateur i pointe par déréférencement elle. Ici, l'opérateur de déréférence * renvoie la valeur à l'adresse dans i .

Vue d'ensemble

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é.

Itérateurs inverses

Si nous voulons parcourir en arrière une liste ou un vecteur, nous pouvons utiliser un reverse_iterator . Un itérateur inversé est créé à partir d'un itérateur bidirectionnel ou à accès aléatoire qu'il conserve en tant que membre et accessible via base() .

Pour itérer en arrière, utilisez rbegin() et rend() comme itérateurs pour la fin de la collection et le début de la collection, respectivement.

Par exemple, pour itérer l'utilisation en arrière:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

Un itérateur inversé peut être converti en un itérateur avant via la fonction membre base() . La relation est que l'itérateur inversé référence un élément après l'itérateur base() :

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

Dans la visualisation où les itérateurs marquent les positions entre les éléments, la relation est plus simple:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Itérateur de vecteur

begin renvoie un iterator au premier élément du conteneur de séquence.

end renvoie un iterator au premier élément après la fin.

Si l'objet vectoriel est const , les deux begin et end renvoient un const_iterator . Si vous souhaitez qu'un const_iterator soit renvoyé même si votre vecteur n'est pas const , vous pouvez utiliser cbegin et cend .

Exemple:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Sortie:

1 2 3 4 5

Itérateur de carte

Un itérateur sur le premier élément du conteneur.

Si un objet map est qualifié en const, la fonction renvoie un const_iterator . Sinon, il renvoie un iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Sortie:

a => 200
b => 100
c => 300

Itérateurs de flux

Les itérateurs de flux sont utiles lorsque vous devez lire une séquence ou imprimer des données formatées à partir d'un conteneur:

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

Le programme d'exemple imprimera 1 -- 2 -- 3 -- 4 -- sur la sortie standard.

Ecrivez votre propre itérateur avec générateur

Un modèle courant dans d'autres langages consiste à avoir une fonction qui produit un "flux" d'objets et à pouvoir utiliser le code de boucle pour la parcourir.

Nous pouvons modéliser ceci en C ++ comme

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

exemple vivant .

Nous stockons l'élément généré tôt afin de pouvoir détecter plus facilement si nous sommes déjà à la fin.

Comme la fonction d'un itérateur de générateur d'extrémité n'est jamais utilisée, nous pouvons créer une gamme d'itérateurs de générateur en ne copiant qu'une seule fois la std::function . Un générateur de génération construit par défaut se compare à lui-même et à tous les autres générateurs-finisseurs.