Set of pairs of numbers in Javascript

Question

ES6 has a new Set data structure for storing sets of unique objects. However it is based on object references as opposed to value comparisons. As far as I can tell this makes it impossible to have a set of pairs of numbers without stringifying.

For example, typing in Chrome's console (needs Chrome 38+):

> var s = new Set();
< undefined
> s.add([2, 3]);
< Set {[2, 3]}
> s.has([2, 3])
< false          <--- was hoping for 'true'

This appears to be by design: since I passed a different array of [2, 3] to has(), it returns false, because although the contents is the same it only looks at object references, and I allocated a new and different array to pass to has(). I would need to store a reference to the original array I passed to add() to check with has(), but this is not always possible. For example if the number pairs represent co-ordinates, I might need to check if the set has [obj.x, obj.y], but this will always return false since it allocates a new array.

The workaround is to stringify the arrays and key on strings like "2, 3" instead. However in something performance-sensitive like a game engine, it is unfortunate if every set access needs to make a string allocation and convert and concatenate number strings.

Does ES6 provide any feature to solve this problem without stringifying, or is there any feature on the horizon with ES7 that could help as well?

Answer 1

It is not perfectly optimal for very compute-intensive tasks, but you could use a concatenated string using template literals for a more idiomatic approach that still maintains efficiency, e.g.

set.add(`${x}_${y}`);

and retrieval:

set.get(`${i}_${j}`);

(note I've purposely avoided use of , as a delimeter since it can be confusing in some fields such as finance).

Another thing that could be done is grabbing the width of the first dimension to flatten an array if you know the bounds e.g.

set.get(x+y*width);

or if you're working with small numbers in general (not exceeding 10,000s) and don't know what the max width would be, you could use an arbitrary very large number. This is slightly less optimal but still better than string concat:

set.get(x+y*Math.floor(Math.sqrt(Number.MAX_SAFE_INTEGER)));

Again, these are not perfect solutions since they do not work with very large numbers where x*y may exceed Number.MAX_SAFE_INTEGER, but they are some things in your toolbox without needing to know a fixed array size.

[Super late here, but since ES7 had not fixed things after all and I noticed this was not specifically mentioned if others are weighing the pros/cons, two approaches (the first explicitly does not solve, the second may possibly)]

Answer 2

As you've noted [2, 3] === [2, 3] is false, meaning you can't use Set like this; however, is Set really the best option for you?

You may find that using a two-level data structure like this will be better for you

var o = {};

function add(o, x, y) {
    if (!o[x]) o[x] = {};
    o[x][y] = true;
}

function has(o, x, y) {
    return !!(o[x] && o[x][y]);
}

function del(o, x, y) {
    if (!o[x]) return;
    delete o[x][y];
    // maybe delete `o[x]` if keys.length === 0
}

You could do a similar structure with a Map pointing to Sets if you wanted to use ES6