为什么std :: list上的push_back改变了用rbegin初始化的反向迭代器？

Question

根据我发现的一些STL文档,在std :: list中插入或删除元素不会使迭代器失效.这意味着允许循环遍历列表(从begin()to end()),然后使用push_front添加元素.

例如,在下面的代码中,我使用元素a,b和c初始化一个列表,然后遍历它并执行元素的push_front.结果应该是cbaabc,这正是我得到的:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::iterator itList = testList.begin(); itList != testList.end(); ++itList)
   testList.push_front(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

当我使用反向迭代器(从rbegin()to 循环rend())并使用push_back时,我会期望类似的行为,即abccba的结果.但是,我得到了不同的结果:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::reverse_iterator itList = testList.rbegin(); itList != testList.rend(); ++itList)
   testList.push_back(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

结果不是abccba,但是abcccba.这是正确的,还有一个额外的c.

看起来第一个push_back也改变了用rbegin()初始化的迭代器的值.在push_back之后,它不再指向列表中的第3个元素(之前是最后一个元素),而是指向第4个元素(现在是最后一个元素).

我使用Visual Studio 2010和GCC对它进行了测试,两者都返回相同的结果.

这是一个错误吗？或者反向迭代器的一些奇怪的行为,我不知道？

Answer 1

该标准表示插入过程中迭代器和引用仍然有效.它没有说反向迭代器.:-)

在reverse_iterator通过返回rbegin()内部保存的价值end().经过push_back()这个值显然不会,因为它以前一样.我不认为标准说它应该是什么.明显的替代方案包括列表的前一个最后一个元素,或者如果它是固定值(如sentinel节点)则保留在结尾.

技术细节:返回的值rend()不能指向之前begin(),因为它无效.所以决定rend()应该包含值,begin()并将所有其他反向迭代器进一步移位一个位置.operator*无论如何,补偿这一点并访问正确的元素.

24.5.1反向迭代器的第一段说:

类模板reverse_iterator是一个迭代器适配器,它从其底层迭代器定义的序列的末尾迭代到该序列的开头.反向迭代器与其对应的迭代器之间的基本关系由身份建立:
&*(reverse_iterator(i)) == &*(i - 1).

Answer 2

我想要理解这一点,最好先将for循环重新构建为while循环:

typedef std::list<std::string> container;

container testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

container::reverse_iterator itList = testList.rbegin(); 
while (itList != testList.rend()) {
    testList.push_back(*itList);
     ++itList;
}

与此同时,我们必须了解reverse_iterator一般的工作方式.具体来说一个reverse_iterator真正指向的元素后,你当你取消对它的引用的一个.在容器结束之后end()产生一个迭代器- 但对于像数组这样的东西,没有定义的方法指向容器的开头之前.相反,C++所做的就是让迭代器从结束后开始,然后进行到开始,但是当你取消引用它时,你会在它实际指向的位置之前得到它.

这意味着你的代码实际上是这样的:

在那之后,你得到了你所期望的,推回B然后A,所以你最终得到了ABCCCBA.