您如何通过一个STL列表进行反向迭代?

I'm writing some cross-platform code between Windows and Mac.

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

If list::end() "returns an iterator that addresses the location succeeding the last element in a list" and can be checked when traversing a list forward, what is the best way to traverse backwards?

如果列表::结束()“返回一个迭代器，该迭代器处理列表中最后一个元素的位置”，并且可以在向前遍历列表时进行检查，向后遍历最好的方法是什么?

This code workson the Mac but not on Windows (can't decrement beyond first element):

这段代码可以在Mac上运行，但不能在Windows上运行(不能在第一个元素之外衰减):

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

this works on Windows:

这是在Windows上:

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

Is there another way to traverse backward that could be implemented in a for loop?

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

5 个解决方案

#1

Use reverse_iterator instead of iterator. Use rbegin() & rend() instead of begin() & end().

使用reverse_iterator代替iterator。使用rbegin()和rend()而不是begin()和end()。

Another possibility, if you like using the BOOST_FOREACH macro is to use the BOOST_REVERSE_FOREACH macro introduced in Boost 1.36.0.

如果您喜欢使用BOOST_FOREACH宏，还可以使用Boost 1.36.0中引入的BOOST_REVERSE_FOREACH宏。

#2

The best/easiest way to reverse iterate a list is (as already stated) to use reverse iterators rbegin/rend.

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

However, I did want to mention that reverse iterators are implemented storing the "current" iterator position off-by-one (at least on the GNU implementation of the standard library).

但是，我确实想提到反向迭代器的实现是将“当前”迭代器位置逐个存储(至少在标准库的GNU实现上)。

This is done to simplify the implementation, in order for the range in reverse to have the same semantics as a range forward [begin, end) and [rbegin, rend)

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

What this means is that dereferencing an iterator involves creating a new temporary, and then decrementing it, each and every time:

这意味着取消对迭代器的引用涉及到创建一个新的临时器，然后每次都对它进行降级:

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

Thus, dereferencing a reverse_iterator is slower than an normal iterator.

因此，取消一个reverse_iterator比普通的迭代器要慢。

However, You can instead use the regular bidirectional iterators to simulate reverse iteration yourself, avoiding this overhead:

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

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

Testing showed this solution to be ~5 times faster for each dereference used in the body of the loop.

测试表明，对于循环体中使用的每一个取消引用，这个解决方案的速度要快5倍。

Note: Testing was not done with the code above, as that std::cout would have been the bottleneck.

注意:上面的代码没有进行测试，因为std::cout会成为瓶颈。

Also Note: the 'wall clock time' difference was ~5 seconds with a std::list size of 10 million elements. So, realistically, unless the size of your data is that large, just stick to rbegin() rend()!

同样注意:“挂钟时间”的差异是在std的5秒内::列表大小为1000万元素。因此，实际上，除非数据的大小是这么大，否则只需坚持使用rbegin() rend()!

#3

You probably want the reverse iterators. From memory:

您可能需要反向迭代器。从内存:

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

#4

As already mentioned by Ferruccio, use reverse_iterator:

正如Ferruccio所提到的，使用reverse_iterator:

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

#5

This should work:

这应该工作:

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

#1