How to sort a collection of objects in JavaScript without converting it to an array

Question

I am trying to avoid writing my own sorting algorithm for the following use case:

avatars = {};
avatars[102] = {userInfo: {buddy_name: 'Avatar102', is_online: 1}};
avatars[100] = {userInfo: {buddy_name: 'Avatar100', is_online: 1}};
avatars[101] = {userInfo: {buddy_name: 'Avatar101', is_online: 1}};

console.log(_.keys(avatars));
avatars = _.sortBy(avatars, function(avatar) {return avatar.userInfo.buddy_name.toLowerCase();});
console.log(_.keys(avatars));

Here's the console output:

• ["102", "100", "101"]
• ["0", "1", "2"]

As you can see, with undescore's sortBy I am losing the key data. This struct can get very large, so I am trying to avoid things like converting to an array and then back to the collection. Is there any way to do this without rolling my own sort function?

Answer 1

Your avatars is not an Array, it is just an object:

avatars = {};

so there is no defined order for its elements:

The mechanics and order of enumerating the properties (step 6.a in the first algorithm, step 7.a in the second) is not specified.

and 15.2.3.7 (and 15.2.3.14):

If an implementation defines a specific order of enumeration for the for-in statement, that same enumeration order must be used to order the list elements in step 3 of this algorithm.

You can also check section 8.6 to see if there is any mention about the order of properties in an object. The only requirement for ordering of object properties is that if the implementation defines an order anywhere then it has to use that same ordering everywhere but that's a big if. Most implementations probably use insertion order for an object's keys but I can't find anything that requires them to (I'd appreciate a comment if anyone can point out anything in the specs that define any particular order of an object's keys).

That said, Underscore's sortBy is basically a Schwartzian Transform combined with a standard JavaScript sort and Underscore's pluck to unwrap the Schwartzian Transform memo wrappers; pluck returns an array so sortBy also returns an array. Hence, your final _.keys(avatars) call is actually calling _.keys on an array; the keys of an array (AKA enumerable properties) are the array's indices and those are consecutive integers starting at zero.

You're using the wrong data structure. If you need a sparse array but also need to manipulate it like an array (i.e. sort it), then you should put the indexes inside the objects and use a normal array and pluck instead of keys:

var avatars = [
    {idx: 102, userInfo: {buddy_name: 'Avatar102', is_online: 1}},
    {idx: 100, userInfo: {buddy_name: 'Avatar100', is_online: 1}},
    {idx: 101, userInfo: {buddy_name: 'Avatar101', is_online: 1}}
];
console.log(_(avatars).pluck('idx'));
avatars = _(avatars).sortBy(function(avatar) {
    return avatar.userInfo.buddy_name.toLowerCase();
});
console.log(_(avatars).pluck('idx'));

Demo: http://jsfiddle.net/ambiguous/UCWL2/

If you also need quick access by idx then you could set up a parallel object for direct idx access:

var avatars_by_idx = { };
for(var i = 0; i < avatars.length; ++i)
    avatars_by_idx[avatars[i].idx] = avatars[i];

Then avatars_by_idx provides the direct access you're looking for. Of course, you'd have to keep avatars and avatars_by_idx synchronized but that's not terribly difficult if you hide them both behind an object.