通过引用相同向量的元素插入向量

Question

我想知道更有经验的人是否能够澄清这是否是对矢量进行的错误操作:

std::vector<int> v{1, 2, 3, 4, 5};
v.insert(v.begin() + 1, v[0]);

我问的原因是因为要插入的元素是对向量中第0个元素的引用.如果插入强制向量调整大小(因为其容量已满),则引用v[0]将无效,并且代码可能会插入不正确的值.这里有一些伪代码可能会证明:

template <typename T>
void vector_insert_method(Iterator pos, const T& value) {
    if capacity full:
        reallocate array and copy over element
        // if value was reference to elem in this vector,
        // that reference might be invalidated


    insert element

    ++size
}

在并发系统上,此问题可能更为现实.

如果您尝试插入在您尝试插入的位置之后的元素,会发生类似且相关的问题.例如,执行类似v.insert(v.begin(), v[2])因为标准指出插入点之后对元素的引用无效.这保证有效吗？

Answer 1

最初的问题是......

[..]这是否是对矢量执行的错误操作:

v.insert(v.begin(), v[0]);
//              ^^^ no + 1 here!

可能是的,它可能是未定义的行为.引用N3337("几乎是C++ 11"AFAIK):

[..]如果没有重新分配,插入点之前的所有迭代器和引用都保持有效.[..]

§23.3.6.5/ 1

虽然这不是读取标准时使用的明确措辞,但我将其解释为:迭代器和插入点之后的引用无效.

因此,v[0]通过调用(*)来使引用无效insert.即使没有重新分配,insert 也必须将所有元素转移到更高的索引(因此v[0]重新定位到v[1]).

假设元素类型是不平凡破坏,那么不管其重新定位是如何完成(通过移动或复制),之后v[1]已经分配/从构造v[0],析构函数v[0]需要被称为(和其寿命结束)之前一新对象(您要插入的对象)可以放在内存位置v[0].因此,这里你的引用变成了一个悬空引用,当它直接用于构造new时会导致未定义的行为v[0].不,据我所知,这个问题可以通过std::vector::insert()不构造新对象而是将新对象分配给 "旧"对象来规避.我不确定是否std::vector需要这样做,尽管它的元素类型必须CopyInsertable提示这可能是这种情况.

更新: 我已经玩了另一个答案中提供的代码,添加了一些打印调试.这说明不是我所期待的(破坏一个元素,然后访问它),但仍显示了标准库的实现(通过ideone这里使用)并没有符合标准:它的插入点之前无效于元素的引用,即使在容量足够大.这样就可以避免上述问题(但打破了标准......所以).

(*):人们可以争论失效何时发生.这个问题的最佳答案是IMO,在调用insert函数之前引用是有效的,并且在从该函数返回后无效(肯定).无效的确切点是未指定的.

编辑过的问题提出了同样的问题,但有一个非常重要的修改:

v.insert(v.begin() + 1, v[0]);
//                ^^^^^

现在这是一个完全不同的情况.由于插入点是"后面",因此引用v[0]不一定会被调用无效.可能出现的唯一问题是如果必须重新分配其内部缓冲区,但在这种情况下,以下操作序列应保证正确的行为:insertv[0]std::vector

1. 分配更大容量的新内存
2. 在新分配的内存区域中构造新元素的正确索引.
3. 将元素从旧(太小)内存复制/移动到新分配的内存区域.
4. 免费旧记忆.