c++ - 通过引用同一 vector 的元素插入 vector

Question

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

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

我问的原因是因为要插入的元素是对 vector 中第 0 个元素的引用。如果插入强制 vector 调整大小(因为它的容量已满)，那么对 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

原来的问题问...

[..] whether this is a buggy operation to do on a vector:

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

可能是的，它可能是未定义的行为。报价 N3337 (“几乎 C++11”AFAIK):

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

§23.3.6.5/1

虽然这不是阅读标准时所习惯的清晰措辞，但我将其解释为:迭代器和对插入点及其之后的引用无效。

因此，对 v[0] 的引用因对 insert 的调用 (*) 而无效。即使没有发生重新分配，insert 必须将所有元素移动到更高的索引(因此 v[0] 重新定位到 v[1])。

假设元素类型不是可轻易破坏，那么无论如何重新定位(通过移动或复制)，在 v[ 1] 已从 v[0] 分配/构造，需要调用 v[0] 的析构函数(并且其生命周期已结束)before 一个新对象(您要插入的对象)可以放置在 v[0] 的内存位置。因此，在这里您的引用变成了一个悬空引用，当它被直接用于构造新的 v[0] 时，这会导致未定义的行为。不，据我所知，可以通过 std::vector::insert() 而不是 construct 新对象而是 assign 来规避这个问题 新对象到“旧”对象。我不确定是否需要 std::vector 以这种方式运行，尽管它的元素类型必须是 CopyInsertable 暗示这可能是这种情况.

更新: I've played around with the code在另一个答案中提供，添加了一些打印调试。这表明不是我所期望的(破坏一个元素然后访问它)但仍然表明标准库实现(这里由 ideone 使用)确实不是 符合标准:它使对插入点之前的元素的引用无效即使容量足够大。这样它就绕过了上述问题(但违反了标准......所以)。

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

---

编辑后的问题提出了同样的问题，但做了一个极其重要的修改:

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

现在情况完全不同了。对 v[0] 的引用不一定会因调用 insert 而无效，因为插入点在“后面”v[0]。唯一可能出现的问题是如果 std::vector 必须重新分配其内部缓冲区，但在这种情况下，以下操作序列应该保证正确的行为:

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