c++ - 为什么 std::list 上的 push_back 会更改用 rbegin 初始化的反向迭代器？

Question

根据我发现的一些 STL 文档，在 std::list 中插入或删除元素不会使迭代器无效。这意味着它可以遍历一个列表(从 begin() 到 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() 到 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 之后，它不再指向列表中的第三个元素(之前是最后一个)，而是指向第四个元素(现在是最后一个)。

我使用 Visual Studio 2010 和 GCC 对此进行了测试，都返回了相同的结果。

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

Answer 1

标准规定迭代器和引用在插入期间保持有效。它没有说明反向迭代器。 :-)

rbegin() 返回的reverse_iterator 内部保存着end() 的值。在 push_back() 之后，这个值显然与之前不同。我认为标准没有说明它应该是什么。明显的替代方案包括列表的前一个最后一个元素，或者如果它是一个固定值(如哨兵节点)，它会停留在末尾。

---

技术细节:rend() 返回的值不能指向begin() 之前，因为那是无效的。所以决定 rend() 应该包含 begin() 的值，并且所有其他反向迭代器被移动一个位置。 operator* 对此进行了补偿并访问了正确的元素。

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

Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence. The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity:
&*(reverse_iterator(i)) == &*(i - 1).