Sorted Map Implementation

My Task In my JavaScript code i'm often using objects to 'map' keys to values so i can later access them directly through a certain value. For example: var helloMap = {}; helloMap.

Solution 1:

You'll need a wrapper of some kind using an array internally, I'm afraid. ECMAScript 5 (which is the standard on which current browser JavaScript implementations are based) simply doesn't allow for ordered object properties.

However, ECMAScript 6 will have a Map implementation that has ordered properties. See also http://www.nczonline.net/blog/2012/10/09/ecmascript-6-collections-part-2-maps/.

There may also be other options in ECMAScript 6. See the following question:

How can I define a default getter and setter using ECMAScript 5?

Solution 2:

Adding a link to a custom javascript library which provides Sorted maps and other implementation, for future reference in this thread . Check out https://github.com/monmohan/dsjslib -msingh

Solution 3:

I don't know of a general solution but non-general solutions are very simple to construct.

Typically, you maintain an Array of objects, with several methods defined as properties of the Array. At least, that's my approach.

Here's an example, taken (in a modified form) from a larger application :

var srcs = [];
srcs.find = function(dist) {
    var i;
    for(i=0; i<this.length; i++) {
        if(dist <= this[i].dist) { returnthis[i]; }
    }
    returnnull;
};
srcs.add = function(dist, src) {
    this.push({ dist:dist, src:src });
}
srcs.remove = function(dist) {
    var i;
    for(i=0; i<this.length; i++) {
        if(this[i].dist === dist) {
            srcs.splice(i,1);
            returntrue;
        }
    }
    returnfalse;
};
srcs.add(-1, 'item_0.gif' );
srcs.add(1.7, 'item_1.gif');
srcs.add(5, 'item_2.gif');
srcs.add(15, 'item_3.gif');
srcs.add(90, 'item_4.gif');

Unfortunately, you lose the simplicity of a plain js object lookup, but that's the price you pay for having an ordered entity.

If you absolutely must have order and dot.notation, then maintain a plain js Object for lookup and an Array for order. With care, the two can be maintained with total integrity.

Solution 4:

See my answer to this question. I implemented an basic ordered hashtable (ES 5+ only, didn't bother to polyfill)

Solution 5:

var put = function(k,v){
 if(map[k]){
   console.log("Key "+ k+" is already present");
 }else
 {
   var newMap = {};
   map[k] = v;
   Object.keys(map).sort().forEach(function(key){
   newMap[key] = map[key];
 });
   map = newMap;
   //delete newMap; in case object memory need to releasereturnmap;
 }
}

Put method will always take a key-value pair, internally creates another map with sorted keys from the actual map, update the value and return the updated map with sorted keys.No external library need to includ.