Изменение контейнера во время итерационного перебора

@rikimaru2013 · Регистрация: 30.11.2013

Студворк — интернет-сервис помощи студентам

Добрый вечер,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Add( Some* ptr )
{
    cont.push_back( ptr );
}
void Update()
{
    for ( auto it = std::begin( cont ); it != std::end( cont ); )
    {
        ( *it )->Update();
        if ( ( *it )->Finished() )
        {
            it = cont.erase( it );
        }
        else
        {
            ++it;
        }
    }
}

Если в Update как-то запушить в cont - то итератор не валиден по понятным причинам, как и ++it. Пришлось извращаться:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Add( Some* ptr )
{
    if(_protect)
        delay.push_back(ptr)
    else
        cont.push_back( ptr );
}
void Update()
{
    _protect = true;
    for ( auto it = std::begin( cont ); it != std::end( cont ); )
    {
        ( *it )->Update();
        if ( ( *it )->Finished() )
        {
            it = cont.erase( it );
        }
        else
        {
            ++it;
        }
    }
    _protect = false;
    PushAllDelayToContAndClear();
}

Подскажите, есть ли методики не писать такие костыли? Или концептуально вы скажите не правильно, что некий тип умеет пушить в родителя?

@Fulcrum_013 · 12.09.2016, 11:16

Сообщение от rikimaru2013

да правильно)

И насколько понимаю порядок соблюдать не обязательно?

@Avazart · 12.09.2016, 11:20

HelicopterK52, Ну я не знаю как это реализовывается, но идея "самоудаления" и вообще то что элемент знает о контейнере кажется мне не продуктивной в этом случае.

@Fulcrum_013 · 12.09.2016, 11:25

Сообщение от Avazart

Нужно просто стараться его избегать или выбрать другой контейнер - std::list

И каждый раз выдергивать их по всей ОЗУ? Такие тормоза будут за счет промомахов кеша при каждом проходе что уж лучше удалять за О(n) но в кеше. А еще лучше постараться сделать так чтобы порядок их следования не имел значения. С партиклами это очень даже возможно.

Добавлено через 2 минуты

Сообщение от Avazart

Да? Т.е и что будет если один элемент удалится и нумерация изменится?

Слежением за этим вопросом должен заниматься контейнер при удалении. Плюс одна операция присваивания инта при каждом перемещении элемента и не более.

@rikimaru2013 · 12.09.2016, 11:29 **[ТС]**

Fulcrum_013, нужно естественно - z-order ведь. И с раскрытием карт про партикл думаю беседа плавно переплывет в частный случай - хотя это не так)

@Fulcrum_013 · 12.09.2016, 11:38

Сообщение от Avazart

Нужно просто стараться его избегать или выбрать другой контейнер - std::list

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

Добавлено через 3 минуты

Сообщение от rikimaru2013

нужно естественно - z-order ведь

Так тогда и в конец добавлять нельзя получается а нужно искать место для вставки в соответствии с Z добавляемого

Добавлено через 2 минуты

Сообщение от Avazart

У меня удаление всех элементов сразу за один цикл.

а цикл смещения который у erase под капотом?

@Avazart · 12.09.2016, 11:49

Сообщение от Fulcrum_013

а цикл смещения который у erase под капотом?

Да но смешения минимальное кол-во за счет обратного прохода.

@Fulcrum_013 · 12.09.2016, 11:50

Avazart Вот такое отложенное удаление поэффективнее erase будет:

C++
1
2
3
4
5
6
7
8
9
10
11
void CStringList::Pack(){
     int NewCount=0;
 
     for(NewCount=0;NewCount<FCount;NewCount++) 
           if(!Data[i]) break;
   
     for (int i=NewCount+1;i<FCount; i++) 
          if (Data[i]) Data[NewCount++]=Data[i];
 
     FCount=NewCount;
}

Правда вопрос с повторным перебором всей последовательности при каждом апдейте при этом не снимается.

@Avazart · 12.09.2016, 11:50

Сообщение от rikimaru2013

с раскрытием карт про партикл думаю беседа плавно переплывет в частный случай - хотя это не так)

Так общего случая и не может быть ...

@rikimaru2013 · 12.09.2016, 12:04 **[ТС]**

Avazart, ну вот первый пошёл) Может - вот другой пример:

- игра с монстрами, идёт монстр по карте у него логика: каждые 50 секунд, если хватает маны вызывать двух волков - куда ему их пушить? Да туда же где он сам. Когда он их вызывает? В Update(dt) когда просят обновить его логику и его личный счётчик _timeDt перевалит за 50 секунд.

@Fulcrum_013 · 12.09.2016, 12:05

Сообщение от Avazart

Так общего случая и не может быть ...

С этим утверждением абсолютно согласен

@rikimaru2013 · 12.09.2016, 12:06 **[ТС]**

Пример номер 3:

Кнопка в приложении "купить" - тыкаешь, а она через N время пушит в контейнер где она сама еще 2 кнопки "Вы уверены?" "Или не уверены"

@Fulcrum_013 · 12.09.2016, 12:17

Сообщение от rikimaru2013

игра с монстрами, идёт монстр по карте у него логика: каждые 50 секунд, если хватает маны вызывать двух волков - куда ему их пушить? Да туда же где он сам. Когда он их вызывает? В Update(dt) когда просят обновить его логику и его личный счётчик _timeDt перевалит за 50 секунд.

