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

[Cheb]

Сабж. С забрасыванием поддержки фпц 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;

взлетит, или итератор упадёт с страшным хряпом оттого, что у него выдернули коврик из под ног?
Пощупать не могу: до компилируемости проекту ещё семь вёрст лесом.

[BlackShark]

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

[Cheb]

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

Добавлено спустя 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;

[iskander]

Если поменять порядок удаления элемента и вызова 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;


Вроде работает.

[Cheb]

итератору требуется делать Free.

Ой.
Спасибо.

[wavebvg]

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

[Cheb]

Спасибо.
В данном случае, мне понадобилось хранить набор визуальных представлений игрового мира (чанки, игроки, системы частиц), адресуемых хтоническим хешем. В типичных условиях, от кадра к кадру набор меняется мало, (всего ~ 5000, добавление/удаление меньше десятка за кадр). Собственно это моё "удаление в процессе обхода" - это очистка списка от протухших.

[runewalsh]

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

[zub]

Всё-таки такие колбэки лучше на время итерации дожить в отдельный массив и добавить удалить после завершения итерации

[BlackShark]

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