Как добавлять в std::vector во время итерирования?

Question

[Андрей Яндуганов]

Имеется контейнер vector. Нужно пройтись по всем его элементам и при выполнении некоторого условия добавить или удалить элементы. При этом на каждом шаге нужно знать обо всех элементах.
Чтобы было совсем понятно, что именно я хочу получить, вот код:

for (auto obj = Organisms.begin(); obj != Organisms.end(); obj++)
	{
		(*obj)->eat();
		(*obj)->move();
		(*obj)->reproduce();
	}

В функции eat объекты могут удаляться, а в reproduce добавляться. И во всех трех функциях нужно знать обо всех существующих объектах.

Answer 1

[tsarevfs]

Возможно не самый элегантный, но достаточно предсказуемый способ -- разделить это на отдельные этапы.

for (auto obj = Organisms.begin(); obj != Organisms.end(); obj++)
{
    (*obj)->eat();
}
Organisms.erase(
    std::remove_if(Organisms.begin(), Organisms.end(),
        [](organism_ptr obj){obj->is_eaten();}
        ),
    Organisms.end()
    );
organisms_t new_organisms;
for (auto obj = Organisms.begin(); obj != Organisms.end(); obj++)
{
    organism_ptr org = (*obj)->reproduce();
    if (org)
        new_organisms.push_back(org);
}
Organisms.insert(Organisms.end(), new_organisms.begin(), new_organisms.end())
for (auto obj = Organisms.begin(); obj != Organisms.end(); obj++)
{
    (*obj)->move();
}

Comments

[Андрей Яндуганов]

В вашем варианте все хорошо, кроме одного. Вы предлагаете класть новые организмы в отдельный контейнер, а потом их все вставить в исходный. Для меня это не приемлемо, так как в процессе создания нового организма мне может понадобиться информация о только что созданном, но еще не добавленном в основной список.

[tsarevfs]

Андрей Яндуганов: Тогда есть 2 пути. Первый -- использовать list, второй -- скопировать Organisms и итерироваться по копии, внося изменения в основной массив (получается уже заморочено). Еще можно посмотреть на map или set.

Answer 2

[Армянское Радио]

Посмотрите на семантику insert и erase - они же возвращают итератор на вновь вставленный, либо следующий за удаленным элемент. От этого и пляшите.

Answer 3

[Олег Цилюрик]

А в чём вопрос?
(и что должно означать "нужно знать обо всех существующих объектах."?)
Некоторые ваши операции будут делать итератор obj недействительными, тогда obj++ закончится ... неизвестно чем.
В таких случаях нужно бы цепочку итераторов пробежать с начала, или от какого-то фиксированного места ранее.
Для таких вещей лучше (удобнее) переписать это всё не как цикл for, а как цикл while.

Comments

[Армянское Радио]

Олег Цилюрик - while здесь не уместен (нарушение одного из советов Голуба) - здесь присутствуют два из трех компонентов for -> нужно использовать for. А с while произойдет засорение области переменных.

[Олег Цилюрик]

Армянское Радио:
Глупость какая вместе с вашим Голубом ;-)
Во многих языках программирования, более "теоретических", развитых в сравнении с C/C++, в матлингвистике, теории языков программирования и т.д. - цикл while всегда считался более развитым, продвинутым и общным, чем for (for - это наследие FORTRAN).

[Армянское Радио]

Олег Цилюрик: Очень жаль, что у вас неверное представление о чистоте в коде. Для while придется завести внешнюю по отношению к циклу переменную. Зачем она нужна?
В С++, while является подмножеством for, а не наоборот.

[Олег Цилюрик]

Армянское Радио:
У меня правильное представление о чистоте кода ;-)

[Олег Цилюрик]

Армянское Радио:

Для while придется завести внешнюю по отношению к циклу переменную. Зачем она нужна?

Вовсе не обязательно ;-) :

while( true ) {
...
}

Более общей формы не бывает ;)

[Армянское Радио]

