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

@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, 00:20

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

кол-во кода должно уменьшиться в несколько раз?

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

@Nosey · 12.09.2016, 00:21

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

Какие сложности создаст вынесение логики добавления из Update элемента во внешний Update?

Что значит внешний?

Ну и в общем еще повторю свою точку зрения:
Если это какая-то листовая сущность в архитектуре с <500 строками, то мне как-то пофиг, будут там архитектурные изыски али нет, ибо от них ничего не зависит. И также, будет практически пофиг, где этот код написан с точки зрения разделения на функции, т.е. будут ли там процедурные изыски.
В ситуации архитектурной важности сего объекта, все совсем иначе, я предлагаю полностью разбить логику update на несколько раздельных методов с разными обязанностями. В данном случае update который будет вместо добавления детей, регистрироваться на будущее добавление. Но тут нужно видеть максимально возможный контекст.

@rikimaru2013 · 12.09.2016, 00:23 **[ТС]**

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

Есть списки обработки

Он один, и далее по тексту везде главная причина что их много. Нет список один)

@Fulcrum_013 · 12.09.2016, 00:26

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

Почему не разбить на два метода

А зачем вообще этот флаг? Может проще запилить обработку контейнером самоудаления элемента?

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

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

Он один, и далее по тексту везде главная причина что их много. Нет список один)

Как только допилишь его до идеала сразу таких же захочется много.

Это же ~~бубль-гум~~ ООП

@Avazart · 12.09.2016, 00:46

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

А зачем вообще этот флаг? Может проще запилить обработку контейнером самоудаления элемента?

Не факт что это будет эффективно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void removeFinished()
{
  for(int i= cont.size(); i>0; --i)
     if(cont[i]->finished())
     {
       delete cont[i];
       cont.erase(cont.begin()+i)
     }  
}
 
void update()
{
  for(std::size_t i=0; i<cont.size(); ++i)
     cont[i]->update();
     
  removeFinished();  
}

Кстати removeFinished() наверное можно через std::remove_if() реализовать.

@ct0r · 12.09.2016, 01:00

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

Да хранится в объекте - используется только в методе Update

И ты думаешь, что это ок? Ок, если ок. Но по-моему - не ок.

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

Потому, что это полиморфизм? Вот он один такой - решил выделится - среди 20 других типов, что ему нужно соседи

Хорошо. Идем дальше. Как мне понять/догадаться из кода, что (*it)->Update() может модифицировать контейнер?
Так что:
Либо мы передаем туда всегда явно контейнер.
Либо мы возвращаем оттуда функцию, которая тут у нас что-то сделает с контейнером.
Либо мы разбиваем Update на несколько функций, одна из которых не меняет контейнер, а другая принимает контейнер и что-то с ним делает.

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

Элемент не просто это решает а тут же отдает команду контейнеру списков в какой список его занести/извлечь.

Иии? Где тут в несколько раз? На несколько строк максимум.

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

Если это какая-то листовая сущность в архитектуре с <500 строками, то мне как-то пофиг, будут там архитектурные изыски али нет, ибо от них ничего не зависит. И также, будет практически пофиг, где этот код написан с точки зрения разделения на функции, т.е. будут ли там процедурные изыски.

Как мне кажется, лучше потратить жалких полчаса и написать эти 500 строк нормально, чем коммитить быдлокод на ревью с фразой "чуваки, эта туфта вообще почти нигде не используется, так что я тут набыдлокодил". Потом эта туфта может стать не туфтой, или придется на ней ловить баги, или кто-то потом скопипастит часть логики, или джуниоры почитают и подумают что так надо писать, или потом на ревью кто-то другой будет доказывать, что его быдлокод тоже мало где нужен...
Другое дело - если ты тормоз/неопытен и в сроки можешь только набыдлокодить.
Или - если ты перфекционист и каждую мелочь вылизываешь целый день.
Но это крайности.
Хороший программист всегда пишет хороший код, если нет веских причин писать плохой. Это привычка как минимум.

@Fulcrum_013 · 12.09.2016, 01:02

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

Не факт что это будет эффективно.

Будет. Удаление элемента делается за тоже O(n-i), а если порядок элементов всписке не важен то и за константное время. При этом не потребуется обходить проверять на предмет удаления свежедобавленных. Опять же если объемы удаления при одном обходе небольшие относительно размера списка то обработать инстансно будет быстрее. Кстати именно из за этого у себя огород с мультисписками и городил - чтобы флаги не пользовать, т.к. списки не маленькие, а изменение прибывания в списках для элемента максимум раз на несколько сот обходов, соответственно если по флагам проверять да еще после каждого обхода по флагам проверят удалять или нет... В общем больше перелопачивания последовательности бестолку.

@Avazart · 12.09.2016, 01:04

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

O(n-i)

Это хорошо по вашему? Точнее сказать n*m где m- кол-во удаляемых элементов.

@Fulcrum_013 · 12.09.2016, 01:18

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

Иии? Где тут в несколько раз? На несколько строк максимум.

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

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

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

Точнее сказать n*m где m- кол-во удаляемых элементов.

