Как вы перебираете список 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 вместо итератора. Используйте rbegin () & rend () вместо begin () & end ().

Другая возможность, если вам нравится использовать макрос BOOST_FOREACH , это использовать макрос BOOST_REVERSE_FOREACH, представленный в Boost 1.36.0.

Answer 2

Лучший / самый простой способ выполнить итерацию в обратном порядке - это (как уже было сказано) использовать обратные итераторы rbegin / rend.

Однако я хотел бы упомянуть, что обратные итераторы реализованы с сохранением «текущей» позиции итератора по одному (по крайней мере, в реализации стандартной библиотеки GNU).

Это сделано для упрощения реализации, чтобы обратный диапазон имел ту же семантику, что и диапазон вперед [начало, конец) и [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 был бы узким местом.

Также обратите внимание: разница «время настенных часов» составляла ~ 5 секунд при размере std :: list в 10 миллионов элементов. Таким образом, на самом деле, если размер ваших данных не настолько велик, просто придерживайтесь rbegin () rend ()!

Answer 3

Возможно, вам нужны обратные итераторы. По памяти:

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

Answer 4

Это должно работать:

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

Answer 5

Как уже упоминал Ферруччо, используйте reverse_iterator:

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