为什么在std::list上执行push_back操作会改变用rbegin初始化的反向迭代器？

Question

为什么在std::list上执行push_back操作会改变用rbegin初始化的反向迭代器？

22

根据我找到的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都测试过，两者都返回相同的结果。

这是一个错误吗？还是我不知道的reverse iterators的一些奇怪行为？

- Patrick

3个回答

7

我认为要理解这个问题，最好的方法是将 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++ 的解决方法是从结束位置开始迭代，直到到达开始位置，但是当您进行解引用时，实际上获取的是指针所在位置的前一个元素。

这意味着您的代码实际上像这样运行：

enter image description here

之后，您会得到您期望的结果，将 B 和 A 推回去，最终得到 ABCCCBA。

- Jerry Coffin

你能指出规范，或者甚至是一个参考网站，说明反向迭代器是这样工作的吗？（如果没有，这并不一定意味着解释是错误的，但如果它不是错误的话，那就是一个实现 bug） - user253751

@immibis: §[reverse.iterators]/1："反向迭代器与其对应的迭代器i之间的基本关系由以下等式确定：&(reverse_iterator(i)) == &(i - 1)。" - Jerry Coffin

0

尝试同时使用迭代器。尝试：

std::list<std::string>::iterator i = testList.end();

使用 --i 进行反向遍历

- ldgorman

我不是在寻找替代方案。我想知道为什么反向迭代器突然指向其他内容，因为这似乎与文档（请参见http://www.sgi.com/tech/stl/List.html）中的描述相矛盾。 - Patrick

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bo Persson · Accepted Answer

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

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

技术细节：由于指向 begin() 之前是不合法的，所以决定 rend() 应该包含 begin() 的值，而所有其他反向迭代器都要向前移动一个位置。 operator* 补偿这一点，仍然可以访问正确的元素。

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

类模板 reverse_iterator 是一个迭代器适配器，以其基础迭代器定义的序列的结尾为起点，向该序列的开头迭代。反向迭代器与其相应迭代器 i 之间的基本关系由以下公式确定：
&*(reverse_iterator(i)) == &*(i - 1)。