Итерация по контейнерам STL и удаление / добавление нескольких элементов

Одна из самых частых ошибок в моем коде заключается в том, что контейнеры STL изменяются во время цикла.

Элементы удаляются или добавляются во время выполнения цикла, поэтому я обычно сталкиваюсь с исключениями за пределами границ.

Мой цикл for обычно выглядит так:

for (auto& Item : Items) { // Will not work when Items container is modified
    //... loop logic
}

Когда несколько предметов могут быть удалены, я использую это чудовище:

for (int Index=Items.size()-1;Index
 Grapes21 июн. 2013 г., 10:38
@ Говори, я обычно неНе зная, что и где, событие может удалить любое количество элементов в любой момент цикла for.
 Spook21 июн. 2013 г., 10:36
Вы можете просто изменить итератор при удалении или добавлении элементов - если вы знаете, сколько элементов изменено и где.
 Matthieu M.21 июн. 2013 г., 11:16
Однако возникает вопрос: если при нажатии кнопки 4 удаляется кнопка 9, а вы действительно удаляете ее, а затем при нажатии кнопки 5 следует удалить кнопку 9 ... это то же самое «9» или он удаляет то, что раньше было 10-м элементом? Другими словами, идентифицированы ли ваши элементы по ключу или по их положению в контейнере?
 Damon21 июн. 2013 г., 10:46
Ну, если ты действительно неНе зная, когда и где элементы могут быть удалены (и сколько), ваш единственный вариант - сделать копию контейнера и изменить это ... В противном случаенет способа заставить это работать.

Ответы на вопрос(4)

Решение Вопроса

использованиеstd::remove_if с предикатом, который решает, нужно ли удалять кнопку:

bool needsRemoved(const Button& button);

vec.erase(std::remove_if(vec.begin(), vec.end(), &needsRemoved), vec.end());

РЕДАКТИРОВАТЬ: Для вашего последнего примера алгоритм квадратичного (т.е. плохого для производительности):

std::vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
auto end = vec.end();
for (auto it = vec.begin(); it < end; ++it)
{
    std::set<int> bad = {1, 4, 9};
    end = std::remove_if
        (vec.begin(), end,
         [bad](int x) { return (bad.find(x) != bad.end()); });
}
vec.erase(end, vec.end());
</int></int>

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

 rectummelancolique21 июн. 2013 г., 11:33
@James Kanze, я пропустил последнюю часть, см. Отредактированный ответ, спасибо за указание на это.
 James Kanze21 июн. 2013 г., 16:33
@rectummelancolique Я это понимаю. Но если пример нене имеет смысла в отношении текста? (И пример явно нене могу объяснить все.) Указатели WRT:слишком много, мы нене знаю, как ответить (Формально удаление указателя из контейнера до его удаления из контейнера - это неопределенное поведение. Но на практике это будет работать,если другой код пытается использовать его.)
 Spook21 июн. 2013 г., 11:03
Тот'Хорошая идея - если вы не хотите добавлять элементы :)
 rectummelancolique21 июн. 2013 г., 16:03
@ Джеймс Канз, ятолько повторное использование примера, который предоставляет OP. В любом случае я нене понимаю, почему ты не могт использоватьremove_if, Если они не подлежат копированию, их нельзя разумно поместить вvector на первом месте. Если они являются указателями, в приведенном вышеend вvec.end() удалить объекты перед вызовом стирания достаточно просто. Не говоря уже об использовании умных указателей вместо обычных.
 rectummelancolique21 июн. 2013 г., 16:45
@James Kanze Я считаю, что это очень хорошо определено. После того, как вы удалите элемент указателя, указатель будет недействительным, и если вы разыменуете его, тогда да, вы, очевидно, рискуете полностью изменить протон, точно так же, как указатель не в контейнере. Но я'Я не стандартный гуру, поэтому если у вас есть глава & стих об этом, яЯ буду рад прочитать это и отойти от вашей точки зрения. Когда ты сказалесли другой код не пытается использовать его на что ты ссылаешься?
 James Kanze21 июн. 2013 г., 18:07
@rectummelancolique Стандарт требует, чтобы элементы в контейнере были копируемыми, и даже требует их копирования в определенных случаях. Указатель на удаленную память не подлежит копированию. (Было оказано "недействительным", увидеть §3.7.4.2/4.) На практике контейнер не будет копировать его, если это не требуется, и очень мало, если какие-либо реализации, все еще существующие, где его копирование не будут просто копировать биты, без проблем. Но §3.7.4.2 все еще делает это неопределенным поведением.
 James Kanze21 июн. 2013 г., 18:11
@rectummelancolique The "если другой код не пытается использовать его " просто ссылается на тот факт, что его функция, очевидно, обращается к другим элементам в списке (поскольку она может их удалять). Вся его проблема связана с тем, что действие над пунктом 4 может удалить пункты 1, 4 и 9. Я нене понимаю, какremove_if можно заставить работать в этом случае.
 James Kanze21 июн. 2013 г., 15:20
@rectummelancolique Я все еще сомневаюсь, что ваше решение можно заставить работать. Если "кнопки» являются компонентами графического интерфейса, они, вероятно, не копируются, и, вероятно, они полиморфны. В этом случае фактические элементы в контейнере являются указателями, что означает, чтоremove_if не может быть использован.
 rectummelancolique21 июн. 2013 г., 18:21
Ах, хорошо спрятанная сноска в черновике, которую я получил, объясняет почему. Спасибо! Там есть несколько сумасшедших систем :) Точка уступила моему хорошему сэру. Тем не менее, я поддерживаю умный указатель, чтобы решить эту проблему.
 James Kanze21 июн. 2013 г., 11:04
