Почему std:: generate() и std:: generate_n() требуют разных итераторов?

Я смотрел generate() и generate_n() в cppreference и пытаюсь понять, почему generate() требует ForwardIterator, тогда как generate_n() требует OutputIterator для диапазона? (Я проверил последний рабочий проект стандарта, и это то же требование.)

Поскольку, по крайней мере, их возможные реализации, похоже, требуют идентичных концепций итератора, а OutputIterator кажется достаточно:

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;
}

Такая же история с std::fill() и std::fill_n().

Ответ 1

по крайней мере, для их возможных реализаций, похоже, требуется идентичная концепция итератора, а OutputIterator кажется достаточно

OutputIterator не поддерживает сравнение равенства/неравенства (включая operator!=, используемый в возможной реализации generate(), который вы показали) и многопроходную гарантию, а ForwardIterator. Это означает, что OutputIterator не может использоваться для представления диапазона через два итератора (например, [first, last)), который требуется интерфейсу generate().

Равенство и неравенство не могут быть определены для выходных итераторов. Даже если определен оператор ==, x == y не должен подразумевать ++ x == ++ y.

Ответ 2

songyuanyao answer объясняет этот вопрос с технической точки зрения. Я попытаюсь дать немного более неофициальное объяснение.

Многие алгоритмы STL, включая generate и fill, применяются к ряду элементов. Способ, которым алгоритм должен иметь доступ к этим элементам, определяет требования к итератору.

В вашем случае определение generate содержит:

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

В то время как второе требование, похоже, удовлетворено любым типом итератора (в конце концов, что все итераторы - итерации по всем вещам:)), поддержка сравнения operator!= предоставляется не всеми типами итераторов.

Например, вы не можете использовать ostream_iterator для std::generate. Но вы можете, например, вывести фиксированное количество сгенерированных значений в поток через std::generate_n.

Здесь очень искусственный пример в Coliru. Как только я начну думать о реальных приложениях, я бы предположил, что способность работать с OutputIterators может быть полезна для реализации некоторой логики сериализации.

Ответ 3

generate() и generate_n(), как и все стандартные библиотечные алгоритмы, работают в диапазоне, то есть в последовательности значений, доступных через итератор. Чтобы применить операцию ко всем элементам диапазона, алгоритм должен знать, где начинается диапазон и где он заканчивается. Существует два распространенных способа предоставления этой информации: вы можете указать диапазон с итератором и длиной и использовать цикл формы while (length-- != 0) { ... ++first; }; или вы можете указать диапазон с парой итераторов [first, last) и использовать цикл формы while (first != last) { ... ++first; }.

Для первой версии вам нужно усовершенствовать итератор, и для этих алгоритмов напишите значение через итератор. Это основные свойства итератора вывода, и все, что вам нужно для generate_n().

Для второй версии вам необходимо увеличить итератор и записать значение через итератор, как и в первой версии. Вы также должны иметь возможность сравнивать два итератора для равенства, а выходной итератор не поддерживает это; у вас должен быть хотя бы forward iterator. Поэтому для generate(), который принимает диапазон, обозначенный парой итераторов, требуется итератор вперед.