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());