Вопрос знатокам: удалять элементы TMap в процессе итерации

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Вопрос знатокам: удалять элементы TMap в процессе итерации

Сообщение Cheb » 14.08.2022 10:20:09

Сабж. С забрасыванием поддержки фпц 2.6.4, могу использовать stl - и начал применять специализацию TMap. Я ея *уже* активнейше использовал, в том числе на работе, даже премию получил.
НО: я всё ещё на уровне нуба, т.е. использую ея, как чёрный ящик, не имея представления, как она устроена под капотом (в отличие от обычных классов, строк и прочая, которые знаю до мелочей ещё с Дельфи 2 (это который первый 32-битный).
Вопрос в студию:
Код: Выделить всё
  procedure TVisualsMap.TrashExpired(start: pqword; limit: TUsecDeltaVal);
  var
    it: TIterator;
    v: TVisual;
  begin
    if IsEmpty then Exit;
    CS.Enter;
    it:= Min;
    repeat
      v:= it.Value;
      if (v.Expiration > 0) and (v.LockCount < 1)
        and (Mother^.State.CurrentFrame - v.LastEvoked > v.Expiration)
      then begin
        SetLength(Trash, Length(Trash) + 1);
        Trash[High(Trash)]:= v;
        Delete(it.Key)
      end;
    until (UsecDelta(start) > limit) or not it.Next;
    CS.Leave;
  end;

взлетит, или итератор упадёт с страшным хряпом оттого, что у него выдернули коврик из под ног?
Пощупать не могу: до компилируемости проекту ещё семь вёрст лесом.
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение BlackShark » 14.08.2022 14:12:34

Под капотом сбалансированное бинарное дерево, соответственно при вставки/удалении оно постоянно перестраивается. Едва ли итератор это учитывает. В лучшем случае будут пропуски элементов при итерировании. Аналогично сталкивался с подобным с делфёвой хэш-таблицей (TDictionary), а так же своих велосипедах/бинарных деревьях. В итоге для себя принял что если уж очень хочется пользовать деревья (бывает что без них ни как) с периодической чисткой - складываю в процессе итерации что нужно почистить в отдельный список и после отдельно чищу дерево по этому списку. А хеш-таблицу сделал свою которая позволяет удалять в процессе итерации.
Аватара пользователя
BlackShark
новенький
 
Сообщения: 44
Зарегистрирован: 20.05.2019 12:52:15

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение Cheb » 14.08.2022 15:04:01

Ага. То есть, надо использовать промежуточный массив, в который накласть ключи к удалению.
Океюшки.

Добавлено спустя 15 минут 44 секунды:
Re: Вопрос знатокам: удалять элементы TMap в процессе итерации
P.S.
Код: Выделить всё
procedure TVisualsMap.TrashExpired(start: pqword; limit: TUsecDeltaVal);
    // the only force in the universe to delete stale visuals
  var
    it: TIterator;
    v: TVisual;
    a: array of TAssetHash;
    b: TUsecDeltaVal;
    i: integer;
  begin
    if IsEmpty then Exit;
    Assert(Mother^.State.MainThreadId = GetCurrentThreadId()
      , 'Only call ' + {$i %CURRENTROUTINE%} + ' from the main thread');
    CS.Enter;
    b:= limit - max (0.3 * (limit - UsecDelta(start)) , 300.0); // microseconds
    it:= Min;
    repeat
      v:= it.Value;
      if (v.Expiration > 0) and (v.LockCount < 1)
        and (Mother^.State.CurrentFrame - v.LastEvoked > v.Expiration)
      then begin
        SetLength(a, Length(a) + 1);
        a[High(a)]:= it.Key;
      end;
    until (UsecDelta(start) > b) or not it.Next;
    if Length(a) > 0 then begin
      i:= 0;
      repeat
        if TryGetValue(a[i], v) then begin
          SetLength(Trash, Length(Trash) + 1);
          Trash[High(Trash)]:= v;
          Delete(a[i]);
        end;
        Inc(i);
      until (i > High(a)) or (UsecDelta(start) > limit);
    end;
    CS.Leave;
  end;
Последний раз редактировалось Cheb 14.08.2022 20:54:37, всего редактировалось 1 раз.
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение iskander » 14.08.2022 15:46:21

Если поменять порядок удаления элемента и вызова Next у итератора, то всё должно работать.
Кстати, кажется у вас там ещё утечка памяти, итератору требуется делать Free.
Небольшая тестовая процедура:
Код: Выделить всё
procedure TestMap;
type
  TIntMap = TMap<Integer, Integer, TLess<Integer>>;
var
  m: TIntMap;
  it: TIntMap.TIterator;
  p: TIntMap.TPair;
  I: Integer;
  Done: Boolean;
begin
  m := TIntMap.Create;
  try
    for I := 1 to 42 do
      m.Insert(I, I);
    it := m.Min;
    try
      repeat
        p := it.GetData;
        Done := not it.Next;
        if Odd(p.Value) then
          m.Delete(p.Key);
      until Done;
    finally
      it.Free;
    end;
    //Посмотрим, что получилось
    it := m.Min;
    try
      repeat
        p := it.GetData;
        WriteLn('Key: ', p.Key, ', Value: ', p.Value);
      until not it.Next;
    finally
      it.Free;
    end;
  finally
    m.Free;
  end;
end;

Вроде работает.
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение Cheb » 14.08.2022 22:14:37

iskander писал(а):итератору требуется делать Free.

Ой.
Спасибо.
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение wavebvg » 15.08.2022 11:09:04

Итератор -- это обход коллекции. Если Вы удалите из коллекции элемент, то итератор не должен этого заметить (в некоторых реализациях есть доп. признак, что в основном хранилище элемент удалён) или просто ломается.
При практическом применении, удалять элементы в процессе обхода коллекции является плохим тоном (задача бессмысленна, сложно отлаживается в многопоточном режиме).
Для удаления элементов из коллекции: либо обходят циклом (к примеру, в обратном порядке), либо копируют коллекцию и по копии уже итерируют, либо (для связных списков) запоминают прошлый элемент, переходят к следующему, а прошлый удаляют.
wavebvg
постоялец
 
Сообщения: 354
Зарегистрирован: 28.02.2008 04:57:35

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение Cheb » 16.08.2022 10:03:02

Спасибо.
В данном случае, мне понадобилось хранить набор визуальных представлений игрового мира (чанки, игроки, системы частиц), адресуемых хтоническим хешем. В типичных условиях, от кадра к кадру набор меняется мало, (всего ~ 5000, добавление/удаление меньше десятка за кадр). Собственно это моё "удаление в процессе обхода" - это очистка списка от протухших.
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение runewalsh » 17.08.2022 06:57:23

Можно сделать коллекцию, действующие итераторы которой отслеживаются в ней же и исправляются при удалениях элементов.
Это не то чтобы очень хорошая идея, но есть интересные юзкейсы; например, список коллбэков, вызываемых как for cb in list do cb.Call, где Call может добавлять или удалять другие коллбэки, в частности, коллбэк может удалить сам себя.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение zub » 17.08.2022 08:57:20

Всё-таки такие колбэки лучше на время итерации дожить в отдельный массив и добавить удалить после завершения итерации
zub
долгожитель
 
Сообщения: 2884
Зарегистрирован: 14.11.2005 23:51:26

Re: Вопрос знатокам: удалять элементы TMap в процессе итерац

Сообщение BlackShark » 17.08.2022 21:55:58

Если уж говорить о нормальном удалении элемента коллекции с итераторами в процессе перебора коллекции (чистки по критериям), предлагаю обратить внимание на подход, верный на мой взгляд, например в С++, где удаление элемента возможно выполнить через итератор. ИМХО, всё остальное это кривые костыли. В паскале возможно есть подобные решения, но мне не посчастливилось их увидеть.
Аватара пользователя
BlackShark
новенький
 
Сообщения: 44
Зарегистрирован: 20.05.2019 12:52:15


Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot] и гости: 31

Рейтинг@Mail.ru