11

在 C++11 中，STL 现在有了一个std::iota函数（参见参考资料）。然而，与 , 相比std::fill_n，std::generate_n没有std::iota_n。什么是一个好的实现呢？std::generate_n直接循环（备选方案 1）或使用简单 lambda 表达式（备选方案 2）的委托？

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

两种替代方案都会通过优化编译器生成等效代码吗？

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

4

4 回答 4

10

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等）。

于 2012-08-01T21:26:35.133 回答
3

您太专注于代码生成，以至于忘记了正确的接口。

您正确 require 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());
于 2015-03-09T09:47:02.593 回答
1

一个假设的iota_n

std::iota_n(first, count, value)

可以用一个衬里代替。

std::generate_n(first, count, [v=value]()mutable{return v++;})

我更喜欢它有一个不在标准中的挥之不去的功能。话虽如此，我认为 astd::iota_n应该在标准中。

于 2019-09-18T05:24:01.600 回答
0

可能将 back_insertor 与 std::generate_n 一起使用，这样可以避免预先分配集合。

vector<int> v3;
generate_n(back_inserter(v3),10,[i=1]() mutable{
    return i++;
});

我们可以把它换成 iota_n 直到我们得到 iota_n :)

于 2021-07-26T11:04:28.773 回答