Is there a standard implementation of a sorted map (aka "associative array") compatible with D2.0?

-- Brian

On Sun, 30 Mar 2008 11:59:57 +0200, Brian White wrote:

> Is there a standard implementation of a sorted map (aka "associative array") compatible with D2.0?

Because different people can mean different things by the terms "sorted map" and "associative array", what exactly are you after in D?

Currently, both v1 and v2 implement associative arrays, but neither the keys or values are sorted. This is not a big problem unless you need to continually access the data in sorted order.

Here's one example of its usage...

import std.stdio;
void main()
{
   int[string] myAA;  // Define an AA of integers that uses a string key.

   // English
   myAA["one"]   = 1;
   myAA["two"]   = 2;
   myAA["three"] = 3;
   myAA["four"]  = 4;
   myAA["five"]  = 5;
   myAA["six"]   = 6;
   myAA["seven"] = 7;
   myAA["eight"] = 8;
   myAA["nine"]  = 9;
   myAA["ten"]   = 10;

   // Thai
   myAA["nueng"] = 1;
   myAA["song"]  = 2;
   myAA["saam"]  = 3;
   myAA["see"]   = 4;
   myAA["hah"]   = 5;
   myAA["hok"]   = 6;
   myAA["djet"]  = 7;
   myAA["bpaht"] = 8;
   myAA["kow"]   = 9;
   myAA["sip"]   = 10;

   // Display in 'stored' order
   foreach(k, v; myAA)
      writef("%s=%s ", k, v);
   writefln();

   // Display in sorted key order
   foreach(v; myAA.keys.sort)
      writef("%s=%s ", v, myAA[v]);
   writefln();

   // Display in sorted data order
   foreach(v; myAA.values.sort)
      writef("%s ", v);
   writefln();

   // Display in sorted data order with keys
   // This is not so easy when multiple keys have the same value.

   string[][int] temp; // Set up a reverse-index array
   foreach(v; myAA.keys)
   {
        temp[myAA[v]] ~= v;
   }
   foreach(v; temp.keys.sort)
      writef("%s=%s ", temp[v], v);

   writefln();
}


-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell

> Currently, both v1 and v2 implement associative arrays, but neither the
> keys or values are sorted. This is not a big problem unless you need to
> continually access the data in sorted order.

Right.  I want the keys sorted.  I have a task where I'll be inserting into the map sporadically but will be accessing it freely and I need it sorted.  A "heap" would suffice, too, as I really is O(1) access to the smallest element.

-- Brian