Как вы перебираете назад через список STL?

Я пишу кросс-платформенный код между 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?

Ответы

Ответ 1

Используйте reverse_iterator вместо итератора. Используйте rbegin() и rend() вместо begin() и end().

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

Ответ 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()!

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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