А по вашему что по другому? Только плюсом к этому еще и обход всей последовательности там где это не нужно.

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

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

очнее сказать n*m где m- кол-во удаляемых элементов.

а если подумать то удаление одного O(n-i) где i порядковый номер удаляемого который он может хранить. Если нет необходимости соблюдать упорядоченность то вообще константное время.

@Nosey · 12.09.2016, 01:31

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

Как мне кажется, лучше потратить жалких полчаса и написать э..... плохой. Это привычка как минимум.

Это все правильные, красивые, философские слова. Но для конструктива вы не ответили что значит внешний update? Это просто пара бонусных глобальных функций/методов, али что-то серьезней?

@Fulcrum_013 · 12.09.2016, 01:32

Avazart, Вообще как подозреваю контейнер для партиклов которых тьма, при этом удаление штука относительно редкая по сравнению с обработкой, да и упорядоченность не важна. А вот каждый лишний проход проверки флагов это действительно очень неэффективно в таких задачах.
rikimaru2013 Правильно подозреваю?

@ct0r · 12.09.2016, 01:57

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

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

При каждом? Ну я так код не дублирую.

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

а если подумать то удаление одного O(n-i) где i порядковый номер удаляемого который он может хранить.

big-O - это ж асимптотика, какой там i?

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

А по вашему что по другому?

O(n), если мы сперва соберем все удаляемые и вставляемые. И это сводится к O(m), если порядок не важен.

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

Но для конструктива вы не ответили что значит внешний update?

Да тот самый Update(). Я было подумал, что решение о вставке принимается на основе данных, которые можно достать из элемента, и применимо ко всем элементам. А оказалось, что оно тупо зависит от самого типа элемента.

@Fulcrum_013 · 12.09.2016, 02:04

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

И это сводится к O(m), если порядок не важен.

к О(m) это сводится только если элемент хранит свой порядковый номер и удаление инстансное. а иначе O(n) причем на каждом апдейте а не только на том на котором было удаление.

@Avazart · 12.09.2016, 02:13

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

А по вашему что по другому? Только плюсом к этому еще и обход всей последовательности там где это не нужно.

А вы не видите что по другому? У меня удаление всех элементов сразу за один цикл.

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

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

а если подумать то удаление одного O(n-i) где i порядковый номер удаляемого который он может хранить. Если нет необходимости соблюдать упорядоченность то вообще константное время.

Для этого нужно сначала на узнать это i элемент а это O(n) для вектора. Т.е для самоудаления объект должен найти себя в контейнере родителе.

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

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

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

У нас конкретный случай.

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

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

А вот каждый лишний проход проверки флагов это действительно очень неэффективно в таких задачах.

Эффективный если учитывать что удаление вызывает смещение элементов. Поэтому делать его нужно в цикле в обратном порядке что бы минимизировать "перекопирование", в отличии от обновления который идет в прямом.

@Fulcrum_013 · 12.09.2016, 02:28

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

Для этого нужно сначала на узнать это i элемент а это O(n) для вектора.

А вот это уже от элемента зависит. Элемент может хранить свой порядковый номер.

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

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

Эффективный если учитывать что удаление вызывает смещение элементов

Просто смещать эффективно надо а не через erase. Тогда удалить можно за O(n) вместе со всеми смещениями и по флагам. Но это O(n) проверки флагов на каждой итерации а не только на тех где были удаления.

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

У нас конкретный случай.

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

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

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

@Avazart · 12.09.2016, 10:46

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

А вот это уже от элемента зависит. Элемент может хранить свой порядковый номер.

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

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

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

Просто смещать эффективно надо а не через erase.

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

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

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

именно для хранения партиклов.

Посветите в ваш нововыдуманный термин? Может уже словарь напишите для форумчан?

@HelicopterK52 · 12.09.2016, 10:54

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

Посветите в ваш нововыдуманный термин?

Система частиц (particle system).
Частица (particle).

@Avazart · 12.09.2016, 10:58

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

Система частиц (particle system). Отсюда единичное - партикл.

Типа:

Кликните здесь для просмотра всего текста

@HelicopterK52 · 12.09.2016, 10:59

Avazart,

Кликните здесь для просмотра всего текста

Новые блоги и статьи Все статьи Все блоги /
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 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию 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-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@Fulcrum_013 2083 / 1575 / 169 Регистрация: 14.12.2014 Сообщений: 13,614
	12.09.2016, 01:32
	Avazart, Вообще как подозреваю контейнер для партиклов которых тьма, при этом удаление штука относительно редкая по сравнению с обработкой, да и упорядоченность не важна. А вот каждый лишний проход проверки флагов это действительно очень неэффективно в таких задачах. rikimaru2013 Правильно подозреваю? 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	12.09.2016, 10:10 [ТС]
	Fulcrum_013, да правильно) 0

@HelicopterK52 829 / 253 / 34 Регистрация: 27.07.2016 Сообщений: 497 Записей в блоге: 1
	12.09.2016, 10:59
	Avazart, Кликните здесь для просмотра всего текста 0