Javascript Map ordering

Question

i recently had a bug in my code that was due to me missing the "in insertion order" text while looking through Map object details on MDN. In short, i have a map object, lets say

let myMap = new Map;

and then, after populating it, i iterate over its contents with a simple for .. of statement. Like this

for (let [key, val] of myMap) { 
    ...
}

The code in for loop depends on (key, value) pair to be sorted by key. However the algorithm that populates the map, does so in a random order(and i can't change that). To get around this problem, i now add all possible keys to the map object first, something like this:

let myMap = new Map;
for (let i=0; i<maxkey; ++i) myMap.set(key(i), undefined);

// And in the for loop
for (let [key, val] of myMap) {
    if (typeof val === "undefined") continue;
    //...
}

Fortunately, there aren't many of them(so the performance penalty is negligible), and this works. Still this solution looks a bit awkward to me.

Is there something better?

Convert it to an array and sort it. `[...map].sort(([k1], [k2]) => k1.localeCompare(k2))` — Aluan Haddad, Apr 27 '18 at 19:23
array of type [{key: T, value: V}], then arr.sort((a, b) => compare(a.key, b.key)) ? — Pavel Beliy, Apr 27 '18 at 19:36

Bergi · Answer 1 · 2020-10-31T15:57:09.643

The code in for loop depends on (key, value) pair to be sorted by key.

Then a Map is the wrong data structure for you. Its purpose is fast lookup, not maintaining an order. If you need an ordered (sortable) sequence, use an array. Or if you need both lookup and custom order, then use both in combination. For your particular case with a small number of known keys, pre-populating the map is fine, alternatively use them only for the iteration

for (let key=0; key < maxkey; key++) {
    if (myMap.has(key)) {
        const val = myMap.get(key);
        … // use key and value
    }
}

Or if there are much more keys than stored in the map, you can also do

for (const key of Array.from(myMap.keys()).sort((a, b) => a-b)) {
    const val = myMap.get(key);
    … // use key and value
}

If you have to do this more than once, you might also want to implement your own iterator.

Maps *do* maintain an order, the order of insertion. What you want to say is that maps don't remain *sorted*. An array's order is the same as a map, unless you explicitly use the `sort` method. — David Callanan, Oct 31 '20 at 12:21
@DavidCallanan Yes, that's what I meant to say - maps cannot be reordered. And even if they do use a fixed order for consistency, being ordered is not their main purpose. — Bergi, Oct 31 '20 at 15:59

score 3 · Answer 2 · answered Apr 27 '18 at 21:42

3

The ordering of keys in a map depends on the map implementation. A map with naturally ordered keys is often called a tree map because the keys are stored in a tree. I have not used a tree map in JS so I can't recommend a particular implementation.

answered Apr 27 '18 at 21:42

StackOverthrow

1,158
11
23

score 3 · Answer 3 · answered Nov 13 '21 at 05:36

3

According to mozilla javascript reference here

A Map object iterates entries, keys, and values in the order of entry insertion.

so you should sort the keys before insert them into the map, then you can iterate the map in key order.

answered Nov 13 '21 at 05:36

wsysuper

146
6

Javascript Map ordering

3 Answers3

Linked