The way, in which data is structured, plays a vital role in being able to efficiently perform certain operations on the data or solve certain problems in relation to the data. For example you can delete any item from a doubly linked list in constant time, whereas that could take linear time if the list is represented as an array. Also, searching for the presence of a key in an array of keys can be done more efficiently (in logarithmic time) when the array is sorted than when not sorted.
Some very popular programming languages like Java and Python provide lots of useful data structure implementations out of the box, as part of their standard library; whereas the ubiquitous "JavaScript" programming language appears to be pretty lean in that regard. However, like most programming languages, JavaScript ships with some very basic data types — such as arrays, strings, objects, sets, maps, etc.
Prior to the ECMAScript 2015 specification updates (popularly known as ES6), JavaScript provided Array objects as the only standard built-in indexed collections — although there were other exotic objects such as the arguments object and String objects, that behaved like arrays with special handling for integer index property keys (usually referred to as array-like objects), but were not really indexed collections.
Moving forward, starting from ES6, a handful of new standard built-in types has been added to JavaScript, such as: Symbol, Promise, Proxy, as well as a number of typed array objects (which, just like arrays, are also indexed collections themselves). In addition to these, a new category of collections known as keyed collections has also been added to the language, with these built-in object types: Map, Set, WeakMap and WeakSet.
Just as the name implies, every element (known as an entry) in a keyed collection can be identified by some kind of key, such that the keys in the collection are distinct — so that every key maps exactly to one entry in the collection. If you are familiar with hash tables, then you might have already inferred their usefulness here in ensuring that the average access time is sublinear on the number of elements in the collection.
In this post, we'll take a peek into how we can leverage JavaScript Map and Set objects to efficiently solve problems. But before we jump right in, let's consider a sample problem.
Contains Duplicates Given an array of integers
nums, returntrueif any element appears at least twice in the array, and returnfalseif every element is distinct.
Pause for a moment and try solving this problem on your own, before you proceed. If the nums array was sorted, will that simplify the solution?
Now, here is a working solution to the problem:
function hasDuplicates(nums) {
// 1. Sort the array in-place (sorting makes it easier)
nums.sort((a, b) => a - b);
if (nums.length > 1) {
// 2. Loop through the sorted array until a duplicate is found
for (let i = 1, len = nums.length; i < len; i++) {
// If a duplicate is found, return immediately
if (nums[i] == nums[i - 1]) return true;
}
}
// 3. If it ever gets here, no duplicate was found
return false;
}There is no doubt that this solution works (for the given constraints of our problem). The reasoning behind why it should work is quite straightforward — if the array of integers is already sorted, then it is possible to check (in a single pass) whether there exists two consecutive equal integers in the array. And since there isn't any guarantee that the array of integers will already be sorted, the solution first tries to sort the array, before checking for duplicate integers.
Here is some analysis of the above solution:
-
The running time of the solution will grow in linearithmic fashion as the size of the input array grows. While this is not a bad thing, it's not so great as well — the reason being that, even for an already sorted array, it would still take a significant amout of time. This is due to the fact, that a lot of time is spent trying to first sort the array.
-
The solution uses
Array.prototype.sortto sort the input array in-place — modifying the original input array as a result. Hence, no auxiliary space (additional memory) is required for the sort. It is important to note however that, if the problem required that the original order of the input array remain unchanged, then a copy of the input array must be made before using this solution — which is tantamount to the use of additional memory that will grow in linear fashion as the size of the input array grows.
Now, whether this is an acceptable solution or not is subject to a number of factors — including but not limited to the constraints on the problem (such as the maximum size the problem's input), the constraints on computational resources (such as available machine memory), acceptable trade-offs (such as accepting the use of auxiliary space if that will potentially improve the running time), etc.
If we are certain that the array of integers might not already be sorted, and we also don't mind using some auxiliary space — provided we can get a faster running time, then this solution is not the best of solutions. As we progress, we will soon see that we can actually come up with a solution whose running time grows linearly (rather than linearithmically) with the size of the input.
The ECMAScript specification definition of a Map object can be summarized as follows:
-
It is a collection of key/value pairs. A collection of key/value pairs where both the keys and values may be arbitrary ECMAScript language values. It is an ordered collection, hence the insertion order of its elements matters, and is followed when iterating the collection.
-
Keys in the collection are distinct or unique. A key value may only occur in one key/value pair within the Map's collection. Hence every key in the collection may occur only once with respect to the ECMAScript SameValueZero comparison algorithm.
That means any valid JavaScript value can be used as a key in a Map object collection — both primitive values and object references, including unseemly values like NaN and undefined.
To determine whether a key already exists in the Map object collection (in other words ensuring that keys are distinct), the ECMAScript SameValueZero comparison algorithm is used.
If Strict Equality comparison algorithm were to be used, then it will be impossible to determine whether a key of value NaN already exists in the collection, since NaN === NaN always evaluates to false.
If SameValue comparison algorithm were to be used, then it becomes possible to determine whether a key of value NaN already exists in the collection. However, the keys +0 and -0 will be taken to be different keys, although +0 === -0 always evaluates to true.
The SameValueZero comparison algorithm however behaves like the SameValue comparison algorithm, except that it considers both +0 and -0 to be the same key. If the SameValueZero comparison algorithm were to be implemented as a JavaScript function, it will look like this:
function SameValueZero(x, y) {
return x === y || (Number.isNaN(x) && Number.isNaN(y));
}Each key/value pair contained in a Map object collection is usually referred to as an entry object (or simply entry). An entry object is usually represented using a two element array (more like a tuple in most other programming languages), whose first element is the key and whose second element is the value.
The type definition for a generic Map object entry should look like this (in TypeScript):
type MapEntry<Key, Value> = [Key, Value];That said, you can use JavaScript syntax such as destructuring assignment on a Map object entry (like you would with an array) as demonstrated in the following for...of loop example:
/**
* Iterating over entries of `Map` object using a
* `for...of` loop — assuming that `map` has been
* defined already as a `Map` object.
*/
for (const [key, value] of map) {
console.log(key, value);
}Both Map and Set objects inherit an entries() method from their corresponding constructors' prototype objects. This entries() method returns an iterator for all the entries contained in the collection with respect to their insertion order. For Map objects however, the iterator returned by the entries() method also serves as the default iterator of the collection.
At the time of this writing, the only way to create a Map object is by invoking the global Map constructor function. The constructor function must be invoked with the new keyword — otherwise, a TypeError will be thrown. When the Map constructor function is invoked without arguments, an empty Map object of 0 size is returned.
// Throws a `TypeError` — when invoked without `new` keyword
const throwTypeErrorMap = Map();
// Creates an empty `Map` object of 0 `size`
const mapA = new Map();
// Omitting the parentheses — when invoked without arguments
// Also creates an empty `Map` object of 0 `size`
const mapB = new Map;
console.log(mapA.size); // 0
console.log(mapB.size); // 0The Map constructor function can also be invoked with an optional iterable argument. When specified, iterable must be a JavaScript object that:
-
properly implements the iterable protocol. Many built-in JavaScript objects implement this protocol — such as
Array,String,Setand evenMap. -
returns an iterator object that produces a two element array-like (entry) object whose first element is a value that will be used as a
Mapkey and whose second element is the value to associate with that key.
If the iterable argument does not meet these two requirements, a TypeError will be thrown — the only exception being when iterable is the value null or undefined, in which case the effect is the same as calling the Map constructor function without any argument — hence creating an empty Map object of 0 size.
Paying more attention to the second requirement stated above, it is very obvious that a new Map object cannot be created from a string primitive, even though String objects are iterable objects themselves.
// Map from String — throws a `TypeError`
const throwTypeErrorMap = new Map("programming");In creating a new Map object from another iterable object, an empty Map object is first created, and then the following steps are taken for each entry object produced by the iterator object returned by the iterable:
-
Extract the first and second elements from the entry object as
keyandvaluerespectively. -
Check if an entry with
keyalready exists in theMapobject collection using SameValueZero comparison. If it exists, update the entry's current value tovalue. Otherwise, append a new entry to the end of theMapobject collection with thatkeyandvalue. Ifkeyis-0, it is changed to+0before appending a new entry to the collection.
const pairs = [[1, 3], [3, 3], [4, 2], [2, 2]];
// (1) Map from Array or Set
// Here a set is created from the `pairs` array and
// used to create the map. However, the map can also
// be created directly from the `pairs` array.
const mapA = new Map(new Set(pairs));
console.log(mapA.size); // 4
console.log(...mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
// (2) Map from Map
// New map contains all the items of the original map
// However, both maps are entirely different objects.
// Think of it as creating a clone of a map.
const mapB = new Map(mapA);
console.log(...mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
console.log(...mapB); // [1, 3] [3, 3] [4, 2] [2, 2]
console.log(mapA === mapB); // false
console.log(mapA.size === mapB.size); // true
// (3) Map from Object
// In ES6, the `Object.entries()` method was added,
// and it returns an array of entries representing
// key/value pairs for every key in an object.
const mapC = new Map(Object.entries({
language: "JavaScript",
hello: "world"
}));
console.log(mapC.size); // 2
console.log(...mapC); // ["language", "JavaScript"] ["hello", "world"]Now that we are able to create new Map objects, let's go ahead to explore their instance properties and methods.
Already, we've seen the size property in action a couple of times. The size property, just as the name implies, returns the number of entries in the Map object at any instant. It might interest you to know that the size property is an accessor property and not a data property. Also, it only has a get accessor function and not a set accessor function. That's the reason why its value cannot be overriden by an assignment operation.
Whenever you access the size property of a Map object, its get accessor function will be invoked — which basically counts and returns the number of elements (entries) currently in the Map object.
There are several cases where it is sufficient just to know whether an entry with a particular key is present in a Map object or not. Every Map object will originally have a has() method — which can be called to assert whether an entry with a specified key is present in the Map object or not. The has() method returns a boolean value — true if the specified key is present, and false otherwise.
const M = new Map(Object.entries({
language: "JavaScript",
hello: "world"
}));
console.log(M.has("hello")); // true
console.log(M.has("Hello")); // false
console.log(M.has("language")); // true
console.log(M.has("world")); // falseBeyond checking whether a key exists in a Map object, being able to read the value of the entry associated with that key is also very important. As such, every Map object initially have a get() method for this purpose. When the get() method is called with a key for which no entry exists, it returns undefined.
const M = new Map(Object.entries({
language: "JavaScript",
hello: "world"
}));
console.log(M.get("hello")); // "world"
console.log(M.get("Hello")); // undefined
console.log(M.get("language")); // "JavaScript"
console.log(M.get("world")); // undefinedAlthough the get() method returns undefined for non-existent keys, it should not be relied upon in checking for the existence of a key in a Map collection, seeing that it is also possible for a key in the collection to have a value of undefined associated with it. Hence, the most accurate way to determine the existence of a key in the collection is to use the has() method.
Being able to add, update or remove one or more entries from a Map object is very nontrivial, hence every Map object will originally have set(), delete() and clear() methods.
The set() method takes a JavaScript value as its argument, and will append that value to the end of the Set object — provided it isn't already in the Set object. If the specified value is already in the Set object, it is ignored. The add() method returns the same Set object (with the added value), making it amenable to method chaining (invoking multiple add() calls at once).
The delete() method, on the otherhand, will remove the entry associated with the specified key from the Map object — provided their is such an entry in the Map object. If an entry is actually removed from the Map object as a result of this delete operation, it returns true, otherwise it returns false.
It might be useful in some cases to empty a Map object completely — by removing all the entries in the Map object. While this can be achieved through multiple delete() calls on the Map object, it will make more sense if this could be done in a single method call — and that is exactly what the clear() method does. A call to the clear() method empties the Map object and returns undefined.
// Convert object to map
const M = new Map(Object.entries({
language: "JavaScript"
}));
console.log(M.size); // 1
console.log(...M); // ["language", "JavaScript"]
// (1) Add and update some map entries
M.set("year", 1991);
M.set("language", "Python");
console.log(M.size); // 2
console.log(...M); // ["language", "Python"] ["year", 1991]
// (2) Add or update several values at once (using chaining)
M.set("version", 3)
.set("year", 2000)
.set("version", "2.0");
console.log(M.size); // 3
console.log(...M); // ["language", "Python"] ["year", 2000] ["version", "2.0"]
// Delete some entries from the map
console.log(M.delete("Year")); // false
console.log(M.delete("year")); // true
console.log(M.delete("year")); // false
console.log(M.delete("version")); // true
console.log(M.size); // 1
console.log(...M); // ["language", "JavaScript"]
// Empty the map
M.clear();
console.log(M.size); // 0One other thing we might want to do with a Map object is to have a view into the keys, values or even the entries that are in it. You can loop through each entry in a Map object (in insertion order) using the for...of loop. This is because every iterable has a [Symbol.iterator] method that returns its default iterator — which is responsible for producing the sequence of values for the loop. Besides the for...of loop, the same sequence of values returned by the default iterator is what the spread operator (...), the yield* statement, and destructuring assignment are based on.
We've already seen the entries() method, which returns an iterator for all the entries in a Map object with respect to their insertion order. As stated earlier, the iterator returned by the entries() method also serves as the default iterator of a Map object.
That said, the two for...of loops shown in the following code snippet are the same and will produce the exact same sequence of values:
const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);
// (a) Iteration using the default iterator (`[Symbol.iterator]`)
for (const [key, value] of M) {
console.log(key, value);
}
// (b) Iteration using the `entries()` iterator
for (const [key, value] of M.entries()) {
console.log(key, value);
}It is important to note that an iterable object could provide other iterators, besides the default iterator provided by its [Symbol.iterator] method. This holds true for most built-in iterables in JavaScript, including Map objects. In fact, every Map object originally has three methods that return iterators, namely: entries(), keys() and values().
The keys() method, as the name implies, returns an iterator that yields the keys associated with each entry of the Map object (in insertion order), where as the values() method returns an iterator that yields the values associated with each entry of the Map object.
The following code snippet demonstrates a couple of ways we can leverage the iterable behavior of a Map object to access the values or keys of each element in it.
const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);
// Using the spread operator (...) to pass values
// in the `Map` object as function arguments.
console.log(...M.values()); // 3 3 2 2
// Using the spread operator in building an array
// with the unique keys of the `Map` object.
const arr = [...M.keys()];
console.log(arr); // [1, 3, 4, 2]
console.log(arr[0]); // 1
console.log(arr[3]); // 2
console.log(arr.length); // 4
// Using destructuring assignment with a `Map` object
// to extract the first, second and remaining keys.
const [first, second, ...remainingKeys] = M.keys();
console.log(first); // 1
console.log(second); // 3
console.log(remainingKeys); // [4, 2]
console.log(remainingKeys.length); // 2
// Iteration using a `for...of` loop
// to read all the keys in the collection.
for (const key of M.keys()) {
console.log(key);
}
// 1
// 3
// 4
// 2We've been able to explore quite a number of ways in which we could iterate over a Map object. However, there remains one more very useful iteration method — the forEach() method. Just as with arrays, the forEach() method of a Map object accepts a callback function as its first argument, which is triggered for each entry of the Map object. The forEach() method also accepts an optional second argument, which represents the this value that will be used when executing the callback function.
The forEach() callback function is called with three arguments for every entry of the Map object. The first argument is the value associated with the the current entry in the iteration, the second argument is the key associated with the current entry in the iteration, and the third argument is the Map object itself.
const M = new Map([[1, 4], [3, 5], [4, 0], [2, 2]]);
M.forEach(function _callback(value, key, map) {
console.log([...map]);
const replacement = this[value];
if (replacement) map.set(key, replacement);
else if (Number.isInteger(value)) map.delete(key);
}, "hello");
console.log([...M]);
// [[1, 4], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [4, 0], [2, 2]]
// [[1, "o"], [4, "h"], [2, 2]]
// [[1, "o"], [4, "h"], [2, "l"]]Just in case you are not so sure, the forEach() method call in the previous code snippet results in the following _callback() calls:
_callback.call("hello", 1, 4, M);
_callback.call("hello", 3, 5, M);
_callback.call("hello", 4, 0, M);
_callback.call("hello", 2, 2, M);A
Setobject is an ordered collection of unique JavaScript values.
It therefore follows that for every Set object, there exists the following invariants:
- It is an ordered collection. The insertion order of its elements matters, and is followed when iterating the collection.
- Values in the collection are distinct or unique. Hence every value may occur only once in the collection with respect to the ECMAScript SameValueZero comparison algorithm.
Any valid JavaScript value can be contained in the collection — both primitive values and object references, including unseemly values like NaN and undefined.
Since we've already explored Map objects in the previous section, it makes sense to see how they compare with Set objects.
-
A
Setobject is a one-dimensional collection — because it stores only unique values, whereas aMapobject is a two-dimensional collection — because it stores records as key/value pairs (each key being unique in the collection). -
A
Setobject can be likened to aMapobject for whichkeyandvalueboth point to the same value or reference for every entry. In other words, an entry of aSetobject is represented as a two-element array whose first and second elements are the same value or point to the same object reference. This can be observed from the values produced by theentries()method of aSetobject. -
The default iterator (
[Symbol.iterator]) of aSetobject is the one returned from itsvalues()method, whereas that of aMapobject is obtained from theentries()method. -
Unlike as with
Mapobjects, theset()andget()methods are not defined in theSet.prototypeobject. Instead, theSet.prototypeobject defines anadd()method.
As we progress in our exploration of JavaScript Set objects, we will find out more ways in which they differ from Map objects.
Just as with Map objects, the only way to create a Set object is by invoking the global Set constructor function. The constructor function must be invoked with the new keyword — otherwise, a TypeError will be thrown. When the Set constructor function is invoked without arguments, an empty Set object of 0 size is returned.
// Throws a `TypeError` — when invoked without `new` keyword
const throwTypeErrorSet = Set();
// Creates an empty `Set` object of 0 `size`
const setA = new Set();
// Omitting the parentheses — when invoked without arguments
// Also creates an empty `Set` object of 0 `size`
const setB = new Set;
console.log(setA.size); // 0
console.log(setB.size); // 0The Set constructor function can also be invoked with an optional iterable argument. When specified, iterable must be a JavaScript object that properly implements the iterable protocol. Many built-in JavaScript objects implement this protocol — such as Array, String, Map and even Set — hence, these are all valid objects that can be passed to the Set constructor function as the iterable argument.
If iterable is the value null or undefined, then the effect is the same as calling the Set constructor function without any argument — hence, an empty Set object of 0 size will be created. Otherwise, a TypeError will be thrown for any other iterable value that does not properly implement the iterable protocol.
Unlike with Map objects, creating a new Set object from another iterable object has the effect of deduping (i.e eliminating redundant duplicate values from) the values yielded by the internal iterator of the iterable object. This is understandable, since one important attribute of a Set object is that it must contain only distinct values.
// (1) Set from String
// Set contains all the unique characters of the string
const testString = "programming";
const uniqueChars = new Set(testString);
console.log(testString.length); // 11
console.log(uniqueChars.size); // 8
console.log(...uniqueChars); // p r o g a m i n
// (2) Set from Array
// Set contains all the distinct elements of the array
const integers = [1,1,1,3,3,4,3,2,4,2];
const distinctIntegers = new Set(integers);
console.log(integers.length); // 10
console.log(distinctIntegers.size); // 4
console.log(...distinctIntegers); // 1 3 4 2
// (3) Set from Set
// New set contains all the items of the original set
// However, both sets are entirely different objects.
// Think of it as creating a clone of a set.
const setA = new Set([1,1,1,3,3,4,3,2,4,2]);
const setB = new Set(setA);
console.log(...setA); // 1 3 4 2
console.log(...setB); // 1 3 4 2
console.log(setA === setB); // false
console.log(setA.size === setB.size); // trueBased on what we've learnt so far about Set objects, we can give another shot at the Sample Problem from before — only this time, we will be creating a new Set object from the nums array, containing only distinct integers (no duplicates). We can then be able determine whether the nums array contains duplicates by comparing the size of the Set object with the length of the nums array.
Here is what the new solution looks like:
function hasDuplicates(nums) {
// Create a new set from `nums` containing only its distinct
// integers (i.e de-duplicate the `nums` array).
const distinct = new Set(nums);
// If the size of the `distinct` set matches the length of the
// `nums` array, then there are no duplicates, and vice-versa.
return distinct.size != nums.length;
}By leveraging a Set object, we have been able to come up with a solution whose running time is guaranteed to grow linearly with the size of the input array — even though it will require some additional memory for the Set object. The worst that could happen is that there is no duplicate integer in the input array — for which a portion of memory will be allocated for every element of the input array.
The size property, just as with Map objects, returns the number of values in the Set object at any instant. Again, the size property of the Set.prototype object is an accessor property and not a data property. Also, it only has a get accessor function and not a set accessor function — hence it cannot be overriden by an assignment operation.
Whenever you access the size property of a Set object, its get accessor function will be invoked — which basically counts and returns the number of elements (values) currently in the Set object.
Every Set object will originally have a has() method — which can be called to assert whether an element with a specified value is present in the Set object or not. Like with Map objects, the has() method returns a boolean value — true if the specified value is present, and false otherwise.
const uniqueChars = new Set("programming");
console.log(...uniqueChars); // p r o g a m i n
console.log(uniqueChars.has("p")); // true
console.log(uniqueChars.has("A")); // false
console.log(uniqueChars.has("a")); // true
console.log(uniqueChars.has("t")); // falseSince Set objects are one-dimensional (storing only unique values), it is impractical for them to have get() method — unlike with Map objects. Hence, the Set.prototype object does not define a get() method.
Being able to add or remove one or more values from a Set object is very important, hence every Set object will originally have add(), delete() and clear() methods. Notice that there is no set() method for Set objects — like exists for Map objects.
The add() method takes a JavaScript value as its argument, and will append that value to the end of the Set object — provided it isn't already in the Set object. If the specified value is already in the Set object, it is ignored. The add() method returns the same Set object (with the added value), making it amenable to method chaining (invoking multiple add() calls at once).
Just like with Map objects, the delete() method of a Set object will remove the element associated with the specified value from the Set object — provided such an element is present in the Set object. If an element is actually removed from the Set object as a result of this delete operation, it returns true, otherwise it returns false. Also, a call to the clear() method empties the Set object and returns undefined.
// Create new set of integers
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);
console.log(integers.size); // 4
console.log(...integers); // 1 3 4 2
// Add some values to the set
integers.add(5);
integers.add(1);
console.log(integers.size); // 5
console.log(...integers); // 1 3 4 2 5
// Add several values at once (using chaining)
integers.add(7).add(2).add(9);
console.log(integers.size); // 7
console.log(...integers); // 1 3 4 2 5 7 9
// Delete some values from the set
console.log(integers.delete(3)); // true
console.log(integers.delete(8)); // false
console.log(integers.delete(3)); // false
console.log(integers.delete(1)); // true
console.log(integers.size); // 5
console.log(...integers); // 4 2 5 7 9
// Empty the set
integers.clear();
console.log(integers.size); // 0Now that we've learnt a few things we can do with Set objects, let's come back to our previous solution to the Sample Problem — to see if there is any way we can optimize it even further. As you might have rightly guessed, it can be optimized further.
A careful examination of our previous solution will show that it's doing a little too much. It always considers all the integers in the input array — adding them to the Set object (just like using the add() method multiple times) and then checking the size of the Set object (which counts and returns the number of elements in the Set object by going through each element).
The problem with this solution is that it isn't conservative. It is very possible that a duplicate integer might found from just considering the first few integers in the array — hence, considering the remaining integers in the array becomes redundant. To optimize this solution, we can decide to be lazy about adding integers to the Set object, and only continue as long as we haven't encountered an integer that has already been added to the Set object.
Here is what the optimized solution looks like:
function hasDuplicates(nums) {
// 1. Create an empty set to hold distinct integers
const distinct = new Set();
// 2. Loop through the integers until a duplicate is found
for (const int of nums) {
// 2a. If a duplicate is found, return immediately
if (distinct.has(int)) return true;
// 2b. Otherwise, add the integer to the distinct set
distinct.add(int);
}
// 3. If it ever gets here, no duplicate was found
return false;
}It is often necessary to have a view into the values that are contained in a Set object. This is very attainable with arrays (indexed collections) — hence, we can easily access the element of an array arr, at some index i, using the property access bracket notation arr[i]. Unfortunately, this kind of element access is not directly possible with Set objects (keyed collections).
However, just like with arrays and other iterables, you can loop through the values for each element in a Set object (in insertion order) using the for...of loop, or you could use the sequence of values it produces with the spread operator (...), the yield* statement, or destructuring assignment.
The following code snippet demonstrates a couple of ways we can leverage the iterable behavior of a Set object to access the values of each element in it.
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);
// Using the spread operator (...) to pass values
// in the `Set` object as function arguments.
console.log(...integers); // 1 3 4 2
// Using the spread operator in building an array
// with the unique values from the `Set` object.
const arr = [...integers];
console.log(arr); // [1, 3, 4, 2]
console.log(arr[0]); // 1
console.log(arr[3]); // 2
console.log(arr.length); // 4
// Using destructuring assignment with a `Set` object
const [first, second, ...remainingIntegers] = integers;
console.log(first); // 1
console.log(second); // 3
console.log(remainingIntegers); // [4, 2]
console.log(remainingIntegers.length); // 2
// Iteration using a `for...of` loop
for (const integer of integers) {
console.log(integer);
}
// 1
// 3
// 4
// 2Just like with Map objects, every Set object originally has three methods that return iterators, namely — values(), keys() and entries().
The values() method, as the name implies, returns a new iterator that yields the values for each element in the Set object (in insertion order). The iterator returned by the values() method yields the exact same sequence of values as the default iterator returned by the [Symbol.iterator] method.
For iteration purposes, the keys() method of a Set object behaves exactly like the values() method, and can be used interchangeably. In fact, the values, keys and [Symbol.iterator] properties of a Set object all point to the same value (function) initially. Hence, the following for...of loops will log the exact same sequence of values.
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);
// (a) Iteration using the default iterator (`[Symbol.iterator]`)
for (const integer of integers) {
console.log(integer);
}
// (b) Iteration using the `values()` iterator
for (const integer of integers.values()) {
console.log(integer);
}
// (c) Iteration using the `keys()` iterator
for (const integer of integers.keys()) {
console.log(integer);
}Some basic set operations can be implemented by iterating over one or more Set objects. For example, the following code snippet shows how to implement the union and intersection set operations.
function union(setA, setB) {
const setUnion = new Set(setA);
for (const value of setB) {
setUnion.add(value);
}
return setUnion;
}
function intersection(setA, setB) {
const setIntersection = new Set();
for (const value of setB) {
if (setA.has(value)) {
setIntersection.add(value);
}
}
return setIntersection;
}Just as with Map objects, Set objects also have a forEach() method with a similar call signature. However, accounting for the one-dimensional nature of Set objects, the forEach() callback function is called with three arguments like so: the first argument is the value for the current element in the iteration, the second argument is always the same as the first argument, and the third argument is the Set object itself.
const S = new Set([1,1,1,3,3,4,3,2,4,2]);
S.forEach(function _callback(value, _, set) {
console.log([...set]);
const replacement = this[value];
if (replacement) set.add(`${value}${replacement}`);
if (Number.isInteger(value)) set.delete(value);
}, "hello");
// [1, 3, 4, 2]
// [3, 4, 2, '1e']
// [4, 2, '1e', '3l']
// [2, '1e', '3l', '4o']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
console.log(...S); // 1e 3l 4o 2lJust in case you are not so sure, the forEach() method call in the previous code snippet results in the following _callback() calls:
_callback.call("hello", 1, 1, S);
_callback.call("hello", 3, 3, S);
_callback.call("hello", 4, 4, S);
_callback.call("hello", 2, 2, S);
_callback.call("hello", '1e', '1e', S);
_callback.call("hello", '3l', '3l', S);
_callback.call("hello", '4o', '4o', S);
_callback.call("hello", '2l', '2l', S);When the Set constructor function is called without any argument, you already know that it creates an empty Set object (with no elements). The same however does not hold true for the add() method.
When the add() method of a Set object is called without any argument, it actually adds an element to the collection with a value of undefined (if it does not already exist). In other words for a given Set object S, S.add() is exactly the same as S.add(undefined). This is what I'd like to refer to as accidental undefined — because it might not be intended.
You might have already inferred the behaviour of the has() and delete() methods when called without any argument. As with the add() method, calling these methods without any argument is exactly the same as calling them with undefined as first argument. Hence for a given Set object S, S.has() checks whether undefined exists as a value in the Set object, while S.delete() removes the value undefined from the collection (if it exists).
// Creates an empty set object
const S = new Set();
// Add some items to the set object
S.add(5);
S.add("hello");
console.log(...S); // 5 'hello'
// Adds `undefined` to the set object
S.add();
console.log(...S); // 5 'hello' undefined
console.log(S.has(5)); // true
console.log(S.has("world")); // false
// Logs `true` because `undefined` exists in the set
console.log(S.has()); // true
// Logs `true` because `undefined` was removed from the set
console.log(S.delete()); // true
// Logs `false` because `undefined` does not exist in the set
console.log(S.has()); // falseThat said, always be sure to explicitly call the add(), delete() and has() methods of a Set object with at least one argument to avoid dealing with an accidental undefined value.
Before we finish this section on JavaScript Set objects, let's see how we can solve a modified version of the Sample Problem from before — using all we've learnt so far.
Contains Duplicates (2) Given an array of integers
nums, return the number of elements that appear at least twice in the array, and return0if every element is distinct.
Pause for a moment and try solving this problem on your own, before you proceed. The solution could be a little tricky — how would you ensure a duplicate integer is not counted more than once?
Now, here is a working solution to the problem:
function countDuplicates(nums) {
// Create an empty set for distinct integers
// (i.e integers appearing only once)
const distinct = new Set();
// Create an empty set for duplicate integers
const duplicates = new Set();
// Create a variable to keep track of the duplicates count
let count = 0;
// Loop through the integers while counting duplicates
for (const int of nums) {
// If duplicate integer is found (it has already been counted),
// continue with the iteration to the next integer.
if (duplicates.has(int)) continue;
if (distinct.delete(int)) {
// If integer was successfully deleted from the `distinct` set,
// that means it has been seen once before. Hence add it, to
// the `duplicates` set and increment `count`.
duplicates.add(int);
count++;
} else {
// Integer is being seen for the first time and should be added
// to the `distinct` set.
distinct.add(int);
}
}
// Finally, return the duplicates count
return count;
}