Летять ~~гуси~~ штурмовики по бескрайнему спейсу ограниченному сферой диаметром 50км. Когда юзеру приспичило затапить гашетку пуляють ракеты пачками. Ракеты в тот же массив пишутся. Когда ракета выработала топливо или вышла за радиус сферы она взрывается (самоудаляется) докидывая при этом в массив объект взрыв, который тоже самоудаляется по завершении. Порядок в котором производится апдейт неважен поэтому живет на константном по времени инстансном добавлении в конец и удалении обменом с последним, при обработке обход сзади наперед. Для самой обработки логики порядок обработки не важен потому как она условно-синхронная. А для отрисовки все равно z-буфер никуда не денется бо как оно 3D.
Да кстати начинал с одного списка потом сдеал их 5. Отдельно вызываются пересчет внутренних процессов, скорости,
движения, коллизий (2 списка - способен вызвать колизию (только подвижные) и способен к столкновению (подвижные и стационарные в которые можно въехать - пули и мелкие ракеты в нем не присутствуют))

@rikimaru2013 · 12.09.2016, 12:19 **[ТС]**

Fulcrum_013, запихнуть ракету и взрыв в одни контейнер - фу-фу-фу таким быть))) И какой там общий родитель? IBadabum ?

@Fulcrum_013 · 12.09.2016, 12:58

Сообщение от rikimaru2013

И какой там общий родитель? IBadabum ?

TPhisicObject.

Сообщение от rikimaru2013

запихнуть ракету и взрыв в одни контейнер - фу-фу-фу таким быть)))

Это космос. Взрыв не стоит на месте а продолжает полет по траектории в процессе горения, правда уже без ускорения.
А вот пули в отдельном массиве живут, тоже потомке TPhisicObject который в общем массиве живет и в своих апдейтах апдейтит пули.

Добавлено через 10 минут
Опять же безусловно общий там список владения. А в самих списках обработки они где в одном где в разных. К примеру взрыв не подписывается на пересчет скорости а ракета на возможность столкновения с ней.

Добавлено через 19 минут
Опять же все построено на концепции "создал объект из прототипа добавил в модель и забыл". Посему в каком состоянии на какие апдейты подписаться объекты сами знают. Т.е. сам контейнер только среда существования которая обеспечивает добавление/отслеживание удаления,подписку/отписку на апдейты ,и условно-синхронный вызов апдейтов для подписчиков.

@Avazart · 12.09.2016, 13:27

Сообщение от rikimaru2013

- игра с монстрами, идёт монстр по карте у него логика: каждые 50 секунд, если хватает маны вызывать двух волков - куда ему их пушить? Да туда же где он сам. Когда он их вызывает? В Update(dt) когда просят обновить его логику и его личный счётчик _timeDt перевалит за 50 секунд.

Мм в чем проблема использовать std::list ?

@Fulcrum_013 · 12.09.2016, 13:32

Сообщение от rikimaru2013

Кнопка в приложении "купить" - тыкаешь, а она через N время пушит в контейнер где она сама еще 2 кнопки "Вы уверены?" "Или не уверены"

Ну в таком случае я бы просто отдельный модальный диалог с оными двумя кнопками показывал бы (при необходимости модальный относительно формы покупки а не всего интерфейса/приложения).

Добавлено через 4 минуты

Сообщение от Avazart

Мм в чем проблема использовать std::list

разве что лепить лист с пулами константного времени распределения элементов. Тогда он еще как то будет в кеше присутствовать. Иначе элементы придется по всему ОЗУ выдергивать при доступе а это очень медленное занятие. т.е. получится дернул из листа указатель для чего подождал несколько сот тактов и только потом уже сам объект дергаешь.

@Avazart · 12.09.2016, 13:42

Ну так там все равно по указателю.

@Fulcrum_013 · 12.09.2016, 13:49

Сообщение от Avazart

Ну так там все равно по указателю.

Только с листом и список указателей по всей ОЗУ размазан а не в одном месте как с массивом.

@Voivoid · 12.09.2016, 13:57

Сообщение от Fulcrum_013

Только с листом и список указателей по всей ОЗУ размазан а не в одном месте как с массивом.

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

@Fulcrum_013 · 12.09.2016, 14:14

Сообщение от Voivoid

В случае с вектором можно еще конечно рассчитывать на data prefetch, но крайне сомневаюсь, что там требования к производительности настолько высоки, что стоило бы об этом задумываться

тесты производительности контейнеров. Обход массива соответствует линейному поиску. На вскидку вектор будет быстрее раза в 3 на наиболее часто используемой операции.

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@Avazart 8488 / 6155 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	12.09.2016, 11:20
	HelicopterK52, Ну я не знаю как это реализовывается, но идея "самоудаления" и вообще то что элемент знает о контейнере кажется мне не продуктивной в этом случае. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 11:29 [ТС]
	Fulcrum_013, нужно естественно - z-order ведь. И с раскрытием карт про партикл думаю беседа плавно переплывет в частный случай - хотя это не так) 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 12:04 [ТС]
	Avazart, ну вот первый пошёл) Может - вот другой пример: - игра с монстрами, идёт монстр по карте у него логика: каждые 50 секунд, если хватает маны вызывать двух волков - куда ему их пушить? Да туда же где он сам. Когда он их вызывает? В Update(dt) когда просят обновить его логику и его личный счётчик _timeDt перевалит за 50 секунд. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 12:06 [ТС]
	Пример номер 3: Кнопка в приложении "купить" - тыкаешь, а она через N время пушит в контейнер где она сама еще 2 кнопки "Вы уверены?" "Или не уверены" 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 12:19 [ТС]
	Fulcrum_013, запихнуть ракету и взрыв в одни контейнер - фу-фу-фу таким быть))) И какой там общий родитель? IBadabum ? 0

@Avazart 8488 / 6155 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	12.09.2016, 13:42
	Ну так там все равно по указателю. 0