Javascript - sequencial array-like object

Question

There are often some tasks like adding items into shopping cart. If the cart is an array, it will take O(n) to retrieve an item by id. It is O(1) using objects, but it then does not guarantee to have the inserting order.

So is there an elegant way to have fast lookup object while maintaining the inserting order?

Option #1 - save both. Option#2 - why do you care about performance? Do you think you will have some performance issue there? — Dekel
– Dekel, Commented Aug 18, 2017 at 16:35
For example in react, I have a list of products (components). Each needs to check if it appears in the cart or not upon updates. One way is to pass the whole cart to the components and each have an O(n) check. Second way is to create a dict with item.id using reduce() method. But these are all recomputed whenever user maybe presses a button. So it is quite a performance hit. — Nakamura
– Nakamura, Commented Aug 18, 2017 at 17:01

T.J. Crowder · Accepted Answer · 2017-08-18 16:35:16Z

1

I've typically done this by having an array and an object that both reference the same object. E.g.:

var thingies = [];
var thingiesById = Object.create(null);

when adding a "thingy":

thingies.push(thingy);
thingiesById[thingy.id] = thingy;

Example:

var thingies = [];
var thingiesById = Object.create(null);

function addThingy(thingy) {
    thingies.push(thingy);
    thingiesById[thingy.id] = thingy;
}

// Note intentionally not adding them in ID order
addThingy({id:3, name: "Thingy 3"});
addThingy({id:1, name: "Thingy 1"});
addThingy({id:2, name: "Thingy 2"});

thingies.forEach(function(thingy) {
    console.log(thingy.id + ": " + thingy.name);
});

ES2015+'s Maps maintain insertion order and provide iteration semantics that follow that order. You'll want to test that lookup speed on get is as good as you need it to be.

Example:

const thingies = new Map();

function addThingy(thingy) {
    thingies.set(thingy.id, thingy);
}

// Note intentionally not adding them in ID order
addThingy({id:3, name: "Thingy 3"});
addThingy({id:1, name: "Thingy 1"});
addThingy({id:2, name: "Thingy 2"});

for (const thingy of thingies.values()) {
    console.log(thingy.id + ": " + thingy.name);
}

answered Aug 18, 2017 at 16:35

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nakamura Over a year ago

Having two references together may introduce inconsistency and hard to maintain. Map seems cool and may be what I was looking for. It is possible or simple enough to add quantity of the item if it is already in the Map?

T.J. Crowder Over a year ago

@Nakamura: If you wrap it up into an object that does the management for you, it's not hard to maintain. Re Map: Sure, you could store a wrapper object with a count on it.

Collectives™ on Stack Overflow

Javascript - sequencial array-like object

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related