C++ standard wording: Does "through all iterators in the range" imply sequentiality?

Esta pregunta SO provocó una discusión sobre std::generate y las garantías hechas por el estándar. En particular, puede usar objetos de función con estado interno y confiar en generate(it1, it2, gen) para llamar a gen(), almacenar el resultado en *it, llamar a gen() nuevamente, almacenar en *(it + 1), etc., o puede empezar por atrás, por ejemplo?

El estándar (n3337, §25.3.7 / 1) dice esto:

Efectos: El primer algoritmo invoca el objeto de función gen y asigna el valor de retorno de gen a través de todos los iteradores en el rango [first,last). El segundo algoritmo invoca el objeto de función gen y asigna el valor de retorno de gen a través de todos los iteradores en el rango [first,first + n) si n es positivo, de lo contrario no hace nada.

Parece que no se garantiza ningún orden, especialmente porque otros párrafos tienen una redacción más fuerte, por ejemplo std::for_each (Efectos: Se aplica f al resultado de desreferenciar cada iterador en el rango [first,last), comenzando desde primero y continuando a last - 1. Si tomamos esto literalmente, solo garantiza comenzar en first y terminar en last, sin embargo, no hay garantías en el pedido intermedio).

Pero: Ambos Microsoft y Apache C++ standard library ambos dan ejemplos en sus páginas de documentación que requieren que la evaluación sea secuencial. Y tanto libc++ (en algorithm) como libstdc++ (en bits/stl_algo.h) lo implementan de esa manera. Por otra parte, se pierde una gran cantidad de aplicaciones potenciales para generate sin esta garantía.

¿La redacción actual implica secuencialidad? De no ser así, ¿fue un descuido de los miembros del comité o intencional?

(Soy muy consciente de que no hay muchas personas que puedan proporcionar respuestas perspicaces a esta pregunta sin meramente especular o discutir, pero en mi humilde opinión, esto no hace que esta pregunta 'no sea constructiva' según las directrices SO.)

Gracias a @juanchopanza por señalar este tema y me refiero al párrafo sobre for_each.

Author: Community, 2013-02-12
Source

2 answers

En la discusión de LWG475, std::for_each se compara con std::transform. Se observa que "transform no garantiza el orden en el que se llama a su objeto de función". Así que, sí, el comité es consciente de la falta de garantías secuenciales en la norma.

Tampoco hay un requisito opuesto para el comportamiento no secuencial, por lo que Microsoft y Apache son libres de usar la evaluación secuencial.

 7
Author: MSalters,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-12 10:55:19

En cualquier lugar donde el estándar no especifique un orden en un algoritmo, debe asumir que una implementación puede explotar eso para el paralelismo. El documento n3408 discute las opciones para la paralelización, y apunta a la biblioteca Thrust, que es tanto una reimplementación habilitada en paralelo utilizable de los algoritmos estándar como una prueba de concepto para la futura estandarización del paralelismo en los algoritmos.

Mirando la implementación de Thrust de generate, llama a gen en un bucle paralelo siempre que la categoría del iterador sea de acceso aleatorio. Como has observado, esto es consistente con el estándar, por lo que no debes asumir que generate siempre será secuencial. (Por ejemplo, un thread-safe std::rand se puede usar eficientemente con generate y no requiere invocación secuencial.)

Los únicos algoritmos que garantizan la invocación secuencial son los de numeric; si su código depende de la invocación secuencial, debe usar iota en lugar de generate. Adaptar un generador existente:

template<typename F> struct iota_adapter {
   F f;
   operator typename std::result_of<F()>::type() { return f(); }
   void operator++() {}
};
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; }

Utilizar como: 

#include <numeric>
#include <iostream>

int main() {
   int v[5], i = 0;
   std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; }));
   for (auto i: v) std::cout << i << '\n';
}
 5
Author: ecatmur,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-12 14:55:43