Согласованность при удалении элементов из мультииндекса повышения с помощью итератора

Я знаю, что следующий код неверен для std::vectors и вообще для всех контейнеров STL:

std::vector<something>::iterator it = array.begin();
for(; it != array.end(); it++) {
   ...
   array.erase(it);
   ...
}

потому что итератор необходимо обновить после стирания и элемента.

Мне было интересно, то же самое для мультииндекса повышения, например, будет ли что-то вроде следующего правильным или нет:

my_index::iterator it = index.get<0>().begin();
for(; it != index.get<0>().end(); it++) {
   ...
   index.erase(it);
   ...
}

Я хотел бы убедиться, что хорошо понял следующий абзац документации: http://www.boost.org/doc/libs/1_51_0/libs/multi_index/doc/tutorial/indices.html#гарантирует, в котором, кажется, говорится, что я могу стереть без делает итератор недействительным. Однако я не уверен, что из-за того, что я удаляю элемент, другой элемент, который я должен посетить во время итерации, может быть перемещен перед текущей позицией итератора и никогда не будет посещен (другими словами, путем стирания некоторых элементов во время итерации, я все еще уверен, что пройду все элементы?).

Спасибо!


c++ boost iterator boost-multi-index
person sunmat    schedule 22.10.2012    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Связанный вами абзац применяется только к хэшированным (неупорядоченным) индексам. В нем указано, что при вставке новых элементов итераторы хэшированного индекса остаются действительными.

При стирании для упорядоченных индексов вы всегда можете гарантировать полную итерацию, используя возвращаемое значение из erase:

for (; it != index.get<0>().end(); ) {
    if (...) it = index.erase(it);
    else ++it;
}

Это также будет работать для хешированных (неупорядоченных) индексов, поскольку порядок итерации стабилен при стирании элементов.

person ecatmur    schedule 22.10.2012

arrow_upward
3
arrow_downward

Нет, ваше действие недействительно в индексе повышения. Итераторы, стертые из коллекции, никогда не остаются действительными, что может оставаться действительным, так это другие итераторы в коллекции, если вы где-то их храните.

Собственно текст такой:

Гарантии валидности итератора и безопасности исключений

Из-за внутренних ограничений, налагаемых платформой Boost.MultiIndex, хешированные индексы обеспечивают гарантии достоверности итератора и безопасности исключений, которые на самом деле более сильны, чем требуется в Техническом отчете стандартной библиотеки C++ (TR1) в отношении неупорядоченных ассоциативных контейнеров:

Действительность итератора сохраняется в любом случае во время вставки или повторного хэширования: TR1 допускает аннулирование итератора при выполнении повторного хеширования (неявного или явного). Стирание элемента или диапазона элементов с помощью итераторов никогда не вызывает исключение, так как внутренняя хеш-функция и объекты-предикаты равенства фактически не вызываются. rehash безоговорочно обеспечивает сильную гарантию безопасности исключений.

TR1 гарантирует это только в том случае, если внутренняя хэш-функция и объекты-предикаты равенства не вызывают исключения. Несколько неожиданным последствием является то, что неупорядоченный ассоциативный контейнер, совместимый с TR1, может стереть элементы, если во время повторного хеширования возникнет исключение! В общем, эти более сильные гарантии играют в пользу удобства пользователя, особенно то, что относится к стабильности итератора. Однако снижение производительности (надеюсь, минимальное) может привести к обмену на эти товары.

person CashCow    schedule 22.10.2012
comment
Означает ли это, что если я создам копию исходного итератора, эта копия останется в силе? Например, если я делаю итератор it2 = it; индекс.стереть(это); это = это2; это сработает? - person sunmat; 22.10.2012
comment
Нет, вы все равно стираете копию, вы можете предположить, что стирание принимает свой параметр по значению. Вы должны использовать алгоритмы remove_if, которые всегда гарантированно работают. - person CashCow; 22.10.2012