www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Sorted Map/AA for D2.0

reply Brian White <bcwhite pobox.com> writes:
Is there a standard implementation of a sorted map (aka "associative 
array") compatible with D2.0?

-- Brian
Mar 30 2008
parent reply 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
Mar 30 2008
parent 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
Mar 30 2008