Как выполнить итерацию назад по списку 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?
Ответы 5
Используйте reverse_iterator вместо iterator. Используйте rbegin() и rend() вместо begin() и end().
Другая возможность, если вам нравится использовать макрос BOOST_FOREACH, - это использовать макрос BOOST_REVERSE_FOREACH, представленный в Boost 1.36.0.
Документация для итератора и reverse_iterator почти одинакова. итератор двунаправленный, так в чем разница?
Разница в том, что вы по-прежнему используете «++ Iter» для увеличения итератора, а не «--Iter». Или я не прав?
Нет, вы правы, что немного странно увеличивать, чтобы вернуться назад, но также имеет смысл. Хотя reverse_iterator кажется ненужным, учитывая, что итератор двунаправлен. В документации для reverse_iterator говорится, что он действует в обратном списке; конечно, он не меняет внутренний список сначала.
@AlanKey: если вы знаете, что имеете дело со списком, вы можете просто уменьшить обычный итератор. Обратные итераторы становятся самостоятельными, когда вы пишете общий код - им не нужно делать ничего особенного, чтобы просмотреть коллекцию в обратном направлении - им просто нужно дать обратные итераторы
Да, Майк, моим первым подходом было уменьшение обычного итератора, как показано в двух моих примерах. Используя этот метод, я не был уверен, как лучше всего проверить начало списка. Поведение в Windows и Mac оказалось разным.
Не все «прямые» итераторы «двунаправленные». Это зависит от класса коллекции.
@AlanKey: Основное различие в том, что означают конечные точки. iterator :: begin () ссылается на первый элемент, iterator :: end () ссылается на один за последним элементом, reverse_iterator :: rbegin () ссылается на последний элемент, reverse_iterator :: rend () ссылается на один перед первым элементом. При итерации с помощью цикла for удобно иметь возможность увеличивать на единицу после конца коллекции в любом направлении, в котором вы выполняете итерацию, что упрощает использование reverse_iterator, чем перемещение назад через двунаправленный итератор.
Вероятно, вам нужны обратные итераторы. Из памяти:
list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for( ; iter != m_Objs.rend(); ++iter)
{
}
Спасибо, звучит хорошо. Но также кажется пустой тратой создавать специальный reverse_iterator, когда итератор предполагается двунаправленным.
Это должно быть "...> :: reverse_iterator iter = ..."
@AlanKley Я думаю, что цикл for, который вы задали в своем вопросе, в порядке. Причина, по которой я думаю, что это работает, заключается в том, что функция-член .end () возвращает контрольное значение, которое назначается как значение следующего указателя из последнего элемента, а также указатель prev на первом элементе.
К сожалению, перечитайте вопрос ... не работает в Windows. Я также тестировал код на Mac.
Как уже упоминал Ферруччо, используйте reverse_iterator:
for (std::list<int>::reverse_iterator i = s.rbegin(); i != s.rend(); ++i)
Это должно работать:
list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for (; iter!= m_Objs.rend(); iter++)
{
}
Лучший / самый простой способ отменить итерацию списка - это (как уже говорилось) использовать обратные итераторы rbegin / rend.
Однако я хотел упомянуть, что реверсивные итераторы реализованы с сохранением «текущей» позиции итератора по очереди (по крайней мере, в реализации стандартной библиотеки GNU).
Это сделано для упрощения реализации, чтобы диапазон в обратном порядке имел ту же семантику, что и диапазон вперед [начало, конец) и [rbegin, rend)
Это означает, что разыменование итератора включает создание нового временного объекта, а затем его уменьшение, каждый раз:
reference
operator*() const
{
_Iterator __tmp = current;
return *--__tmp;
}
Таким образом, разыменование reverse_iterator медленнее обычного итератора.
Однако вместо этого вы можете использовать обычные двунаправленные итераторы для самостоятельного моделирования обратной итерации, избегая этих накладных расходов:
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 ()!
Посмотрев на это еще раз, возможно, вы захотите просто инициализировать с помощью current = --end (); и оставьте шаг приращения внутри цикла for. Это также защитит от пустого массива, которого нет в моей версии выше. Я пока оставлю оригинал опубликованным, так как я не тестировал.
Я не думаю, что это сработает, если вы также не измените условие цикла. В противном случае вам будет не хватать первого элемента (потому что цикл не будет выполняться, если current == begin())
Первая строка цикла for выполняет декремент, так что да, я думаю. Просто напишите быстрый тест, чтобы попробовать! В любом случае, я больше не думаю, что это лучший способ использования этой идиомы, и некоторые недавние тесты, которые я проводил, больше не показывают заметного улучшения скорости обратного обращения итераторов при полной оптимизации. Тем не менее, стоит все же отметить, что происходит под капотом, и провести соответствующее тестирование!
Я намеревался прокомментировать ваш комментарий, а не ответ, но SO удалил @ -part. Код в вашем ответе работает отлично, однако я согласен, что он может быть не лучшим;) Обновлено: quick тестовое задание
Будет только случайностью реализации, что ваш первый пример (круговой итератор, сравнение с end ()) будет работать.