Điều gì sẽ là một triển khai tốt của iota_n (thiếu thuật toán từ STL)

Question

Với C++ 11, STL hiện có chức năng std::iota (xem reference). Ngược lại với std::fill_n, std::generate_n, tuy nhiên, không có std::iota_n. Điều gì sẽ là một thực hiện tốt cho điều đó? Vòng lặp trực tiếp (phương án 1) hoặc ủy quyền cho std::generate_n với biểu thức lambda đơn giản (phương án 2)?

Alternative 1)

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

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

có cả hai lựa chọn thay thế tạo ra mã tương đương với việc tối ưu hóa trình biên dịch?

CẬP NHẬT: kết hợp điểm tuyệt vời của @Marc Mutz cũng trả lại trình lặp tại điểm đích của nó. Đây cũng là cách std::generate_n được cập nhật trong C++ 11 so với C++ 98.

Answer 1

Như một ví dụ ngẫu nhiên, tôi biên soạn đoạn mã sau với 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"); 
} 

Đây iota_n là phiên bản đầu tiên và iota_m thứ hai. Việc lắp ráp là trong cả ba trường hợp này:

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 

Với -O3, ba phiên bản cũng rất giống nhau, nhưng một nhiều lâu hơn (sử dụng di chuyển có điều kiện và punpcklqdq và như vậy tương tự).

Answer 2

Bạn quá tập trung vào việc tạo mã mà bạn quên để có được giao diện đúng.

Bạn yêu cầu chính xác OutputIterator, nhưng điều gì sẽ xảy ra nếu bạn muốn gọi nó lần thứ hai?

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

bên iota_n, bạn vẫn biết bạn đang ở đâu, nhưng bạn đã ném thông tin mà đi, vì vậy người gọi không thể nhận được vào nó trong thời gian liên tục.

Nguyên tắc chung: không vứt bỏ thông tin hữu ích.

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

Với định nghĩa này, ví dụ trên trở nên đơn giản:

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