9

在处理 C++ 标准库容器(如std::vector)时,它们的基于范围的插入方法如何使用引用向量自身内容的迭代器来处理用户?

据推测,如果他们已经说过vector::iterator,那么实现可以特例这种情况,但如果它们是最终导致访问向量的用户定义类型,那么向量如何处理在评估范围时保持这些迭代器有效?标准是否只是禁止引用范围内的向量?

举个简单的例子,考虑一个 value_type 为 size_t 的迭代器,取消引用它的结果是插入的向量的大小。

struct silly_iterator {
    vector<std::size_t>* v;
    unsigned number;
    std::size_t operator*() { return v->size(); }
    operator++() { --number; }
    bool operator==(silly_iterator other) const { return number == 0; }
    // other methods
};
std::vector<std::size_t> vec = { 3, 4, 5, 6, 7 };
vector.insert(vector.begin() + 2, silly_iterator(&vec, 10), silly_iterator());

vec这段代码执行后的内容是什么?

再举一个例子,

struct silly_iterator { 
    std::vector<std::size_t>* v; 
    std::size_t operator*() { return 0; } 
    operator++() { --number; v->push_back((*v)[4]); } 
    bool operator==(silly_iterator other) const { return number == 0; } 
    // other methods 
}; 
std::vector<std::size_t> vec = { 3, 4, 5, 6, 7 }; 
vec.insert(vec.begin() + 2, silly_iterator(&vec, 10), silly_iterator());
4

2 回答 2

1

基本上,使向量的迭代器/引用无效的唯一原因是重新分配,否则您仍然指向向量的某些部分。

C++11 23.3.6.3/5:

备注:重新分配使所有引用序列中元素的引用、指针和迭代器无效。保证在调用 reserve() 之后发生的插入期间不会发生重新分配,直到插入会使向量的大小大于 capacity() 的值。

这在插入函数 C++11 23.3.6.5/1 的注释中再次重申:

备注:如果新大小大于旧容量,则导致重新分配。如果没有发生重新分配,则插入点之前的所有迭代器和引用仍然有效。[...]

使用vector,您可以认为迭代器的行为与指针非常相似(这说明了为什么重新分配会导致问题)。事实上,根据标准的定义,reference类型是value_type&,表明引用确实没有被包装。

请注意,迭代器的目标可能会因插入而改变,因为基础数据会发生变化。此外,为了符合标准,您需要确保不会发生重新分配(例如,调用reserve)。

于 2013-05-13T06:54:13.530 回答
1

在表 100 中的 C++11 n3242(有点旧的草案)中,23.2.3我们了解到对于迭代器对insert函数,pre: i and j are not iterators into a. 我相信基于该措辞,我会选择将其广泛解释为i and j shall not access a,并且您的两个迭代器都是未定义的行为。

但是,假设我的广义解释不是标准的意图。然后回答您的问题,对于输入迭代器,结果几乎肯定会是:3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 5, 6, 7而对于前向迭代器或更好的迭代器之一3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 73, 4, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 5, 6, 7取决于在将元素复制到开放空间之前还是之后更新大小。在这种情况下,我看不到任何地方会指定前向迭代器的结果。

于 2013-05-13T23:56:55.447 回答