如何向后迭代 STL 列表？

Question

我正在编写一些 Windows 和 Mac 之间的跨平台代码。

如果 list::end() “返回一个迭代器，该迭代器寻址列表中最后一个元素之后的位置”并且可以在向前遍历列表时进行检查，那么向后遍历列表的最佳方法是什么？

此代码适用于 Mac，但不适用于 Windows（不能递减超出第一个元素）：

list<DVFGfxObj*>::iterator iter = m_Objs.end();
for (iter--; iter!=m_Objs.end(); iter--)// By accident discovered that the iterator is circular ?
{}

这适用于 Windows：

list<DVFGfxObj*>::iterator iter = m_Objs.end();
do{
    iter--;
} while (*iter != *m_Objs.begin());

是否有另一种可以在 for 循环中实现的向后遍历方法？

Answer 1

使用 reverse_iterator 而不是 iterator。
使用 rbegin() 和 rend() 而不是 begin() & 结束()。

另一种可能性，如果您喜欢使用 BOOST_FOREACH宏是使用 Boost 1.36.0 中引入的 BOOST_REVERSE_FOREACH 宏。

Answer 2

反向迭代列表的最佳/最简单方法是（如前所述）使用反向迭代器 rbegin/rend。

然而，我确实想提一下，反向迭代器的实现是逐一存储“当前”迭代器位置（至少在标准库的 GNU 实现上）。

这样做是为了简化实现，以便反向范围具有与正向范围 [begin, end) 和 [rbegin, rend) 相同的语义。

这意味着取消引用迭代器涉及创建一个新的临时值，并且然后递减它，每次：

  reference
  operator*() const
  {
_Iterator __tmp = current;
return *--__tmp;
  }

因此，取消引用反向迭代器比普通迭代器慢。

但是，您可以使用常规双向迭代器自己模拟反向迭代，避免这种开销：

for ( iterator current = end() ; current != begin() ; /* Do nothing */ )
{
    --current; // Unfortunately, you now need this here
    /* Do work */
    cout << *current << endl;
}

测试表明，对于循环体中使用的每次取消引用，此解决方案的速度大约快 5 倍。

注意：上面的代码没有进行测试，因为 std::cout 可能是瓶颈。

另请注意：当 std::list 大小为 1000 万个元素时，“挂钟时间”差异约为 5 秒。 所以，实际上，除非你的数据量很大，否则就坚持使用 rbegin() rend()！

Answer 3

您可能需要反向迭代器。 从记忆里：

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for( ; iter != m_Objs.rend(); ++iter)
{
}

Answer 4

正如Ferruccio 已经提到的，使用reverse_iterator：

for (std::list<int>::reverse_iterator i = s.rbegin(); i != s.rend(); ++i)

Answer 5

这应该有效：

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for (; iter!= m_Objs.rend(); iter++)
{
}