Javascript data structure for quick search and ordered loop?

Question

Is there a data structure or template in Javascript that can be used both for quick search (by key, and for associative arrays) and for an ordered loop?

That's right, now I use object literals to store my data, but I just turned off that Chrome does not maintain order when navigating through property names.

Is there a general way to solve this problem in Javascript?

Thanks for any tips.

Answer 1

Create the data structure yourself. Keep the order in the array that is internal to the structure. Store the objects associated with the key in a regular object. Let us call it OrderedMap , which will have a map, an array, and four basic methods.

 OrderedMap map _array set(key, value) get(key) remove(key) forEach(fn) function OrderedMap() { this.map = {}; this._array = []; } 

When you insert an element, add it to the array in the right place, as well as to the object. The insert at the index or at the end is in O (1).

 OrderedMap.prototype.set = function(key, value) { // key already exists, replace value if(key in this.map) { this.map[key] = value; } // insert new key and value else { this._array.push(key); this.map[key] = value; } }; 

When deleting an object, delete it from the array and object. If you remove the key or value, the complexity is O (n), since you need to go through an internal array that supports ordering. When deleting by index, complexity is O (1), since you have direct access to the value in both the array and the object.

 OrderedMap.prototype.remove = function(key) { var index = this._array.indexOf(key); if(index == -1) { throw new Error('key does not exist'); } this._array.splice(index, 1); delete this.map[key]; }; 

The search will be in O (1). Get the value by key from an associative array (object).

 OrderedMap.prototype.get = function(key) { return this.map[key]; }; 

The traverse will be streamlined and can use any of the approaches. When an ordered traversal is required, create an array with objects (only values) and return it. Being an array, it will not support key access. Another option is to ask the client to provide a callback function, which should be applied to each object in the array.

 OrderedMap.prototype.forEach = function(f) { var key, value; for(var i = 0; i < this._array.length; i++) { key = this._array[i]; value = this.map[key]; f(key, value); } }; 

See the Google LinkedMap implementation of the Closure library for documentation and the source for this class.

Answer 2

The only instance in which Chrome does not support the order of keys in an object literal seems to be if the keys are numeric.

  var properties = ["damsonplum", "9", "banana", "1", "apple", "cherry", "342"]; var objLiteral = { damsonplum: new Date(), "9": "nine", banana: [1,2,3], "1": "one", apple: /.*/, cherry: {a: 3, b: true}, "342": "three hundred forty-two" } function load() { var literalKeyOrder = []; for (var key in objLiteral) { literalKeyOrder.push(key); } var incremental = {}; for (var i = 0, prop; prop = properties[i]; i++) { incremental[prop] = objLiteral[prop]; } var incrementalKeyOrder = []; for (var key in incremental) { incrementalKeyOrder.push(key); } alert("Expected order: " + properties.join() + "\nKey order (literal): " + literalKeyOrder.join() + "\nKey order (incremental): " + incrementalKeyOrder.join()); } 

In Chrome above it is issued: "1,9,342, damsonplum, banana, apple, cherry."

In other browsers, it produces "damsonplum, 9, banana, 1, apple, cherry, 342".

Therefore, if your keys are not numeric, I think that even in Chrome you are safe. And if your keys are numeric, maybe just add them with a string.

Answer 3

As noted , if your keys are numeric, you can add them using a string to preserve order.

 var qy = { _141: '256k AAC', _22: '720p H.264 192k AAC', _84: '720p 3D 192k AAC', _140: '128k AAC' }; 

Example