DeepSet

DeepSet

A Set that decides membership by structure rather than by reference, so has answers the question new Set() cannot: is a value like this one already in here? deepEqual defines "like", exactly as it does for dedupe, and the two share one bucket-then-verify pass — a DeepSet is that pass kept instead of thrown away.

Reach for it when the same unchanging pile is asked about repeatedly. arr.some(x => deepEqual(x, value)) beats it outright for a single lookup: a fold has to read the whole value before it can say a word, where deepEqual abandons most candidates after a key or two. Building the index only pays back across queries, from around thirty of them, and that figure barely moves between a thousand values and a hundred thousand — build and scan both scale with the pile, so their ratio does not. bench/dedupe/membership.bench.mjs regenerates it.

A value must not be mutated while it is in here. Membership is decided by contents, so changing a value changes the bucket it should live in while it sits in the old one, and it becomes unfindable — by has, by delete, and by its own reference. new Set() has no such rule, because reference identity survives mutation and structure does not. Add copies if the originals move.

Insertion order is preserved and the first occurrence of every distinct value is the one kept, so [...new DeepSet(arr)] is dedupe(arr). Values are held as given, -0 included — the platform's Set normalises that to 0 and this does not, which is why an array backs the order rather than a Set.

Two DeepSets are never deepEqual to each other: their members live in private fields a structural walk cannot reach, and refusing is better than the wrong answer that walk would otherwise give. Compare [...a] and [...b].

delete is the one method that costs more here than on a native Set: insertion order is an array, so the value has to be found in it and spliced out, which is linear in the size of the set against the O(1) the name implies. Occasional removal is fine; dropping many values at once is cheaper as a rebuild from a filtered iteration. clear pays nothing — it drops both halves whole.

Constructor

new DeepSet(valuesopt)

Source:
Parameters:
Name Type Attributes Description
values Iterable <optional>

Values to add, in order; duplicates are dropped
Example
const seen = new DeepSet([{ a: 1 }, { b: 2 }])
seen.has({ a: 1 })          // => true — a different object, same structure
seen.has({ a: 2 })          // => false
seen.add({ b: 2 }).size     // => 2 — already present, not added again
seen.delete({ a: 1 })       // => true — again, structure and not reference
[...new DeepSet([{ a: 1 }, { a: 1 }])]  // => [{ a: 1 }]

Classes

DeepSet

Members

size

Source:

Methods

add(value) → {DeepSet}

Adds a value unless one structurally equal to it is already held, in which case the one already here stays and this call changes nothing.

Source:
Parameters:
Name Type Description
value *

The value to add
Returns:
Type:
DeepSet

This set, so calls chain

clear() → {void}

Removes every value, leaving the set reusable.

Source:
Returns:
Type:
void
Example
const seen = new DeepSet([{ a: 1 }])
seen.clear()
seen.size  // => 0

delete(value) → {boolean}

Removes the held value structurally equal to the one given, if there is one. Linear in the size of the set — see the note on the class.

Source:
Parameters:
Name Type Description
value *

The value to remove
Returns:
Type:
boolean

True when a value was removed, false when none matched

Example
const seen = new DeepSet([{ a: 1 }])
seen.delete({ a: 1 })  // => true — a different object, same structure
seen.delete({ a: 1 })  // => false — nothing left to match

has(value) → {boolean}

Source:
Parameters:
Name Type Description
value *

The value to look for
Returns:
Type:
boolean

True when a structurally equal value is already held