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

@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,

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

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

@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