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

@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();
}

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

@Avazart · 12.09.2016, 14:21

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

Обход массива соответствует линейному поиску

Обход списка будет чуть медленнее чем вектора, но зато вставка/удаление в середину будет куда оптимальнее.

@Fulcrum_013 · 12.09.2016, 14:39

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

Обход списка будет чуть медленнее чем вектора, но зато вставка/удаление в середину будет куда оптимальнее.

На 8-байтном элементе список тоже проиграет по скорости раза в 3 а особенно на такой задаче. т.к. подвижка вектора происходить будет скорее всего происходить в L1 и уж точно не дальше чем в L2. При этом наиболее нагруженная задача не вставка/удаление а обход. Т.е. волков медведь может всунуть раз в 50 секунд. Это примерно один раз на 3000 обходов. Если учесть что среднестатический паукан живет около 45 секунд после чего добрые сталкеры разбирают его на запчасти то удаление тоже не чаще.

@Nosey · 12.09.2016, 14:44

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

Объект скорее всего по размеру будет больше кэш-линии (64 байта), так что в целом пофиг откуда читать.

Кэши бывают разные, с листом вы рискуете и в L3 не влезть. Так что не пофиг. Хотя всё зависит от требований алгоритма, в данном случае вектор будет лучше/стабильней, хотя чуть сложнее в реализации.

@Avazart · 12.09.2016, 14:53

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

На 8-байтном элементе список тоже проиграет по скорости раза в 3 а особенно на такой задаче.

Да там хрень какая-то а не замеры. При чем тут размер элемента?

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

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

При этом наиболее нагруженная задача не вставка/удаление а обход.

Нет это не так. Релокация и смещение элементов куда затратнее.

@rikimaru2013 · 12.09.2016, 14:59 **[ТС]**

Fulcrum_013, будут графики где видно что пауканы живут в среднем 45 секунд? Не верю!

@Fulcrum_013 · 12.09.2016, 15:14

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

При чем тут размер элемента?

При том сколько их в станицу кеша и вообще в кеш влезет.

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

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

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

Реалокация указателя в кеше сколько тактов занимает? А промах кеша сотни три тактов ждать будешь как минимум. Вот и получается что пока один указатель из ОЗУ прочитается за это же время 300 сместится в кеше.

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

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

что пауканы живут в среднем 45 секунд? Не верю!

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

@Voivoid · 12.09.2016, 15:21

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

Кэши бывают разные, с листом вы рискуете и в L3 не влезть.

За счет "лишних" 8-16 байт на указатели на предыдущий/следующий элемент что-ли?

@Fulcrum_013 · 12.09.2016, 15:28

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

Нет это не так. Релокация и смещение элементов куда затратнее.

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

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

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

За счет "лишних" 8-16 байт на указатели на предыдущий/следующий элемент что-ли?

За счет того что сами указатели по всему ОЗУ разбросаны а не лежат себе по порядочку как в векторе.

@Nosey · 12.09.2016, 15:42

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

За счет "лишних" 8-16 байт на указатели на предыдущий/следующий элемент что-ли?

Ну если вы так считаете

Лист оправдан только в случаях когда количество вставок соизмеримо с количеством обходов, а это явно не наш случай.

@Voivoid · 12.09.2016, 15:43

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

За счет того что сами указатели по всему ОЗУ разбросаны а не лежат себе по порядочку как в векторе.

И? Дальше-то что? Как это связано с "Кэши бывают разные, с листом вы рискуете и в L3 не влезть." ?

Добавлено через 35 секунд

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

Ну если вы так считаете

Да нет уж, поведай что ты там нарассуждал

@Fulcrum_013 · 12.09.2016, 15:52

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

Как это связано с "Кэши бывают разные, с листом вы рискуете и в L3 не влезть." ?

Да очень просто. Данные в кеш страницами по 4кб попадают а не по элементу выдергиваются. Для того чтобы забить L3 среднестатического домашнего десктопа хватит 750 элементов попавших при распределении в разные страницы ОЗУ.
У вектора же если и в разных страницах то в соседних, причем все не крайние страницы полностью элементами вектора заполнены. Если это вектор указателей то в страницу влезет 512 указателей на x64 и 1024 указателя на x86

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

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

Лист оправдан только в случаях когда количество вставок соизмеримо с количеством обходов, а это явно не наш случай.

Вот и я об этом. Тоже кстати касается флагов и внешней обработки на их основе.

