is there a data structure or a pattern in Javascript that can be used for both fast lookup (by key, as with associative arrays) and for ordered looping?
Right, now I am using object literals to store my data but I just disovered that Chrome does not maintain the order when looping over the property names.
Is there a common way to solve this in Javascript?
Thanks for any hints.
As has been noted, if your keys are numeric you can prepend them with a string to preserve order.
Example
Create a data structure yourselves. Store the ordering in an array that is internal to the structure. Store the objects mapped by a key in a regular object. Let's call it
OrderedMap
which will have a map, an array, and four basic methods.When inserting an element, add it to the array at the desired position as well as to the object. Insertion by index or at the end is in O(1).
When deleting an object, remove it from the array and the object. If deleting by a key or a value, complexity is O(n) since you will need to traverse the internal array that maintains ordering. When deleting by index, complexity is O(1) since you have direct access to the value in both the array and the object.
Lookups will be in O(1). Retrieve the value by key from the associative array (object).
Traversal will be ordered and can use either of the approaches. When ordered traversal is required, create an array with the objects (values only) and return it. Being an array, it would not support keyed access. The other option is to ask the client to provide a callback function that should be applied to each object in the array.
See Google's implementation of a LinkedMap from the Closure Library for documentation and source for such a class.
The only instance in which Chrome doesn't maintain the order of keys in an object literal seems to be if the keys are numeric.
In Chrome, the above produces: "1,9,342,damsonplum,banana,apple,cherry".
In other browsers, it produces "damsonplum,9,banana,1,apple,cherry,342".
So unless your keys are numeric, I think even in Chrome, you're safe. And if your keys are numeric, maybe just prepend them with a string.