Алгоритмы. Обход списка с удалением произвольных элементов

← →
atruhin © (2013-11-22 08:47) [0]

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

← →
все арамисы, а я Дартаньян (2013-11-22 08:50) [1]

если добавит перед собой, то твой алгоритм не сработает

← →
Медвешоног Порожок (2013-11-22 09:19) [2]

Периодически нужно обходить список и вызывать некоторые из этих процедур. Проблема в том, что процедура в процессе работы, может удалить некоторые из элементов списка (включая свой) или добавить.

И чего?
удаленные элементы в следующий цикл перебора не попадут
добавленные наоборот попадут.

← →
Jeer © (2013-11-22 09:20) [3]

Помечай "галками"

← →
RWolf © (2013-11-22 09:23) [4]

пусть процедуры не удаляют элементы, но помечают, как удалённые. Физическое удаление произведёт алгоритм обхода, когда элемент ему встретится в следующий раз.

← →
DevilDevil © (2013-11-22 09:31) [5]

RWolf тему говорит
так - самый быстрый вариант

← →
atruhin © (2013-11-22 09:33) [6]

>> RWolf © (22.11.13 09:23) [4]
Хм. А вот это хороший вариант, в любое время помечать, а собирать мусор при следующем проходе.
Спасибо. Думаю вопрос можно считать закрытым.

PS. Ведь нутром чувствовал, что где то должно быть простое и элегантное решение и не мог сообразить.

← →
jumping jack (2013-11-22 10:11) [8]

atruhin> или добавить
все арамисы, а я Дартаньян> если добавит перед собой, то твой алгоритм не сработает
+1
если процедура такая умная, пусть она итератором и работает (сама индекс инкрементирует и т.п.)

>Это разве не тоже самое? :)

Разумеется:)

Но это как и в аниме: кто-то смотрит на статичные картинки и видит фильм, да еще и 3D, а кто-то - фигу.

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