How to Keep an JavaScript Object/Array Ordered While Also Maintaining Key Lookups

How to keep an Javascript object/array ordered while also maintaining key lookups?

I have run across this problem as well. A solution is to keep an ordered array of keys in addition to the original object.

var objects = {
  "7": {"id":"7","name":"Hello"},
  "3": {"id":"3","name":"World"},
  ...
}
var order = [ "3", "7", ... ];

Now if you want the second element you can do this lookup:

var second_object = objects[order[1]];

The ECMA standard does not say anything about the order of the elements in an object. And specifically Chrome reorders the keys when they look like numbers.
Example:

var example = {
    "a": "a",
    "b": "b",
    "1": "1",
    "2": "2"
};

if you print this in Chrome will get something like:

{
    1: "1",
    2: "2",
    "a": "a",
    "b": "b"
};

It's a little sour .. but life.

You could use the solution Andy linked as well, basically wrapping these two together in one object.

An alternative that I use a lot is a custom map function that allows you to specify the order in which the object is traversed. Typically you will do sorting when you're printing your data to the user so while you loop and create your table rows (for instance) your iterator will pass the rows in the order your sort function specifies. I thought it was a nice idea :)

The signature looks like:

function map(object, callback, sort_function);

Example usage:

map(object, function (row) {
   table.add_row(row.header, row.value);
}, function (key1, key2) {
   return object[key1] - object[key2];
});

Javascript Object order incorrect

As suggested by @Teemu, properties are not stored in any specific order. But you can print them in any order using specific sort function accordingly.

Code

var obj = {};
for (var i = 5; i > -5; i--) {  obj[i * 10] = i * 10;}
// Sort and get all keys...var keys = Object.keys(obj).sort(function(a, b) {  return parseInt(a) - parseInt(b);});
console.log(keys)
// Loop over keys to print values of each propertykeys.forEach(function(item) {  console.log(item, obj[item]);})

Javascript data structure for fast lookup and ordered looping?

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.

OrderedMap
    map
    _array

    set(key, value)
    get(key)
    remove(key)
    forEach(fn)

function OrderedMap() {
    this.map = {};
    this._array = [];
}

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).

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, 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.

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];
};

Lookups will be in O(1). Retrieve the value by key from the associative array (object).

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

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.

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 Google's implementation of a LinkedMap from the Closure Library for documentation and source for such a class.

javascript object property/array manipulation

I'm not sure why you're only going half-way with your object literal syntax (JSON mimics object literal declarations), but it's also created a bug for you. You're over-writing myObject["123"] on the second assignment.

You could much more simply write that entire section 1 as:

var myObject = {
    "123": {
        "A": 123,
        "B": 456,
        "C": 123,
        "D": 456
    },
    "124": {
        "A": 123,
        "B": 456
    },
    "125": {
        "A": 123,
        "B": 456
    }
}

