comparing ECMA6 sets for equality

Question

How do you compare two javascript sets? I tried using == and === but both return false.

a = new Set([1,2,3]);
b = new Set([1,3,2]);
a == b; //=> false
a === b; //=> false

These two sets are equivalent, because by definition, sets do not have order (at least not usually). I've looked at the documentation for Set on MDN and found nothing useful. Anyone know how to do this?

Carpo

Two sets are two different objects. === is for value equality, not object equality. – Paigepaik

So how do you compare them then? – Carpo

iterate and compare each member's value, if all same, set is "same" – Bacteriolysis

@Bacteriolysis With sets, the members are the values. – Redingote

@torazaburo: let's pretend that by value, i meant true or false. honestly though, i was thinking of Maps... – Bacteriolysis

Sets and Maps do have an order, which is the insertion order - for whatever reason: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… – Wixted

Worst of all, even new Set([1,2,3]) != new Set([1,2,3]). This makes Javascript Set useless for sets of sets because the superset will contain duplicate subsets. The only workaround that springs to mind is converting all subsets to arrays, sorting each array and then encoding each array as string (for example JSON). – Tan

@CoDEmanX insertion order comes in handy sometimes – Anecdotal

Answer 1

Try this:

const eqSet = (xs, ys) =>
    xs.size === ys.size &&
    [...xs].every((x) => ys.has(x));

const ws = new Set([1, 2, 3]);
const xs = new Set([1, 3, 2]);
const ys = new Set([1, 2, 4]);
const zs = new Set([1, 2, 3, 4]);

console.log(eqSet(ws, xs)); // true
console.log(eqSet(ws, ys)); // false
console.log(eqSet(ws, zs)); // false

Longish

I think you should change the name of has to isPartOf or isIn or elem – Krutz

@Krutz I changed the name of the function has to isIn. – Longish

Is the order of iteration of the set guaranteed? – Connective

@DavidGiven Yes, sets in JavaScript are iterated in insertion order: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… – Longish

@GhasanAl-Sakkaf, I agree, it is maybe that TC39 consists of scientists, but no pragmatists... – Sinker

This answer is the only one that does not reallocate multiple times the set every single time it is compared. Nice job! I find disturbing that so many fellow programmers consider more "idiomatic" something like JSON.stringify([...new Set(aset)].sort()) for an equality. IMO performance of execution (speed AND memory) in this kind of code is far more important than beauty / cleanliness. – Erasmo

@A.Chiesa - In the kindest, gentlest way possible, you are wrong. Unless there is an actual, identified performance problem, it is more important that someone coming along later can read and understand your code than that its performance is optimal. No-one cares about performance so long as it is "good enough"; the time someone spends understanding your code is money, usually quite a lot of money, and lots of people care about it. – Uprush

That's not to say that JSON.stringify([...new Set(aset)].sort()] is a good solution, of course; just that as a general principle, beauty / cleanliness is more important than performance. – Uprush

@Uprush I don't disagree with you, in general. This is why in my comment there is a "in this kind of code". When you build a generic comparer you are making a function that will be changed some times, and used (probably) thousands (millions?). My call is that this kind of function CAN be performance sensitive, so it's not a matter of premature optimization. This kind of simple helper method should be built in a reliable way, and this includes also performance considerations. So, my totally personal opinion is that code general enough to be reused many times should take performance into account. – Erasmo

unfortunately I'm getting a typescript error Type 'Set<string>' can only be iterated through when using the '--downlevelIteration' flag or with a '--target' of 'es2015' or higher. – Livvyy

@FiddleFreak Either set the target in your tsconfig file to es2015 or higher, or enable the downlevelIteration compiler flag if you don't want to target es2015. – Longish

@AaditMShah thx, but unfortunately I work in an environment where linting is locked and it would break the companies internal packages in the node_modules. I found another way around it > const x of Array.from(s1.values()) and using // eslint-disable-next-line no-restricted-syntax. Ultimately, I still think this is a poor solution as it is o(n) lookup during the compare which defeats the purpose of using a set and the given o(1) power it has. As Ghasan said, I really wish javascript had a .equals() off the Set() :( – Livvyy

