什么是iota_n的好实现（缺少STL算法）

Question

使用C++ 11，STL现在具有std::iota函数（请参阅reference）。然而，与std::fill_n,std::generate_n相反，没有std::iota_n。这将是一个很好的实施？使用简单的lambda表达式（备选方案2）直接循环（备选方案1）或委托给std::generate_n？

备选1）

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

备选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++; }); 
}  

会两个替代方案产生具有优化编译器的等效代码？

UPDATE：结合了@Marc Mutz的优点，也可以在目标点返回迭代器。与C++ 98相比，这也是如何在C++ 11中更新std::generate_n。

Answer 1

作为随机例如，我编译下面的代码与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"); 
} 

这里iota_n是第一版本和iota_m第二。该组件在所有三种情况是：

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 

随着-O3，三个版本也非常相似，但很多更长（使用条件的动作和punpcklqdq以及诸如此类）。

Answer 2

你很专注于代码生成，你忘记了正确的界面。

你正确地要求OutputIterator，但如果你想第二次调用它，会发生什么？

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

内iota_n，你还知道你在哪里，但你抛出的信息了，所以在固定时间调用者不能得到它。

一般原理：不要扔掉有用的信息。

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

根据这个定义，上面的例子简单地变为：

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