为什么 std::list 上的 push_back 会更改用 rbegin 初始化的反向迭代器?
根据我发现的一些 STL 文档，在 std::list 中插入或删除元素不会使迭代器失效.这意味着允许循环遍历一个列表(从 begin() 到 end())，然后使用 push_front 添加元素.
According to some STL documentation I found, inserting or deleting elements in an std::list does not invalidate iterators. This means that it is allowed to loop over a list (from begin() to end()), and then add elements using push_front.
例如，在下面的代码中，我用元素 a、b 和 c 初始化一个列表，然后遍历它并执行元素的 push_front.结果应该是cbaabc，这正是我得到的:
E.g., in the following code, I initialize a list with elements a, b and c, then loop over it and perform a push_front of the elements. The result should be cbaabc, which is exactly what I get:
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.但是，我得到了不同的结果:
When I use reverse iterators (loop from rbegin() to rend()) and use push_back, I would expect similar behavior, i.e. a result of abccba. However, I get a different result:
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.
The result is not abccba, but abcccba. That's right there is one additional c added.
看起来第一个 push_back 也改变了用 rbegin() 初始化的迭代器的值.在 push_back 之后，它不再指向列表中的第三个元素(以前是最后一个)，而是指向第四个元素(现在是最后一个).
It looks like the first push_back also changes the value of the iterator that was initialized with rbegin(). After the push_back it does not point anymore to the 3rd element in the list (which was previously the last one), but to the 4th element (which is now the last one).
我使用 Visual Studio 2010 和 GCC 对此进行了测试，两者都返回相同的结果.
I tested this with both Visual Studio 2010 and with GCC and both return the same result.
这是一个错误吗?或者我不知道的反向迭代器的一些奇怪行为?
Is this an error? Or some strange behavior of reverse iterators that I'm not aware of?
推荐答案
标准规定迭代器和引用在插入期间保持有效.它没有说明反向迭代器.:-)
The standard says that iterators and references remain valid during an insert. It doesn't say anything about reverse iterators. :-)
rbegin() 返回的 reverse_iterator 在内部保存了 end() 的值.在 push_back() 之后，这个值显然与之前不同.我认为标准没有说明它应该是什么.明显的替代方案包括列表的前一个最后一个元素，或者如果它是一个固定值(如哨兵节点)，则它留在最后.
The reverse_iterator returned by rbegin() internally holds the value of end(). After a push_back() this value will obviously not be the same as it was before. I don't think the standard says what it should be. Obvious alternatives include the previous last element of the list, or that it stays at the end if that is a fixed value (like a sentinel node).
技术细节:rend() 返回的值不能指向 begin() 之前，因为那是无效的.因此决定 rend() 应该包含 begin() 的值，并且所有其他反向迭代器进一步移动一个位置.operator* 对此进行了补偿，并且无论如何都会访问正确的元素.
Technical details: The value returned by rend() cannot point before begin(), because that is not valid. So it was decided that rend() should contain the value of begin() and all other reverse iterators be shifted one position further. The operator* compensates for this and accesses the correct element anyway.
24.5.1 反向迭代器的第一段说:
First paragraph of 24.5.1 Reverse iterators says:
类模板 reverse_iterator 是一个迭代器适配器，从定义的序列的末尾开始迭代通过其底层迭代器到该序列的开头.反向之间的基本关系迭代器及其对应的迭代器 i 由标识建立:&*(reverse_iterator(i)) == &*(i - 1).
Class template
reverse_iteratoris 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).
相关文章