How Can I List a TDictionary in Alphabetical Order by Key in Delphi 2009?

Question

How can I use a TEnumerator to go through my TDictionary in sorted order by key?

I've got something like this:

  var
    Dic: TDictionary<string, string>;
    Enum: TPair<string, string>;

  begin
    Dic := TDictionary<string, string>.create;
    Dic.Add('Tired', 'I have been working on this too long');
    Dic.Add('Early', 'It is too early in the morning to be working on this');
    Dic.Add('HelpMe', 'I need some help'); 
    Dic.Add('Dumb', 'Yes I know this example is dumb');

   { I want to do the following but do it in sorted order by Enum.Key }
    for Enum in Dic do
      some processing with Enum.Key and Enum.Value;

    Dic.Free;
  end;

So I would like to process my dictionary in the order: Dumb, Early, HelpMe, Tired.

Unfortunately the Delphi help is very minimal in describing how enumerators in general and TEnumerator specifically works and gives no examples that I can find. There is also very little written on the web about using Enumerators with Generics in Delphi.

And my sample code above doesn't even use TEnumerator, so I'm confused as to how this is all designed to be used.

---

Thanks Barry, for your answer.

My venture into Generics since I asked the question was interesting. I wanted to start implementing them in my code. The "sorting" problem was somewhat perplexing, since it appears that Generics seem to have methods dealing with sorting built in, but there's no good examples or documentation on how to do it.

In the end I did what Barry suggested and built an external index into Dictionary. Still, it doesn't feel right.

However, then I had another surprise: I was attempting to replace Gabr's GPStringHash with the Generic's TDictionary. The code was a little cleaner with the generics. But the bottom line was that TDictionary was over 3 times slower than Gabr's. 1,704,667 calls to TryGetValue took .45 seconds, but the same operation to Gabr's routines took .12 seconds. I'm not sure why, but maybe its as simple as Gabr having a faster Hash function and bucketing combination. Or maybe the generics had to generalize for every case and that inherently slows it down.

Never-the-less, maybe Barry or the other Delphi developers should look at this, because a 3 times speedup could ultimately benefit everyone. I would personally sooner use what's built into the language than a 3rd party package (even one as good as Gabr's) if given the choice. But for now, I'll stick to GPStringHash.

Solution 1

In my case, I use the TDictionary < String, String >.TKeyCollection class.

function compareKey(const L, R: String): Integer;
begin
  Result := SysUtils.CompareText(L, R);
end;

function getReverseSortedKeyArray(dictionary: TDictionary<String, String): TArray<String>;
var
  keyArray: TArray<String>;
  keyCollection: TDictionary<String, String>.TKeyCollection;
begin
  keyCollection:= TDictionary<String, String>.TKeyCollection.Create(dictionary);
  try
    keyArray:= keyCollection.ToArray;
    TArray.Sort<String>(keyArray, TComparer<String>.Construct(compareKey));
  finally
    keyCollection.Free;
  end;

  Result := keyArray;
end;

Example of use :

var
  key: String;
  keyArray : TArray<String>;
begin
    keyArray  := getSortedKeyArray (dictionary);
    for key in keyArray  do
    begin
      // ...
    end;
end;

Solution 2

The dictionary is a hash table, so it doesn't store items in sorted order. TEnumerator is simple - it just a means of iterating over items.

To get items in an order, you need to sort them. One way would be to put them into a list and sort the list, like this:

var
  list: TList<string>;
begin
  list := TList<string>.Create(Dic.Keys);
  try
    list.Sort;
    // process sorted list of items now
  finally
    list.Free;
  end;
end;

Solution 3

Here is a sample code that sorts via Array<T> or a TList<T>. It preserves the Key Value Pair relationship, and it can also be tweaked to sort by Value instead of Key. Also, it uses an anonymous method to do the sorting.

Be sure to include Generics.Collections and Generics.Defaults in your uses clause. The first method to sort using TArray<T>:

procedure TestSortDictionaryViaArray;
var
  D: TDictionary<string, Integer>;
  A: TArray<TPair<string, Integer>>;
  P: TPair<string, Integer>;
begin
  D := TDictionary<string, Integer>.Create;

  D.Add('Test - 6', 6);
  D.Add('Test - 1', 1);
  D.Add('Test - 0', 0);
  D.Add('Test - 4', 4);
  D.Add('Test - 3', 3);
  D.Add('Test - 5', 0);
  D.Add('Test - 2', 2);

  A := D.ToArray;

  TArray.Sort<TPair<string, Integer>>(A,
    TComparer<TPair<string, Integer>>.Construct(
      function (const L, R: TPair<string, Integer>): Integer
      begin
        Result := CompareStr(L.Key, R.Key);
      end)
  );

  for P in A do
    ShowMessage(P.Key);
  D.Free;
end;

And this is using TList<T>:

procedure TestSortDictionaryViaList;
var
  D: TDictionary<string, Integer>;
  L: TList<TPair<string, Integer>>;
  P: TPair<string, Integer>;
begin
  D := TDictionary<string, Integer>.Create;

  D.Add('Test - 6', 6);
  D.Add('Test - 1', 1);
  D.Add('Test - 0', 0);
  D.Add('Test - 4', 4);
  D.Add('Test - 3', 3);
  D.Add('Test - 5', 0);
  D.Add('Test - 2', 2);

  L := TList<TPair<string, Integer>>.Create(D);

  L.Sort(
    TComparer<TPair<string, Integer>>.Construct(
      function (const L, R: TPair<string, Integer>): Integer
      begin
        Result := CompareStr(L.Key, R.Key);
      end)
  );

  for P in L do
    ShowMessage(P.Key);

  D.Free;
  L.Free;
end;

Additional (and unnecessary) information: The TList<T> method needs the list to be freed, whereas the TArray<T> doesn't need freeing. Internally, TList<T> uses TArray<T> (for example, TArray has a BinarySearch() class method, and TList<T> has a BinarySearch method).

Comments

[lkessler]

Here's a follow-up: Earlier this year (2016), I upgraded to Delphi XE8. I was thinking that TDictionary in the Delphi Generics package might have improved since I asked this question 5 years ago. So I took out GPStringHash by @gabr and replaced it with TDictionary. The slowdown to my program was quite significant. So at least for the forseeable future, I'm sticking with GPStringHash.

[Jim Mack]

Depending on your needs, rather than maintaining data in a dictionary and occasionally sorting it, you could do the reverse: maintain your data in a sorted list, but use a dictionary for fast 'random' access. This fits better if you are saving/retrieving through SQL, for example. Just always be clear who owns objects (strings, you're safe).

[Delmo]

What is valueCollecttion? Did you refer to keyCollecttion?

[Stéphane B.]

@Delmo valueCollecttion refer to keyCollecttion. It was a mistake. I update the answer. Thanks.