Second and third, there is no such thing as "first property in array." This is a pretty common mistake for people who write javascript (not just new people, but people who've been writing it for years).

Under no circumstances what-so-ever is any part of an object ever "First" or "second" or have any order in the object. This is clearly outlined in the ECMA-262 specification. Browser vendors will sometimes accommodate this behaviour which is why "it works" sometimes.

This is because objects are not arrays, nor will they ever be. If you want things to be in order of an array, you need to use an array. Let me ask you, what is the "first" element in the document object? Clearly that's a foolish question, but it proves the point. Objects do not maintain order, that's what arrays do.

So use an array for that. Square brackets denote an array, which does not take a string as a key (that's something objects do). To make things more confusing, arrays are objects, so they can act like objects-- don't confuse that and think objects are arrays.

javascript access the counter of a for in loop

(ECMAScript 2015 changes things, see update at end of answer.)

I have an array and an object. I want to iterate over the object properties while doing the same with the array, without explicitly declaring a counter.

I don't believe you can. Moreover, it's important to understand the that properties in the object have no order. You seem to be assuming you'll get "rose", then "sunflower", etc. That is simply not guaranteed. Many engines visit object property names in the order in which the properties were added to the object, and the order in which literal properties in an object initializer are added to the object is now (as of ES5 a couple of years back) specified, but visiting them in any particular order in for-in is not specified behavior (similarly, Object.keys is not sorted in any particular way), and a perfectly correct engine can visit them in any order it wants.

As such, with just the array and object you've shown, you have no reliable way to map those properties to the array entries.

As of ECMAScript 2015 (ES6), object properties have order now:

Let keys be a new empty List.

For each own property key P of O that is an integer index, in ascending numeric index order

Add P as the last element of keys.

For each own property key P of O that is a String but is not an integer index, in property creation order

Add P as the last element of keys.

For each own property key P of O that is a Symbol, in property creation order

Add P as the last element of keys.

Return keys.

Okay, so we know that they'll be visited in "creation" order, but in what order are they created by an object initializer? Good news: Object initializers are processed in source code order, so that's deterministic. Your rose comes before your sunflower, etc.

This means that while you still can't do what you want without explicitly declaring and maintaining an index variable, you can relate that array and that object reliably:

// Works as of ES6
var colors = ['red','yellow','purple','blue'];

var flowers = {'rose':'','sunflower':'','violet':'','hydrangea':''};

let i = 0;
for (prop in flowers) {
    flowers[prop] = colors[i++];
}

I'm not suggesting doing it, but it's possible now, on compliant engines.

Objects vs arrays in Javascript for key/value pairs

Each solution has its use cases.

I think the first solution is good if you're trying to define a one-to-one relationship (such as a simple mapping), especially if you need to use the key as a lookup key.

The second solution feels the most robust to me in general, and I'd probably use it if I didn't need a fast lookup key:

It's self-describing, so you don't
have to depend on anyone using
people to know that the key is the id of the user.
Each object comes self-contained,
which is better for passing the data
elsewhere - instead of two parameters
(id and name) you just pass around
people.
This is a rare problem, but sometimes
the key values may not be valid to
use as keys. For example, I once
wanted to map string conversions
(e.g., ":" to ">"), but since ":"
isn't a valid variable name I had to
use the second method.
It's easily extensible, in case
somewhere along the line you need to
add more data to some (or all) users.
(Sorry, I know about your "for
argument's sake" but this is an
important aspect.)

The third would be good if you need fast lookup time + some of the advantages listed above (passing the data around, self-describing). However, if you don't need the fast lookup time, it's a lot more cumbersome. Also, either way, you run the risk of error if the id in the object somehow varies from the id in people.

Most efficient way to update an object property within an array of objects

You've said your starting point is an array, but the most efficient way to do this is with a Map, not an array, where the key is the name and the value is either the price or an object containing the price (depending on whether you need other information).

With an Unsorted Array

But if you're doing this with an array, unless we can build / maintain the array in sorted order (see "With a Sorted Array" below), there's nothing more efficient than just looping through it looking for a previous element with the given name. filter isn't the right tool for that (you don't need the array it creates). You'd either write your own loop:

let element;
for (let index = 0, length = array.length; index < length; ++index) {
    const thisElement = array[index];
    if (thisElement.name === name) {
        // Already have one
        element = thisElement;
        break;
    }
}
if (element) {
    element.price += price;
} else {
    array.push({name, price});
}

With some JavaScript engines, you might get just that teensy bit more speed if you declared index, length, and thisElement before the loop:

let element, index, length, thisElement;
for (index = 0, length = array.length; index < length; ++index) {
    thisElement = array[index];
    // ...

but with others it could be the opposite. (It's not likely to be a big difference either way.)

Or use find:

const element = array.find(e => e.name === name);
if (element) {
    element.price += price;
} else {
    array.push({name, price});
}

Either of those provides linear lookup time. But if you were using a Map, you'd get sublinear lookup time.

With a Map

If using an object as the value:

const element = map.get(name);
if (element) {
    element.price += price;
} else {
    map.set(name, {name, price});
}

Or if using the price as the value:

const currentPrice = map.get(name) ?? 0; // If not found, `get` returns undefined; convert it to 0
map.set(currentPrice + price);

With a Sorted Array

If we can build / maintain the array in sorted order (you've said you can't, but maybe others finding this later can), we can do better than linear lookup by using a binary search (at the cost of slightly more overhead when inserting a new element, because all the ones after the insertion point have to be moved). It's more code, but if the search time is the main issue, it cuts search time.

const upsert = (array, name, price) => {
    let left = 0;
    let right = array.length;
    while (left < right) {
        let guess = Math.floor((left + right) / 2);
        let element = array[guess];
        if (element.name === name) {
            // Found! Update it
            element.price += price;
            return;
        }
        if (element.name < name) {
            left = guess + 1;
        } else {
            right = guess - 1;
        }
    }
    // Not found, insert it
    array.splice(left, 0, {name, price});
};

How to Keep an JavaScript Object/Array Ordered While Also Maintaining Key Lookups