c++ - ¿Por qué std:: generate() y std:: generate_n() requieren diferentes iteradores?

iterator language-lawyer

Question

Estaba buscando en generate() y generate_n() en cppreference y estoy tratando de entender por qué generate() requiere ForwardIterator , mientras que generate_n() requiere OutputIterator para el rango? (Revisé el último borrador de trabajo del Estándar, y es el mismo requisito).

Porque, al menos, sus posibles implementaciones parecen requerir conceptos de iterador idénticos y OutputIterator parece ser suficiente:

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

La misma historia con std::fill() y std::fill_n() .

Answer 1

al menos sus posibles implementaciones parecen requerir un concepto de iterador idéntico y OutputIterator parece ser suficiente

OutputIterator no admite la comparación igualdad / desigualdad (incluido el operator!= Utilizado en la posible implementación de generate() que mostró) y la garantía multipasada, mientras que ForwardIterator sí lo hace. Eso significa que OutputIterator no se puede usar para representar un rango a través de dos iteradores (por ejemplo, [first, last) ] que es requerido por la interfaz de generate() .

La igualdad y la desigualdad pueden no estar definidas para los iteradores de salida. Incluso si se define un operador ==, x == y no necesariamente implica ++ x == ++ y.

Answer 2

generate() y generate_n() , como todos los algoritmos de la biblioteca estándar, operan en un rango , es decir, una secuencia de valores a los que se accede a través de un iterador. Para aplicar una operación a todos los elementos de un rango, el algoritmo debe saber dónde comienza el rango y dónde termina. Hay dos formas comunes de darle esa información: puede especificar el rango con un iterador y una longitud, y usar un bucle de la forma while (length-- != 0) { ... ++first; } while (length-- != 0) { ... ++first; } ; o puede especificar el rango con un par de iteradores [first, last) y usar un bucle de la forma while (first != last) { ... ++first; } while (first != last) { ... ++first; } .

Para la primera versión, necesita poder incrementar el iterador y, para estos algoritmos, escribir un valor a través del iterador. Esas son las principales características de un iterador de salida , y eso es todo lo que necesita para generate_n() .

Para la segunda versión, necesita poder incrementar el iterador y escribir un valor a través del iterador, al igual que la primera versión. También debe poder comparar dos iteradores para la igualdad, y un iterador de salida no lo admite; debes tener al menos un iterador directo . Es por eso que generate() , que toma un rango designado por un par de iteradores, requiere un iterador directo.

Answer 3

La respuesta de songyuanyao explica el asunto desde un punto de vista técnico. Trataré de dar una explicación un poco más informal.

Muchos algoritmos STL, incluidos generate y fill , se aplican a una serie de elementos. La forma en que un algoritmo debe poder acceder a esos elementos define los requisitos para el iterador.

En su caso, la definición de generate contiene:

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

Mientras que el segundo requisito parece ser satisfecho por cualquier tipo de iterador (después de todo, de eso se tratan los iteradores - iterando sobre cosas :)), el soporte para el operator!= comparación operator!= lo proporcionan todos los tipos de iteradores.

Por ejemplo, no puede usar ostream_iterator para std::generate . Pero, puede, por ejemplo , generar un número fijo de valores generados en una secuencia a través de std::generate_n .

Aquí hay un ejemplo muy artificial en Coliru . Una vez que empiezo a pensar en aplicaciones de la vida real, supongo que la capacidad de trabajar con OutputIterators puede ser útil para implementar alguna lógica de serialización.