Как это решит его проблему. Его проблема заключается в том, что что-то в кнопке 4 может убрать кнопки 1, 4 и 9. Обесценивает итератор в его цикле.
 rectummelancolique21 июн. 2013 г., 18:38

самое простое решение - просто сбросить цикл до начала при обработке события:

for ( auto current = items.begin(); current != items.end(); ++ current ) {
    if ( current->hasEventWhichNeedsProcessing() ) {
        current->processEvent();    //  possibly invalidates current
        current = items.begin();    //  revalidates current
    }
}

Если мы'Мы говорим о событиях кнопок (которые происходят из-за действий пользователя), это должно быть безопасно, так как обычно вы должны иметь возможность обрабатывать все события до того, как произойдет новое событие. (Для очень быстро происходящих событий вы можете никогда не достигнуть финальной записи.) Я '

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

что их не слишком много), вы можете добавить флаг к каждой кнопке, который сообщает, была ли она обработана полностью или что-то в этом роде. Затем вы ищете первый элемент в массиве, который не был обработан, и обрабатываете его. Вы повторяете это, пока все элементы не будут обработаны.

for (;;) // breaks, when all items have been processed.
{
    auto it = std::find( std::begin(Items), std::end(Items), 
        [](const Item & item){ return item.hasBeenProcessed(); }
    if ( it == std::end(Items) )
        break;
    process( *it );
}

Это должно быть безопасно. Обратите внимание, что это может иметь квадратичную временную сложность по отношению к количеству элементов. Как я уже сказал, надеюсь, не будет слишком много предметов. Если это проблема, вы можете немного оптимизировать этот цикл, например, начать поиск с того места, где вы ушли в прошлый раз. Но делайте это только тогда, когда это становится проблемой.

 James Kanze21 июн. 2013 г., 11:08
Это более или менее то, что я предлагаю также (хотя ябуду писать это чисто, без перерыва). Я не• думаю, что квадратичное время является проблемой, если объекты действительно являются кнопками; Сколько кнопок может нажать пользователь за время, необходимое для их обработки?

Переберите копию оригинального контейнера и манипулируйте оригиналом. Это может оказаться невозможным, если в вашем контейнере не хранятся указатели, а не сами элементы.

Дон»t разрешить прямое манипулирование контейнером, но вместо этого пометить элементы, которые должны быть удалены, и очистить их после итерации. Вы также можете поддержать добавление новых элементов, вставив их в отдельный временный контейнер и добавив к оригиналу после завершения цикла - вы также можете сделать это с удаленными элементами, избавляя от необходимости хранить "удален» флаг в самих элементах. Это, конечно, можно абстрагировать с помощью подходящегоadd а такжеremove функции.

Редактировать: Часть удаления решения № 2 может быть красиво сделана с помощью итерации удаления-удаления, показанной прямой кишкой меланколика.

 James Kanze21 июн. 2013 г., 15:17
@JohannesD Re ваше редактирование: если "кнопки» речь идет о компонентах графического интерфейса, они, вероятно, нет копируемый и, вероятно, полиморфный. В этом случае объекты в контейнере являются указателями, и вы можетет использоватьremove_if на контейнере.
 James Kanze21 июн. 2013 г., 15:09
@JohannesD Я нея знаю На самом деле, предполагая, что кнопки являются кнопками в интерфейсе GUI, у меня есть сомнения относительно подхода итерации по кнопкам в целом. В большинстве случаев вам нужно обрабатывать события в порядке их поступления: вы должны ставить события в очередь, используя классическую очередь FIFO.
 JohannesD21 июн. 2013 г., 11:19
@JamesKanze: Ну, вы можете пропустить те элементы, которые отмечены во время итерации. Я'Однако я не уверен, что в его случае это действительно хорошая идея - он создает асимметрию, когда, например, обрабатывающий элемент 2 вызывает удаление элементов 1 и 3, только # 3 можно пропустить как # 1 уже был обработан.
 James Kanze21 июн. 2013 г., 11:06
Второе решение - каноническое решение, но яЯ не уверен, что это применимо здесь (или, по крайней мере, это требует немного дополнительной работы). В его примере кнопка 4 обработки может удалить кнопку 9, поэтому он не долженКнопка обработки 9 позже в цикле.
 Spook21 июн. 2013 г., 10:52
+1, мне нравится второе решение. Гибко и безопасно.

Ваш ответ на вопрос