I like that Ghasanغسان 's comment has more upvotes than the answer itself. – Langford

Answer 2

You can also try:

const a = new Set([1,2,3]);
const b = new Set([1,3,2]);

const areSetsEqual = (a, b) => a.size === b.size && [...a].every(value => b.has(value));

console.log(areSetsEqual(a,b)) 

Bennett

Definitly a better solution as it fits inside an if condition – Airedale

I love how idiomatic this solution is, and how much readable! Thanks @Max – Belgrade

Thanks for making me discover Array.every. However as it does not modify a, why do you need to use [...a], making a copy? – Ettieettinger

every() is part of the array API, it doesn't exist on Set or Iterator – Bennett

Great solution, @MaxLeizerovich ! I'm new to JavaScript, but it seems that the Array methods are much more powerful than the Set's. It would be also nice to have set equality written using the functional programming part of JavaScript. – Alarise

Set is much more efficient, complexity wise. – Bennett

Answer 3

lodash provides _.isEqual(), which does deep comparisons. This is very handy if you don't want to write your own. As of lodash 4, _.isEqual() properly compares Sets.

const _ = require("lodash");

let s1 = new Set([1,2,3]);
let s2 = new Set([1,2,3]);
let s3 = new Set([2,3,4]);

console.log(_.isEqual(s1, s2)); // true
console.log(_.isEqual(s1, s3)); // false

Floorman

Answer 4

you can do the following:

const a = new Set([1,2,3]);
const b = new Set([1,3,2]);

// option 1
console.log(a.size === b.size && new Set([...a, ...b]).size === a.size)

// option 2
console.log([...a].sort().join() === [...b].sort().join())

Benisch

Note that you migth want to join with a "special" separator, to ensure that the set's elements do not contain the seperator. E.g. new Set(["1,2", "3"]) will be equal to new Set([1, 2, 3]) when using , as separator (default). – Nakesha

The new Set([...a, ...b]) is f*king genius :D – Concord

I wonder what the performance of that is, though. – Concord

Answer 5

None of these solutions bring “back” the expected functionality to a data structure such as set of sets. In its current state, the Javascript Set is useless for this purpose because the superset will contain duplicate subsets, which Javascript wrongly sees as distinct. The only solution I can think of is converting each subset to Array, sorting it and then encoding as String (for example JSON).

Solution

var toJsonSet = aset /* array or set */ => JSON.stringify([...new Set(aset)].sort()); 
var fromJsonSet = jset => new Set(JSON.parse(jset));

Basic usage

var toJsonSet = aset /* array or set */ => JSON.stringify([...new Set(aset)].sort()); 
var fromJsonSet = jset => new Set(JSON.parse(jset));

var [s1,s2] = [new Set([1,2,3]), new Set([3,2,1])];
var [js1,js2] = [toJsonSet([1,2,3]), toJsonSet([3,2,1])]; // even better

var r = document.querySelectorAll("td:nth-child(2)");
r[0].innerHTML = (toJsonSet(s1) === toJsonSet(s2)); // true
r[1].innerHTML = (toJsonSet(s1) == toJsonSet(s2)); // true, too
r[2].innerHTML = (js1 === js2); // true
r[3].innerHTML = (js1 == js2); // true, too

// Make it normal Set:
console.log(fromJsonSet(js1), fromJsonSet(js2)); // type is Set

<style>td:nth-child(2) {color: red;}</style>

<table>
<tr><td>toJsonSet(s1) === toJsonSet(s2)</td><td>...</td></tr>
<tr><td>toJsonSet(s1) == toJsonSet(s2)</td><td>...</td></tr>
<tr><td>js1 === js2</td><td>...</td></tr>
<tr><td>js1 == js2</td><td>...</td></tr>
</table>

Ultimate test: set of sets

var toSet = arr => new Set(arr);
var toJsonSet = aset /* array or set */ => JSON.stringify([...new Set(aset)].sort()); 
var toJsonSet_WRONG = set => JSON.stringify([...set]); // no sorting!

var output = document.getElementsByTagName("code"); 
var superarray = [[1,2,3],[1,2,3],[3,2,1],[3,6,2],[4,5,6]];
var superset;

Experiment1:
    superset = toSet(superarray.map(toSet));
    output[0].innerHTML = superset.size; // incorrect: 5 unique subsets
Experiment2:
    superset = toSet([...superset].map(toJsonSet_WRONG));
    output[1].innerHTML = superset.size; // incorrect: 4 unique subsets
Experiment3:
    superset = toSet([...superset].map(toJsonSet));
    output[2].innerHTML = superset.size; // 3 unique subsets
Experiment4:
    superset = toSet(superarray.map(toJsonSet));
    output[3].innerHTML = superset.size; // 3 unique subsets

code {border: 1px solid #88f; background-color: #ddf; padding: 0 0.5em;}

<h3>Experiment 1</h3><p>Superset contains 3 unique subsets but Javascript sees <code>...</code>.<br>Let’s fix this... I’ll encode each subset as a string.</p>
<h3>Experiment 2</h3><p>Now Javascript sees <code>...</code> unique subsets.<br>Better! But still not perfect.<br>That’s because we didn’t sort each subset.<br>Let’s sort it out...</p>
<h3>Experiment 3</h3><p>Now Javascript sees <code>...</code> unique subsets. At long last!<br>Let’s try everything again from the beginning.</p>
<h3>Experiment 4</h3><p>Superset contains 3 unique subsets and Javascript sees <code>...</code>.<br><b>Bravo!</b></p>

Tan

Great solution! And if you know that you've just got a set of strings or numbers, it just becomes [...set1].sort().toString() === [...set2].sort().toString() – Ajar

unfortunately I do not have time to review this right now, but most solutions which sort keys of js collections using the built-in default i.e. .sort() are wrong because there is no total order on js objects, e.g. NaN!=NaN, '2'<3 (coercion), etc. – Jackstraws

Answer 6

I believe this is the most performant version because it's not creating a new array, it's using the Set's own iterator:

function isEqualSets(a, b) {
  if (a === b) return true;
  if (a.size !== b.size) return false;
  for (const value of a) if (!b.has(value)) return false;
  return true;
}

Update - Safari has added native experimental Set methods, so when this is implemented across all browsers we can do:

function isEqualSets(a, b) {
  return a.size === b.size && a.isSubsetOf(b);
}

Logicize

The only solution here that does not create an auxiliary array of all set members – Rap

This doesn't check order – Dinerman

As the original question explains, it's not necessary to check order. – Logicize

Answer 7

The other answer will work fine; here is another alternative.

// Create function to check if an element is in a specified set.
function isIn(s)          { return elt => s.has(elt); }

// Check if one set contains another (all members of s2 are in s1).
function contains(s1, s2) { return [...s2] . every(isIn(s1)); }

// Set equality: a contains b, and b contains a
function eqSet(a, b)      { return contains(a, b) && contains(b, a); }

// Alternative, check size first
function eqSet(a, b)      { return a.size === b.size && contains(a, b); }

However, be aware that this does not do deep equality comparison. So

eqSet(Set([{ a: 1 }], Set([{ a: 1 }])

will return false. If the above two sets are to be considered equal, we need to iterate through both sets doing deep quality comparisons on each element. We stipulate the existence of a deepEqual routine. Then the logic would be

// Find a member in "s" deeply equal to some value
function findDeepEqual(s, v) { return [...s] . find(m => deepEqual(v, m)); }

// See if sets s1 and s1 are deeply equal. DESTROYS s2.
function eqSetDeep(s1, s2) {
  return [...s1] . every(a1 => {
    var m1 = findDeepEqual(s2, a1);
    if (m1) { s2.delete(m1); return true; }
  }) && !s2.size;
}

What this does: for each member of s1, look for a deeply equal member of s2. If found, delete it so it can't be used again. The two sets are deeply equal if all the elements in s1 are found in s2, and s2 is exhausted. Untested.

You may find this useful: http://www.2ality.com/2015/01/es6-set-operations.html.

Redingote

Answer 8

If sets contains only primitive data types or object inside sets have reference equality, then there is simpler way

const isEqualSets = (set1, set2) => (set1.size === set2.size) && (set1.size === new Set([...set1, ...set2]).size);

Bitterroot

Answer 9

Comparing two objects with ==, ===

When using == or === operator to compare two objects, you will always get false unless those object reference the same object. For example:

var a = b = new Set([1,2,3]); // NOTE: b will become a global variable
a == b; // <-- true: a and b share the same object reference

Otherwise, == equates to false even though the object contains the same values:

var a = new Set([1,2,3]);
var b = new Set([1,2,3]);
a == b; // <-- false: a and b are not referencing the same object

You may need to consider manual comparison

In ECMAScript 6, you may convert sets to arrays beforehand so you can spot the difference between them:

function setsEqual(a,b){
    if (a.size !== b.size)
        return false;
    let aa = Array.from(a); 
    let bb = Array.from(b);
    return aa.filter(function(i){return bb.indexOf(i)<0}).length==0;
}

NOTE: Array.from is one of the standard ECMAScript 6 features but it is not widely supported in modern browsers. Check the compatibility table here : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from#Browser_compatibility

Stria

Won't this fail to identify member of b which are not in a? – Redingote

@torazaburo Indeed. The best way to skip checking whether members of b are not in a is to check whether a.size === b.size. – Longish

Also, use var a = new Set([1,2,3]), b = a;. Otherwise, you are making b a global variable. – Longish

Very good spot and suggestions from you all. When declaring a = b = something surely b will become a global variable. Let me update the note. – Stria

Put a.size === b.size first to short-circuit the comparison of individual elements if not necessary? – Redingote

@torazaburo When a = [1,2,3] and b = [3,4,5, a.size === b.size is true, isn't it? We should check the elements in one leg first, then just check if both sets have exactly the same size. – Stria

If size is different, by definition the sets are not equal, so it's better to check that condition first. – Redingote

Ah, I misunderstood the point you raised. Very good suggestion. Let me update it. – Stria

Well, the other issue here is that by the nature of sets, the has operation on sets is designed to be very efficient, unlike the indexOf operation on arrays. Therefore, it would make sense to change your filter function to be return !b.has(i). That would also eliminate the need to convert b into an array. – Redingote

Let us continue this discussion in chat. – Stria

Ow, aa.filter(function(i){return bb.indexOf(i)<0}).length==0; really hurts - given that there's every/some and we have a set b with constant-time access :-/ – Krutz

@TaoP.R.: “Page not found”. So much for using chat as a replacement for comments. What is even the point of Stack Overflow? Let’s make answers viewable only to askers too. – Tan

Turning sets to arrays for comparison makes this O(n^2), which defeats the purpose of having sets in the first place – Trinitytrinket

Answer 10

I created a quick polyfill for Set.prototype.isEqual()

Set.prototype.isEqual = function(otherSet) {
    if(this.size !== otherSet.size) return false;
    for(let item of this) if(!otherSet.has(item)) return false;
    return true;
}

Github Gist - Set.prototype.isEqual

Lithographer

Answer 11

Based on the accepted answer, assuming support of Array.from, here is a one-liner:

function eqSet(a, b) {
    return a.size === b.size && Array.from(a).every(b.has.bind(b));
}

Talc

Or a true one-liner assuming arrow functions and the spread operator: eqSet = (a,b) => a.size === b.size && [...a].every(b.has.bind(b)) – Talc

Answer 12

Very slight modification based on @Aadit M Shah's answer:

/**
 * check if two sets are equal in the sense that
 * they have a matching set of values.
 *
 * @param {Set} a 
 * @param {Set} b
 * @returns {Boolean} 
 */
const areSetsEqual = (a, b) => (
        (a.size === b.size) ? 
        [...a].every( value => b.has(value) ) : false
);

If anyone else is having an issue as I did due to some quirk of the latest babel, had to add an explicit conditional here.

(Also for plural I think are is just a bit more intuitive to read aloud 🙃)

Kalmar

Answer 13

The reason why your approach returns false is because you are comparing two different objects (even if they got the same content), thus comparing two different objects (not references, but objects) always returns you falsy.

The following approach merges two sets into one and just stupidly compares the size. If it's the same, it's the same:

const a1 = [1,2,3];
const a2 = [1,3,2];
const set1 = new Set(a1);
const set2 = new Set(a2);

const compareSet = new Set([...a1, ...a2]);
const isSetEqual = compareSet.size === set2.size && compareSet.size === set1.size;
console.log(isSetEqual);

Upside: It's very simple and short. No external library only vanilla JS

Downside: It's probably going to be a slower than just iterating over the values and you need more space.

Gangrene

Answer 14

With Ramda : equals(set1, set2)

const s1 = new Set([1, 2, 3]);
const s2 = new Set([3, 1, 2]);

console.log( R.equals(s1, s2) );

<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js"></script>

Turnspit

Answer 15

There's a stage 3 ECMAScript proposal that makes this a lot easier (though curiously it does not contain a specific equality check either).

These methods are supported in current Chrome and Safari, and would allow you to compare two sets (a and b) for equality with expressions like:

• a.size == b.size && a.size == a.union(b).size
• a.isSupersetOf(b) && a.isSubsetOf(b)
• (shorter but in my view less clear) a.symmetricDifference(b).size == 0

... whichever reads easiest to you, unless you're using large sets. I haven't performance-tested any of them.

Mothy

Answer 16

I follow this approach in tests :

let setA = new Set(arrayA);
let setB = new Set(arrayB);
let diff = new Set([...setA].filter(x => !setB.has(x)));
expect([...diff].length).toBe(0);

Neel

Wait a sec... this only checks whether A has elements that B doesn't? It doesn't check whether B has elements that A doesn't. If you try a=[1,2,3] and b=[1,2,3,4], then it says they're the same. So I guess you need an extra check like setA.size === setB.size – Ajar

Answer 17

None of the existing answers check the Set's insertion order, so here's one that does. It uses lodash _.isEqualWith to do shallow checking (since _.isEqual does deep checking and is slow for sets)

import isEqualWith from 'lodash/isEqualWith';

export function setsAreEqual (setA: Set<unknown>, setB: Set<unknown>): boolean {
    return isEqualWith(setA, setB, (a: unknown, b: unknown) => {
        if (a === setA) return undefined;
        return a === b;
    });
}

Dinerman

if you care about order you're kinda using sets wrong – Extinct

Differing opinions exist. In particular, the authors of the spec who designed Set to allow for ordered retrieval. – Dinerman

Answer 18

If you want to allow the option of using a custom comparer besides ===:

function setEquals(x, y, comparer) { 
  if (!comparer) {
    return x.size === y.size
      && [...x].every(a => y.has(a));
  }

  return x.size === y.size
    && [...x].every(a => [...y].some(b => comparer(a, b)));
}

This will still work the same as the other methods if you don't pass a comparer, but you have the option of passing a custom comparison method like (a, b) => a.id === b.id.

Gwenny

Answer 19

1) Check if sizes are equal . If not, then they are not equal.

2) iterate over each elem of A and check in that exists in B. If one fails return unequal

3) If the above 2 conditions fails that means they are equal.

let isEql = (setA, setB) => {
  if (setA.size !== setB.size)
    return false;
  
  setA.forEach((val) => {
    if (!setB.has(val))
      return false;
  });
  return true;
}

let setA = new Set([1, 2, {
  3: 4
}]);
let setB = new Set([2, {
    3: 4
  },
  1
]);

console.log(isEql(setA, setB));

2) Method 2

let isEql = (A, B) => {
  return JSON.stringify([...A].sort()) == JSON.stringify([...B].sort());
}

let res = isEql(new Set([1, 2, {3:4}]), new Set([{3:4},1, 2]));
console.log(res);

Steiermark

This answer is completely incorrect. The return statement in the forEach method will NOT make the parent function return. – Sedimentary