std::vector::reserve 是否保证在这种情况下实现不会使迭代器无效？

Question

这是一个函数，它打算：

a) 接受一个整数向量

b) 对于输入向量中的每个整数，追加该整数的倒数

先决条件：none

后置条件：返回向量的 size() 正好是 2 * 输入向量的大小。

请注意，向量已就地修改。

问题：

此函数是否严格定义了转换期间迭代器失效的行为？

奖金：

有better/moresuccinct/robust的写法吗？

代码：

std::vector<int> append_negatives(std::vector<int> v)
{
    v.reserve(v.size() * 2);
    std::transform(begin(v), end(v), 
                   back_inserter(v), 
                   [](auto&& x) { return -x; });
    return v;
}

Answer 1

只要您不超过预分配的容量，就不应发生重新分配，并且引用向量项的引用或迭代器不应失效。但是，由于 end() 返回的迭代器未引用任何向量项，因此它可能仍会失效。

23.3.11.3 vector capacity [vector.capacity]

...No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity()

...

23.3.11.5 vector modifiers [vector.modifiers]

...If no reallocation happens, all the iterators and references before the insertion point remain valid.

Answer 2

关于迭代器失效规则的部分已经介绍过了，所以我会借此机会谦虚地质疑是否需要使用所有这些机制（及其微妙的规则）来解决这样一个微不足道的问题。您也可以认为这是

Bonus:

Is there a better/more succinct/robust way to write it?

部分问题。

老实说，我会用 for 循环的先进技术完全回避这个问题。 KISS!

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz*2);
    for(size_t i = 0; i < sz; ++i) v[i+sz] = -v[i];
    return v;
}

并不是所有的东西都必须在 STL 算法的深层掩护下进行混淆。这既更短，IMO 更具可读性，又避免了迭代器失效带来的麻烦。

此外，除非自从我上次检查以来编译器变得更加聪明，否则这会明显更快，因为避免了 push_back 的所有开销（检查容量是否足够并在每次迭代时增加大小），这替换为直接指针访问（一个汇编指令）；纤细而简单的环体为自动展开提供了更好的机会。我希望这也能更快地编译，因为我们避免实例化一堆模板。

请注意，速度 advantage/no 失效问题即使是 transform 恩人也可以获得：

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz * 2);
    auto beg = begin(v);
    std::transform(beg, beg + sz, beg + sz, 
                   [](int x) { return -x; });
    return v;
}

但是我看不出这种过于冗长的代码比普通的 for 循环有什么优势，除非你通过 "cool" C++ 功能的数量支付你设法挤进你的代码。

@MikeMB 询问默认构造成本高的类型；在这种情况下，显式 push_back 就可以了：

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.reserve(sz*2); // optional
    for(size_t i = 0; i < sz; ++i) v.push_back(-v[i]);
    return v;
}

如果原始 post 中的 transform 有效，您还可以使用基于范围的 for 循环：

std::vector<int> append_negatives(std::vector<int> v) {
    v.reserve(v.size()*2);
    for(int &x: v) v.push_back(x);
    return v;
}

方式比基于变换的解决方案更美观，但我在评论中看到对于结束迭代器失效仍然没有达成共识，所以这将是一样无效。

std::vector::reserve 是否保证在这种情况下实现不会使迭代器无效？

Does std::vector::reserve guarantee that the implementation will not invalidate iterators in this case?

c++

stdvector

language-lawyer

c++11

问题：

奖金：

代码：

Bonus: