Implementing a set that treats object equality on value not reference

Question

I want to be able to implement a Set in javascript that allows me to do something like this:

const s = Set([[1,2,3], [1,2,3], 1, 2, 1]);
s.add([1,2,3]);
console.log(s);
// {[1,2,3], 1, 2}

Of course, since the === operator is used on the set, any object will not equal itself unless a reference to the same object is passed, and so instead of the above we would currently get:

Set(5) { [ 1, 2, 3 ], [ 1, 2, 3 ], 1, 2, [ 1, 2, 3 ] }

Does the following seem like a good way to implement this? What might I be missing or can improve on?

class MySet extends Set {
    constructor(...args) {
        super();
        for (const elem of args) {
            if (!this.has(elem)) super.add(elem);
        }
    }
    has(elem) {
        if (typeof elem !== 'object') return super.has(elem);
        for (const member of this) {
            if (typeof member !== 'object') continue;
            if (JSON.stringify(member) === JSON.stringify(elem))
                return true;
        }
        return false;
    }
    add(elem) {
        return (this.has(elem)) ? this : super.add(elem);
    }
    delete(elem) {
        if (typeof elem !== 'object') return super.delete(elem);
        for (const member of this) {
            if (typeof member !== 'object') continue;
            if (JSON.stringify(member) === JSON.stringify(elem))
                return super.delete(member);
        }
        return false;
    }
}

Aside from the Set angle, you're basically asking how to implement a deep equality check. There isn't a good generic way to do this (if there was it would already exist in the language). You're using `JSON.stringify` here but what if your object isn't JSON serialisable? And this will (I think) consider objects different if they have the same keys and same values but in a different order (if you define them both as object literals), which presumably isn't what you want. — Robin Zigmond, May 09 '22 at 17:04
1. `JSON.stringify` is not at all reliable way to check if objects have similar values. 2. This implementation has linear complexity, as opposed to the sub-linear that the spec guarantees for `Set`. 3. General review questions should go to [codereview.se] SO is for question about *specific* problems with code. — VLAZ, May 09 '22 at 17:05
I think the right way to approach this would be to start from what you're trying to do; from what your application needs are. Trying to force the language to do something it doesn't want to do is usually a terrible idea. As other comments have noted, `JSON.stringify()` is not a good approach, for a list of reasons. — Pointy, May 09 '22 at 17:07
See [How to determine equality for two JavaScript objects?](https://stackoverflow.com/questions/201183/how-to-determine-equality-for-two-javascript-objects) and [Object comparison in JavaScript](https://stackoverflow.com/questions/1068834/object-comparison-in-javascript). — MikeM, May 09 '22 at 17:12
Putting aside the deep equality problem for a sec, it would be nice to have a set constructed with an optional predicate for uniqueness. The predicate would take two args and return true if they should be considered equal. You'd have an O(n) insertion, but but a nice general purpose tool. — danh, May 09 '22 at 19:29

3limin4t0r · Answer 1 · 2022-05-09T19:31:07.417

Assuming the provided objects don't contain values that cannot be stringified to JSON (function, undefined, symbol, etc.) You can use JSON.stringify().

One problem you might encounter is that stringifying { a: 1, b: 2 } doesn't produce the same result as { b: 2, a: 1 }. A fairly easy way to solve this would be to stringify the object and make sure the resulting JSON has properties placed in alphabetical order.

For this we can look to the answer provided in sort object properties and JSON.stringify.

I also think you are over complicating things by only stringifying values if they are an object. Instead you could just stringfy everything, null would result in "null", "string" would result in '"string"', etc. This simplifies the code by a lot. The only restriction then becomes that all values must be a valid JSON value.

// see linked answer
function JSONstringifyOrder(obj, space)
{
    const allKeys = new Set();
    JSON.stringify(obj, (key, value) => (allKeys.add(key), value));
    return JSON.stringify(obj, Array.from(allKeys).sort(), space);
}

class MySet extends Set {
    // The constructor makes uses of add(), so we don't need
    // to override the constructor.

    has(item) {
        return super.has(JSONstringifyOrder(item));
    }
    
    add(item) {
        return super.add(JSONstringifyOrder(item));
    }
    
    delete(item) {
        return super.delete(JSONstringifyOrder(item));
    }
}


const set = new MySet([[1,2,3], [1,2,3], 1, 2, 1]);
set.add([1,2,3]);
set.add({ a: { s: 1, d: 2 }, f: 3 });
set.add({ f: 3, a: { d: 2, s: 1 } });

// Stack Overflow snippets cannot print Set instances to the console
console.log(Array.from(set));
// or unserialized
Array.from(set, json => JSON.parse(json)).forEach(item => console.log(item));

Implementing a set that treats object equality on value not reference

1 Answers1