21

根据我发现的一些 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()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 之后，它不再指向列表中的第三个元素（之前是最后一个），而是指向第四个元素（现在是最后一个）。

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

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

4

3 回答 3

16

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

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

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

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

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

于 2012-04-10T09:16:57.310 回答
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;
}

除此之外，我们还必须了解 areverse_iterator一般是如何工作的。具体来说， areverse_iterator确实指向取消引用时获得的元素之后的元素。在容器结束之后end()生成一个迭代器——但是对于像数组这样的东西，没有定义的方法来指向容器开始之前的位置。相反，C++ 所做的是让迭代器从末尾开始，然后一直到开头，但是当您取消引用它时，您会在它实际指向的位置之前获得元素。

这意味着您的代码实际上是这样工作的：

在此处输入图像描述

在那之后，你得到了几乎你所期望的，推回 B 然后 A，所以你最终得到了 ABCCCBA。

于 2012-04-10T09:37:07.053 回答
0

尝试对两者都使用迭代器。尝试：

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

并使用 --i 反转

于 2012-04-10T09:00:00.813 回答