Pourquoi std :: generate() et std :: generate_n() requièrent des itérateurs différents?

Question

Je regardais generate() et generate_n() dans cppreference et j'essaie de comprendre pourquoi generate() exige ForwardIterator, tandis que generate_n() exige OutputIterator pour la gamme? (J'ai vérifié le dernier projet de travail de la norme, et c'est la même exigence.)

Parce que, au moins leurs implémentations possibles semblent exiger des concepts de iterator identiques et OutputIterator semble être assez:

generate():

template<class ForwardIt, class Generator> 
void generate(ForwardIt first, ForwardIt last, Generator g) 
{ 
    while (first != last) { 
     *first++ = g(); 
    } 
} 

generate_n():

template<class OutputIt, class Size, class Generator> 
OutputIt generate_n(OutputIt first, Size count, Generator g) 
{ 
    for (Size i = 0; i < count; i++) { 
     *first++ = g(); 
    } 
    return first; 
} 

même chose avec std::fill() et std::fill_n().

Answer 1

au moins leurs implémentations possibles semblent exiger concept iterator identique et OutputIterator semble être assez

OutputIterator ne comparaison supporte pas l'égalité/inégalité (y compris operator!= utilisés dans la mise en œuvre possible de generate() vous montriez) et la garantie multipass, tandis que ForwardIterator fait. Cela signifie que OutputIterator ne peut pas être utilisé pour représenter une plage via deux itérateurs (par exemple [first, last)) qui est requise par l'interface generate().

L'égalité et l'inégalité ne peuvent pas être définies pour les itérateurs de sortie. Même si un opérateur == est défini, x == y n'implique pas nécessairement ++ x == ++ y.

Answer 2

songyuanyao's answer explique la question d'un point de vue technique. Je vais essayer de fournir une explication un peu plus informelle.

De nombreux algorithmes STL, y compris generate et fill, sont appliqués à un certain nombre d'éléments. La façon dont un algorithme doit pouvoir accéder à ces éléments définit les exigences pour l'itérateur.

Dans votre cas, la définition de generate contient:

... 
while (first != last) { // implies that Iter implements operator!= 
    *first++;    // implies that Iter implements operator++ 

Alors que la deuxième exigence semble être satisfaite par tout type de iterator (après tout, c'est ce que itérateurs sont tout - itérer sur les choses :)) , le support pour la comparaison operator!= est fourni par tous les types d'itérateurs.

Par exemple, vous ne pouvez pas utiliser ostream_iterator pour std::generate. Mais, vous pouvez, par exemple., génère un nombre fixe de valeurs générées dans un flux via std::generate_n.

Voici a very artificial example at Coliru. Une fois que je commence à penser aux applications de la vie réelle, je suppose que la capacité de travailler avec OutputIterators peut être utile pour implémenter une logique de sérialisation.

Answer 3

generate() et generate_n(), comme tous les algorithmes de la bibliothèque standard, fonctionnent sur une gamme , qui est, une séquence de valeurs accessible via un itérateur. Afin d'appliquer une opération à tous les éléments d'une gamme, l'algorithme doit savoir où la gamme commence et où elle se termine. Il existe deux façons courantes de lui donner cette information: vous pouvez spécifier la plage avec un itérateur et une longueur, et utiliser une boucle de la forme while (length-- != 0) { ... ++first; }; ou vous pouvez spécifier la plage avec une paire d'itérateurs [first, last) et utiliser une boucle de la forme while (first != last) { ... ++first; }.

Pour la première version, vous devez pouvoir incrémenter l'itérateur et, pour ces algorithmes, écrire une valeur dans l'itérateur. Ce sont les principales propriétés d'un itérateur de sortie, et c'est tout ce dont vous avez besoin pour generate_n(). Pour la deuxième version, vous devez pouvoir incrémenter l'itérateur et écrire une valeur à travers l'itérateur, tout comme la première version. Vous également devez être capable de comparer deux itérateurs pour l'égalité, et un itérateur de sortie ne supporte pas cela; vous devez avoir au moins un itérateur avant. C'est pourquoi generate(), qui prend une plage désignée par une paire d'itérateurs, nécessite un itérateur avant.