1

回答如何自我复制向量？让我对迭代器失效感到有些困惑。一些文献说“如果您使用 insert、push_back 等，请考虑所有迭代器无效”。很明显，它可能会导致向量增长，从而使迭代器无效。我知道会有足够空间的特殊情况呢？

第一次尝试：

myvec.reserve(myvec.size()*3);  //does this protect me from iterator invalidation?
vector<string>::iterator it = myvec.end();    
myvec.insert(myvec.end(), myvec.begin(), it);
myvec.insert(myvec.end(), myvec.begin(), it);

经过一些出色的答案后，第二次尝试：

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);

经过更优秀的答案第三次尝试：

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
back_insert_iterator< vector<string> > back_it (myvec);
copy (myvec.begin(),myvec.begin()+size,back_it);
copy (myvec.begin(),myvec.begin()+size,back_it);

这句话来自 Josuttis 的“C++ 标准库参考”：

插入或删除元素会使引用以下元素的引用、指针和迭代器无效。如果插入导致重新分配，它会使所有引用、迭代器和指针无效。

表明我的代码是安全且已定义的行为。标准中是否有段落可以保证这一点？

4

3 回答 3

7

过去的迭代器总是有点特别。我会小心的。标准是这样说的（23.3.6.5）：

如果没有发生重新分配，则插入点之前的所有迭代器和引用仍然有效。

这里的关键是“在插入点之前”。由于您的原件it不在插入点之前（因为它是插入点），所以我不会相信它仍然有效。

于 2013-02-11T21:11:50.310 回答
2

尽管只要不超过容量，插入向量确实不会导致重新分配，并且不会使插入点之前end()的元素的迭代器无效（这可以说是 的情况，正如@KerrekSB 指出的那样）， C++11 标准的表 100（第 23.2.3 段）为序列容器的函数指定了以下先决条件：a.insert(p,i,j)

[...] pre：i 和 j 不是 a 的迭代器。[...]

在您的情况下，它们显然是，这让我认为该程序具有未定义的行为。

于 2013-02-11T21:14:34.093 回答
0

迭代器不应在中间函数中失效。内存可能被重新定位的想法并不成立，因为您不能realloc在具有非平凡构造函数的对象上使用。即使构造不是问题，在最坏的情况下它仍然必须复制初始序列两次，从而抵消了平均情况下的任何好处。

重点是，以这种方式实现它是没有意义的；an alloc, copy,free几乎可以肯定地完成了，不管标准怎么说。

这是安全的，因为v.begin()并且v.end()始终是最新的。

v.insert(v.end(), v.begin(), v.end());
v.insert(v.end(), v.begin(), v.end());

这不是。

vector<foo>::iterator i = v.begin();
vector<foo>::iterator j = v.end();
v.insert(v.end(), i, j);
v.insert(v.end(), i, j);

但是，自插入可能会很不稳定。在 GCC 下尝试以下操作。只有当有足够的内存可用时，自我插入才会给出不正确的结果（不确定这是否是一个错误）。

int main()
{
    int position = 1, first = 2, last = 3;
    // enforce error condition.
    assert(position < first);
    int size = 8;
    // sanity check.
    assert(first < last && last <= size);

    std::vector<int> right, wrong;
    // force resize during insertion.
    right.reserve(size);
    // avoid resize during insertion.
    wrong.reserve(size + (last - first));

    for ( int i = 0; i < size; i++ )
     {
       right.push_back(i);
       wrong.push_back(i);
     }

    std::vector<int>::iterator i;
    i = right.begin();
    right.insert(i + position, i + first, i + last);
    i = wrong.begin();
    wrong.insert(i + position, i + first, i + last);

    assert(right == wrong);
    return 0;
}

注意：上述意见适用于vector特定的容器，而不是一般的容器。此外，上述行为可能是错误的建议与标准无关，而是为vector.

于 2014-05-04T04:55:35.207 回答