Олег Цилюрик: И выходить из цикла при помощи break или того хуже, return? Ваш код когда-нибудь проходил коллективное ревю? Стыдно было?

[Олег Цилюрик]

Армянское Радио:

Очень жаль, что у вас неверное представление о чистоте в коде.

Вы знаете ... я со стыдом признаюсь, что это не мои "неверные представления о чистоте в коде". Я их беззастенчиво списал, как двоечник - у Вирта, Дейкстры, Хоара и др.
... в отличие от крутого авторитета Голуба. ;-)

[Олег Цилюрик]

Армянское Радио:

Ваш код когда-нибудь проходил коллективное ревю?

Вы знаете ... мне никогда не было нужно "коллективное ревю".
Мне всегда было достаточно моего "индивидуального ревю" ;-)

P.S. Сколько себя помню, я всегда был начальником ;-)

[Армянское Радио]

Олег Цилюрик: И где же Дейкстровская нелюбовь к меткообразным сущностям вроде break? Да, дальше блока на break улететь нельзя, но отлавливать все break по телу цикла - удовольствие ниже среднего. Академические идеи с практикой программирования и поддержки вяжутся слабо.

Поэтому Голуб - авторитет, а над мечтами Дейкстры (в частности, о доказуемости программ) остается только сдержанно посмеяться, так как идеальных спецификаций даже на конкретную реализацию стандартной библиотеки нет. А без таковых и доказывать нечего.

[Олег Цилюрик]

Ринат Велиахмедов:

for значит "для всех элементов в таком-то промежутке".

В данном случае for более уместен - мы итерируемся по массиву элементов, выполняя определённые операции для каждого из них, длина цикла пропорциональна размеру массива.

Только здесь и обсуждается то, что за время прохождения "массива элементов" этот массив может стать в 2 раза короче или в 2 раза длиннее ;-)

А цикл while всегда уместнее for ;-)
Только не все умеют ним пользоваться ... и тяжёлый осадок от пережитых бесконечных циклов с while ;-). Эта ситуация с while мне напомнила:

Проходя мимо прислонённых к стене граблей, украинец всегда морщится.

Answer 4

[Vitaly]

Стоп.

Итерироваться по вектору и удалить/добавлять элементы -- плохая идея. Вектор вполне себе может реалоцироваться и всё печально закончится. Т.е. валидность итераторов не гарантируется после удаления/вставки. Можно поизвращаться конечно, но это костыльно. Либо делайте копию вектора и добавляейте/удаляйте элементы, либо выберите другой контейнер, думаю что list подойдёт или forward_list, а то и мапа какая-нибудь. Ктож знает какая у вас задача. В любом случае, я уверен что это не что-то высоконагруженное и быстрое, т.ч. преимущества вектора для последовательного перебора в виде кеш-линии вам ничего не даст.

Вот это мне не слишком понятно:
(*obj)->eat();
У вас какой-то свой хитрый итератор? Или странная логика -- кто кого съел: объект сам себя что ли? Я бы еще что-то вроде этого понял:
(*obj)->eat(*obj1);
В любом случае, советую продумать архитектуру и обратить внимания на паттерны проектирования вроде наблюдателя и посредника.

PS
И вопрос слегка не коректен, похоже что вы боретесь со следствиями какой-то архитектурной ошибки. Т.е. фактически вам нет необходимости удалять элементы из вектора при итерировании. По факту надо спросить как-то так: я решаю такую-то проблему, придумал её решить так-то, но вот незадача... как лучше сделать?

Comments

[Андрей Яндуганов]

Итератор у меня стандартный. Вас, видимо, сбило с толку то, что я храню не сами объекты, у указатели на них.
По поводу "кто кого съел: объект сам себя что ли?". Организм ест не что-то конкретное, а то, что попадется. Если никого рядом нет, то он и не съест ничего.
А задача эта известна как "Волчий остров". Правда, слегка измененная и усложненная. Может я и правда с архитектурой накосячил...