@rikimaru2013 · 12.09.2016, 15:59 **[ТС]**

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

Лист оправдан только в случаях когда количество вставок соизмеримо с количеством обходов

что за количество обходов? Или я не так прочитал или тут сравнили горячее с зелёным.

@Nosey · 12.09.2016, 16:02

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

что за количество обходов?

C++
1
for(auto& ob : objs) {}

@Fulcrum_013 · 12.09.2016, 16:07

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

что за количество обходов?

Отношение вызовов Update всего контейнера (т.е. обхода массива) к количеству вставок/удалений при этих проходах. С учетом особенностей кеширования списка и вектора то еще и отношение количества элементов в контейнере к количеству удалений играет рояль. По большому счету отношение количества вызовов update элемента в секунду к количеству удалений/вставок в секунду. Чем выше это отношение тем лучше пользовать массив а не двусвязный список.

@Voivoid · 12.09.2016, 16:09

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

Данные в кеш страницами по 4кб попадают а не по элементу выдергиваются.

Ты упорот что-ли? каким страницами, какие 4кб? По размеру кэш-линии они попадают, что на подавляющем большинстве совеременных архитектур составляет 64 байта.

@rikimaru2013 · 12.09.2016, 16:16 **[ТС]**

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

for(auto& ob : objs) {}

Да ладно))))

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

Чем выше это отношение тем лучше пользовать массив а не двусвязный список.

А есть значение? К примеру при обходе 100 элементов, когда будет удалено/вставлено свыше 23 элементов - лучше использовать list ?

@Nosey · 12.09.2016, 16:34

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

А есть значение? К примеру при обходе 100 элементов, когда будет удалено/вставлено свыше 23 элементов - лучше использовать list ?

Если erase-remove вектора нас устраивает, т.е. перемещение/копирование элемента совершается быстро(указатели например) + нам не важен порядок, то вектор подойдет, хотя выигрыша в этом случае практически не будет, будет только геморой с итераторами

. А иначе конечно уже лист.

@Fulcrum_013 · 12.09.2016, 16:47

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

Ты упорот что-ли? каким страницами, какие 4кб?

А что упреждающее кеширование для L3 применять перестали что ли? Страницу на борт сразу при обращении и все довольны.

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

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

будет только геморой с итераторами

Можно свой массив и никакого гемороя с итераторами не будет. Если порядок не важен там вообще константное время удаления вставки.

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

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

А есть значение? К примеру при обходе 100 элементов, когда будет удалено/вставлено свыше 23 элементов - лучше использовать list ?

Ну вот тут уже придется эксперементальным путем подбирать с какого предела что быстрее. Я проще сделал - обеспечил обработку не требующую сохранения порядка элементов. Соответственно константное время удаления/добавления в списки (массивы) обработки. Обход в обратном направлении. И все тип-топ. Одно ограничение - объект не имеет права собственноручно удалять соседей во время обхода.

@Voivoid · 12.09.2016, 16:47

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

А что упреждающее кеширование для L3 применять перестали что ли? Страницу на борт сразу при обращении и все довольны.

Что-то у меня крайне большие сомнения на этот счет, как будто прочитать 4кб это как нефиг делать

Давай-ка пруф-линк в, скажем, intel software developer manual'е

@Fulcrum_013 · 12.09.2016, 17:27

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

как будто прочитать 4кб это как нефиг делать

Главное что прочитать их подряд гораздо быстрее чем дергать по одиночке. За счет того что адрес один раз отдается памяти а не на каждый элемент.

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

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

К примеру при обходе 100 элементов, когда будет удалено/вставлено свыше 23 элементов - лучше использовать list ?

При этом стоит учитывать что добавление/удаление имеет свойство возрастать/падать рывками. К примеру если работающая на полный мощность скорострельная пушка добавляет до 2 снарядов за кадр, то взрыв среднестатического 30-мм снаряда дает в одночасье 300 только первичных осколков. Взрыв зенитной ракеты дает оных осколков уже около 10 тысяч. При этом удаляться осколки произведенные одним боеприпасом будут из модели тоже преимущественно одновременно.

Новые блоги и статьи Все статьи Все блоги /
Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	Программный отбор значений справочника Maks 21.03.2026 Установка программного отбора значений справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 14:59 [ТС]
	Fulcrum_013, будут графики где видно что пауканы живут в среднем 45 секунд? Не верю! 0