CODEWITHSUNDEEP
delphidictionary
Tiago
Tiago

Reputation: 183

Using TDictionary "for...in" to remove items

I am using Delphi Berlin 10.1 (the latest update) and I am having a problem with TDictionary in my application with some specific values. The for..in doesn't loop correctly.

Below there is a example code where the for...in doesn't loop through all values and another example where it does.

In the first case, the for...in loop does only two steps and in the second one it goes through all steps.

procedure TForm1.btn1Click(Sender: TObject);
var
  tmpPar: TPair<Integer, Integer>;
  tmpDictionary: TDictionary<Integer, Integer>;
begin
  // NOT WORKING
  tmpDictionary := TDictionary<Integer, Integer>.Create;
  try
      tmpDictionary.Add(631, 40832);
      tmpDictionary.Add(1312, 40837);
      tmpDictionary.Add(5947, 40842);

      for tmpPar in tmpDictionary do
      begin
          tmpDictionary.Remove(tmpPar.Key);
      end;
  finally
      tmpDictionary.Free;
  end;

  // WORKING
  tmpDictionary := TDictionary<Integer, Integer>.Create;
  try
      tmpDictionary.Add(123, 5432);
      tmpDictionary.Add(453, 23);
      tmpDictionary.Add(76, 2334);

      for tmpPar in tmpDictionary do
      begin
          tmpDictionary.Remove(tmpPar.Key);
      end;
  finally
      tmpDictionary.Free;
  end;
end;

Is there something wrong in the first case?

Upvotes: 1

Views: 4807

Answers (2)

Chris Rolliston
Chris Rolliston

Reputation: 4808

J... gives the explanation. The easiest fix goes like this:

var
  tmpKey: Integer;                                //!!!amended
  tmpDictionary: TDictionary<Integer, Integer>;
begin
  // NOW WORKING
  tmpDictionary := TDictionary<Integer, Integer>.Create;
  try
      tmpDictionary.Add(631, 40832);
      tmpDictionary.Add(1312, 40837);
      tmpDictionary.Add(5947, 40842);

      for tmpKey in tmpDictionary.Keys.ToArray do //!!!amended
      begin
          tmpDictionary.Remove(tmpKey);           //!!!amended
      end;
  finally
      tmpDictionary.Free;
  end;
end;

Basically, calling Keys.ToArray gives you a fresh copy of the keys that won't get deleted from under its feet as you do the item deletions.

Upvotes: 5

J...
J...

Reputation: 31403

Your example that works simply works by luck - there should be no expectation that this construct will behave well. If you step through your example you see that the first case invokes list reordering upon removal but the second example does not.

To see what's going on, if you examine the code for removing items from a dictionary : 

function TDictionary<TKey,TValue>.DoRemove(const Key: TKey; HashCode: Integer;
  Notification: TCollectionNotification): TValue;
var
  gap, index, hc, bucket: Integer;
  LKey: TKey;
begin
  index := GetBucketIndex(Key, HashCode);
  if index < 0 then
    Exit(Default(TValue));

  // Removing item from linear probe hash table is moderately
  // tricky. We need to fill in gaps, which will involve moving items
  // which may not even hash to the same location.
  // Knuth covers it well enough in Vol III. 6.4.; but beware, Algorithm R
  // (2nd ed) has a bug: step R4 should go to step R1, not R2 (already errata'd).
  // My version does linear probing forward, not backward, however.

  // gap refers to the hole that needs filling-in by shifting items down.
  // index searches for items that have been probed out of their slot,
  // but being careful not to move items if their bucket is between
  // our gap and our index (so that they'd be moved before their bucket).
  // We move the item at index into the gap, whereupon the new gap is
  // at the index. If the index hits a hole, then we're done.

  // If our load factor was exactly 1, we'll need to hit this hole
  // in order to terminate. Shouldn't normally be necessary, though.
  {...   etc   ...}

You see that there is an algorithm implemented which decides when and how to reorder the underlying list when removing items (this to attempt to optimize the location of gaps in the already-allocated memory block to optimize future insersions). Enumerating simply moves through indices in the underlying list, so once you remove an item from the list the enumerator is no longer valid as it will simply move you to the next index in the underlying list, which has since changed.

For a plain list you would usually iterate in reverse when removing. In the case of a dictionary, however, you must first build a list of keys to remove on the first enumeration pass and then enumerate that list to remove them from the dictionary.

Upvotes: 14

Related Questions