Quale sarebbe una buona implementazione di iota_n (algoritmo mancante da STL)

Question

Con C++ 11, l'STL ha ora una funzione std::iota (vedere uno reference). A differenza di std::fill_n, std::generate_n, tuttavia, non esiste lo std::iota_n. Quale sarebbe una buona implementazione per questo? Un ciclo diretto (alternativa 1) o delega a std::generate_n con un'espressione lambda semplice (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++; }); 
}  

Sarebbe entrambe le alternative generare il codice equivalente con l'ottimizzazione dei compilatori?

UPDATE: ha incorporato l'eccellente punto di @Marc Mutz per restituire l'iteratore nel punto di destinazione. Questo è anche il modo in cui std::generate_n viene aggiornato in C++ 11 rispetto a C++ 98.

Answer 1

Come esempio casuale, ho compilato il seguente codice 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"); 
} 

Qui iota_n è la prima versione e iota_m il secondo. Il montaggio è in tutti e tre i casi questo:

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, le tre versioni sono molto simili, ma un sacco più (usando mosse condizionate e punpcklqdq e simili).

Answer 2

Sei così concentrato sulla generazione del codice che hai dimenticato di avere l'interfaccia giusta.

L'utente richiede correttamente OutputIterator, ma cosa succede se si desidera richiamarlo una seconda volta?

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

all'interno iota_n, è ancora sapere dove sei, ma hai buttato quelle informazioni via, in modo che il chiamante non può ottenere a esso in tempo costante.

Principio generale: non gettare informazioni utili.

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 questa definizione, l'esempio precedente diventa semplicemente:

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