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

@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 на наиболее часто используемой операции.

Новые блоги и статьи Все статьи Все блоги /
Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .	Как надо было делать правильно - вообще не слушать ИИ, его дело - текст. Hrethgir 15.07.2026 А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её. Всё это стресс конечно. Почему?. . .	Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет	Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .

@Avazart 8489 / 6156 / 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 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	12.09.2016, 13:42
	Ну так там все равно по указателю. 0