• Brian White (3/3) Mar 30 2008 Is there a standard implementation of a sorted map (aka "associative
• Derek Parnell (66/68) Mar 30 2008 Because different people can mean different things by the terms "sorted
• Brian White (5/8) Mar 30 2008 Right. I want the keys sorted. I have a task where I'll be inserting

Brian White <bcwhite pobox.com> writes:

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

-- Brian

Derek Parnell <derek psych.ward> writes:

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

Brian White <bcwhite pobox.com> writes:

 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