libreria - stl c++ español

¿Cuál sería una buena implementación de iota_n(algoritmo faltante del STL)

Question

Con C ++ 11, el STL ahora tiene una función std::iota (ver una referencia ). A diferencia de std::fill_n , std::generate_n , no existe std::iota_n , sin embargo. ¿Cuál sería una buena implementación para eso? ¿Un bucle directo (alternativa 1) o delegación a std::generate_n con una expresión lambda simple (alternativa 2)?

Alternativa 1)

template<class OutputIterator, class Size, class T>
OutputIterator iota_n(OutputIterator first, Size n, T value)
{
while (n--)
*first++ = value++;
return first;
}

Alternativa 2)

template<class OutputIterator, class Size, class T>
OutputIterator iota_n(OutputIterator first, Size n, T value)
{
return std::generate_n(first, n, [&](){ return value++; });
} 

¿Ambas alternativas generarían un código equivalente con la optimización de compiladores?

ACTUALIZACIÓN : incorporó el excelente punto de @Marc Mutz para devolver también el iterador en su punto de destino. Esta es también la forma en que std::generate_n se actualizó en C ++ 11 en comparación con C ++ 98.

Answer 1

Como ejemplo al azar, compilé el siguiente código con g++ -S -O2 -masm=intel (GCC 4.7.1, x86_32):

void fill_it_up(int n, int * p, int val)
{
asm volatile("DEBUG1");
iota_n(p, n, val);
asm volatile("DEBUG2");
iota_m(p, n, val);
asm volatile("DEBUG3");
for (int i = 0; i != n; ++i) { *p++ = val++; }
asm volatile("DEBUG4");
}

Aquí iota_n es la primera versión y iota_m la segunda. El conjunto está en los tres casos esto:

 test edi, edi
jle .L4
mov edx, eax
neg edx
lea ebx, [esi+edx*4]
mov edx, eax
lea ebp, [edi+eax]
.p2align 4,,7
.p2align 3
.L9:
lea ecx, [edx+1]
cmp ecx, ebp
mov DWORD PTR [ebx-4+ecx*4], edx
mov edx, ecx
jne .L9

Con -O3 , las tres versiones son también muy similares, pero mucho más largas (usando movimientos condicionales y punpcklqdq y similares).

Answer 2

Estás tan enfocado en la generación de código que olvidaste tener la interfaz correcta.

Necesita correctamente OutputIterator , pero ¿qué ocurre si desea llamarlo por segunda vez?

list<double> list(2 * N);
iota_n(list.begin(), N, 0);
// umm...
iota_n(list.begin() + N, N, 0); // doesn''t compile!
iota_n(list.rbegin(), N, 0); // works, but create 0..N,N-1..0, not 0..N,0..N
auto it = list.begin();
std::advance(it, N);
iota_n(it, N, 0); // works, but ... yuck and ... slow (O(N))

dentro de iota_n , todavía sabes dónde estás, pero has descartado esa información, por lo que la persona que llama no puede acceder a ella en un tiempo constante.

Principio general: no deseche la información útil.

template <typename OutputIterator, typename SizeType, typename ValueType>
auto iota_n(OutputIterator dest, SizeType N, ValueType value) {
while (N) {
*dest = value;
++dest;
++value;
--N;
}
// now, what do we know that the caller might not know?
// N? No, it''s zero.
// value? Maybe, but it''s just his value + his N
// dest? Definitely. Caller cannot easily compute his dest + his N (O(N))
// So, return it:
return dest;
}

Con esta definición, el ejemplo anterior se convierte simplemente en:

list<double> list(2 * N);
auto it = iota_n(list.begin(), N, 0);
auto end = iota_n(it, N, 0);
assert(end == list.end());