Tome I.II JavaScriptmancy and Data Structures
JavaScript Arrays: The All-in-one Data Structure
Remember,
Grasp the subject,
and the words will follow.
Have the argument clear in your mind,
and the words will flow naturally.
Focus on the data structures first,
and your code will be cleaner.
- Svotarld Siunl
Sage
We’ll Just Need To Make Sense of All These Items
For a very long time (up until the year 2015 and the advent of ES6) the only data structure available in JavaScript was the array. This was not a big problem for the hordes of JavaScript developers because JavaScript’s array is an array, a list, a queue, a stack and, in addition, provides similar functionality to LINQ. Sounds interesting? Let’s have a look.
JavaScript’s Array
The easiest way to create an array in JavaScript is to use the array literal:
1 var rightPocket = [];
2 console.log('This is what I have in my right pocket: ' +
3 rightPocket);
4 // => This is what I have in my right pocket:
Although you can use the Array constructor as well:
1 var leftPocket = Array();
2 console.log('And this is what I have in my left pocket: ' +
3 leftPocket);
4 // => And this is what I have in my left pocket:
Which unfortunately is a little bit inconsistent. For instance, you can use the Array constructor with one single argument to create an array of an arbitrary size:
1 console.log(Array(1));
2 // => [undefined]
3 console.log(Array(3));
4 // => [undefined, undefined, undefined]
Or you can use it with more than one argument to create an array that will contain the arguments that you pass in (just like []):
1 console.log(Array(1, 2, 3));
2 // => [1, 2, 3]
As you would expect from any array worth its salt, you can set items in the array by index:
1 rightPocket[0] = 'bearded axe';
2 leftPocket[0] = '10 gold coins';
3
4 console.log('right pocket: ' + rightPocket);
5 // => right pocket: bearded axe
6 console.log('left pocket: ' + leftPocket);
7 // => left pocket: 10 gold coins
And you can also retrieve these items by indexing the array:
1 console.log('I have a ' + rightPocket[0] + 'in my right pocket. ' +
2 'I am maniac... and I have to patent this pants...');
3 // => I have a bearded axe in my right pocket.
4 // I am maniac... and I have to patent this pants...
Arrays have a dynamic size and they grow as you add new elements to them. You can access the size of an array using its length property:
1 console.log('The size of my right pocket is: ' + rightPocket.length);
2 // => The size of my right pocket is: 1
3 rightPocket[1] = "orb of power";
4 console.log('And now it is: ' + rightPocket,length);
5 // => And now it is 2
Specially interesting is the fact that JavaScript allows you to have elements of disparate types within the same array:
1 var leatherBag = ['20 gold coins',
2 {name: 'wand of invisibility',
3 charges: 1,
4 toString(){return this.name;}}];
5 console.log('You examine your leather bag and find: ' + leatherBag);
6 // => You examine your leather bag and find: 20 gold coins,wand of i\
7 nvisibility
An Extremely Flexible Data Structure
The Array was the sole data structure available in JavaScript for a long time and, as such, it grew to provide a lot of functionality to cover most of the use cases that you usually run into when writing JavaScript applications. It is somewhat of an all-purpose collection.
For instance, it can work as a stack (LIFO - Last In First Out) if you use the methods push and pop. These methods add and remove elements from the end of the array respectively:
1 rightPocket.push('chewing gum');
2 console.log('You get the ' + right.Pocket.pop());
3 // => You get the chewing gum
It can work as a queue (FIFO - First In First Out) if you use the method shift to extract an item from the beginning of the array and combine it with push:
1 leftPocket.push('cheese sandwich');
2 console.log('You pay the cheese sandwich with ' +
3 leftPocket.shift() + '. That was a pricy sandwich...');
4 // => You pay the cheese sandwich with 10 gold coins.
5 // That was a pricy sandwich...
You can also insert items in the beginning of the array by using the unshift method:
1 leftPocket.unshift('beautiful stone');
2 console.log('You examine the ' + leftPocket[0] + ' in wonder.');
3 // => You examine the beautiful stone in wonder.
Additionally, both push and unshift let you add multiple items at once:
1 leatherBag.push('dried meat', 'white feather');
2 leatherBag.unshift('1 copper coin', 'skeleton skull');
3 console.log('You look inside your leather bag and find: ' +
4 leatherBag);
5 // => You look inside your leather bag and find:
6 // 1 copper coin,skeleton skull,20 gold coins,
7 // wand of invisibility,dried meat,white feather
Another useful method that lets you remove items from any arbitrary position of an array is the splice method. It has many use cases:
1 var firstItem = leatherBag.splice(/* start */ 0,
2 /* numberOfItemsToRemove */ 1);
3 console.log('extracted first item => ' + firstItem);
4 // => extracted first item => 1 copper coin
5
6 // you can use negative indexes to start from the end of the array
7 var lastItem = leatherBag.splice(-1, 1);
8 console.log('extracted last item => ' + lastItem);
9 // => extracted last item => white feather
10
11 var someRandomItemsInTheMiddle = leatherBag.splice(1, 2);
12 console.log('extracted items in the middle => ' +
13 someRandomItemsInTheMiddle);
14 // => extracted items in the middle => 20 gold coins,
15 // wand of invisibility
splice can even insert items at a given point:
1 console.log(rightPocket);
2 // => ["bearded axe", "orb of power"]
3
4 // let's add a couple of items in between the axe and the orb
5 // splice(startIndex, numberOfItemsToRemove, item1, item2, etc...)
6 rightPocket.splice(1, 0, "candlestick", "yerky");
7 console.log(rightPocket);
8 // => ["bearded axe", "candlestick", "yerky", "orb of power"]
or remove items and insert items at once:
1 // splice(startIndex, numberOfItemsToRemove, item1, item2, etc...)
2 let candle = rightPocket.splice(1, 1, "secret message", "wax");
3 console.log(rightPocket);
4 // => ["bearded axe", "secret message", "wax", "yerky",
5 // "orb of power"]
Sorting Arrays
Arrays offer a couple of methods that let you sort the elements they contain. The first one that you need to consider is the sort method which takes a comparing function as argument. Let’s sort our potions:
1 function Potion(name, quantity){
2 return {
3 name,
4 quantity,
5 toString(){return `(${this.quantity}) ${this.name}`;}
6 };
7 }
8
9 var potionsCase = [
10 Potion('potion of firebreathing', 2),
11 Potion('potion of vigor', 1),
12 Potion('potion of major healing', 3),
13 Potion('potion of cure poison', 1)
14 ];
15 // the compare function f(a,b) should return:
16 // < 0 if a < b
17 // 0 if a === b
18 // > 0 if a > b
19 potionsCase.sort((p1,p2) => p1.quantity - p2.quantity);
20 console.log("You examine your potion case closely... " +
21 potionsCase);
22 // => You examine your potion case closely...
23 // (1) potion of cure poison,
24 // (1) potion of vigor,
25 // (2) potion of firebreathing
26 // (3) potion of major healing,
And it looks like you need to buy some more of that curing poison because you never know what may be waiting to bite you behind that next corner. The comparing function compare(a,b) is expected to return:
-
0whenaandbare considered equal -
< 0whena < b -
> 0whena > b
Another fact that is important to remember is that the sort method does in-place sorting so your original array will reflect the changes after being sorted.
The second array method related to sorting is the reverse method. This method reverses the position of all items within the array and does so in-place:
1 console.log("Let's see what I can sell... " +
2 potionsCase.reverse());
3 // => Let's' see what I can sell...
4 // (3) potion of major healing,
5 // (2) potion of firebreathing,
6 // (1) potion of cure poison,
7 // (1) potion of vigor
Safe Array Methods
All these methods that we have seen up until now mutate the array itself. This means that using them will change the inner contents of the array where the method is called. Let’s look at some safe methods now, methods that don’t change the original array.
The concat method lets you concatenate two arrays together and returns the resulting array:
1 // concatenate arrays with concat
2 var superPocket = rightPocket.concat(leftPocket);
3 console.log(superPocket);
4 // => ["bearded axe", "secret message", "wax", "yerky",
5 // "orb of power", "beautiful stone", "cheese sandwich"]
The join method allows you to join the elements of an array to form a string using an arbitrary separator of your choice:
1 function beautifyPocket(pocket){
2 return pocket.join('\n=============\n');
3 }
4 console.log(`You examine your inventory: \n
5 ${beautifyPocket(rightPocket)}`);
6 // => You examine your inventory:
7 //
8 // bearded axe
9 // =============
10 // secret message
11 // =============
12 // wax
13 // =============
14 // yerky
15 // =============
16 // orb of power
The indexOf method returns the position of an item within an array:
1 var indexOfBeardedAxe = rightPocket.indexOf('bearded axe');
2 console.log('The bearded axe is at position: ' + indexOfBeardedAxe);
It is often used to find out whether or not an array contains a given item like this:
1 // indexOf returns -1 when it can't find an item
2 if (rightPocket.indexOf('red stone') === -1)
3 {
4 console.log("You don't have a precious red stone in your pocket");
5 }
indexOf returns the first ocurrence of an item in an array, alternatively you can use lastIndexOf to find the last ocurrence of an item.
The last safe array method is slice which is a non-destructive alternative to splice. This being JavaScript we couldn’t have a similar signature. Instead of working with the start index and the number of items to remove, the slice method expects the start and end of the subarray to extract:
1 console.log('leather bag has ' + leatherBag.length + ' items: ' +
2 leatherBag);
3 // => leather bag has 2 items: skeleton skull,dried meat
4
5 // let's be god and reproduce the dried meat
6 console.log(leatherBag.slice(/* start */ 1, /* end */ 3));
7 // => ['dried meat']
8 // Note how slice extracts up to but not including the end
9
10 // we still have two items in the original array
11 console.log('leather bag has ' + leatherBag.length + ' items: ' +
12 leatherBag);
13 // => leather bag has 2 items: skeleton skull,dried meat
slice also supports negative indices which represent starting counting from the end of the array. The end parameters is also optional, so we can extract a new array containing only the last item from the original array pretty easily:
1 var lastItem = leatherBag.slice(-1);
2 console.log(lastItem);
3 // => ["dried meat"]
Iterating an array
Prior to ES6, JavaScript offered two ways in which to iterate over the elements of an array: the for/in loop and the Array.prototype.forEach method.
The for/in loop is a JavaScript construct that lets you iterate over the properties1 of any object. In the case of an array, these properties are the indices of the array:
1 console.log('You examine your inventory: ');
2 for(var index in leatherBag){
3 console.log(leatherBag[index]);
4 }
5 // => You examine your inventory:
6 // skeleton skull"
7 // dried meat"
The forEach method offers a better developer experience to iterating as it gives you each item of the array directly:
1 console.log('You examine your inventory.... closer: ')
2 leatherBag.forEach(function(item) {
3 console.log('You examine ' + item + ' closely');
4 });
5 // => You examine your inventory.... closer:
6 // You examine skeleton skull closely
7 // You examine dried meat closely
And, additionally, it gives you access to each index and the array itself:
1 console.log('You examine your inventory.... veeery closely: ')
2 leatherBag.forEach(function(item, index, array) {
3 console.log('You examine ' + item + ' closely (' +
4 (index+1) + '/' + array.length + ')');
5 });
6 // => You examine your inventory.... veeery closely:
7 // You examine skeleton skull closely (1/2)
8 // You examine dried meat closely (2/2)
ES6 generalizes the concept of iterability in JavaScript through the addition of the iterator protocol and the for/of loop:
1 console.log('You look at the stuff in your bag:');
2 for(let item of leatherBag){
3 console.log(item);
4 }
5 // => You look at the stuff in your bag:
6 // skeleton skull
7 // dried meat
JavaScript Arrays and LINQ
If you thought that everything you’ve seen thus far was everything there was about JavaScript arrays you’re in for a treat, because Wait! There is more!.
One of my favorites features of the JavaScript array is that it comes with a set of methods that are very similar to .NET LINQ. Yes, you read it. Isn’t that absolutely awesome? I devote a whole chapter to the Array’s LINQ-like methods in the functional programming tome of this series, but here’s a small appetizer.
1 var shop = [
2 {name: 'sword of truth', type: 'sword', damage: 60, price: 1000},
3 {name: 'shield of stamina', type: 'shield', defense: 50,
4 price: 500, modifiers: [{value: 2, characteristic: 'stamina'}]},
5 {name: 'minor potion of healing', type: 'potion', price: 1,
6 effects: [{value: 10, characteristic: 'hitPoints'}]},
7 {name: 'grand potion of healing', type: 'potion', price: 7,
8 effects: [{value: 50, characteristic: 'hitPoints'}]}
9 ];
10
11 console.log('The shopkeeper looks at you greedily and tells you:');
12 console.log('*These are the potions we have today sir...' +
13 'they are the best in the kingdowm!*');
14 var potions = shop
15 .filter(item => item.type === 'potion')
16 .map(potion => potion.name);
17 for(let potion of potions){
18 console.log(potion);
19 }
20 // => The shopkeeper looks at you greedily and tells you:
21 // *These are the potions we have today sir...
22 // they are the best in the kingdowm!*
23 // minor potion of healing
24 // grand potion of healing
I used arrow functions in this example to give you a feeling of familiarity between the Array.prototype LINQ-like methods and LINQ, but you must know that most of these methods are available in ES5 and work just as well with normal function expressions.
1 var totalPrice = shop
2 .map(function(item){return item.price;})
3 .reduce(function(total, itemPrice){
4 return total + itemPrice;
5 }, /* initialTotal */ 0);
6 console.log('The total price of the items is ' + totalPrice +
7 ' silvers');
8 // => The total price of the items is 1508 silvers
Other ES6 and ES7 Features
In addition to formalizing the concept of iteration in Arrays, ES6 brings several new helpful methods that will make operating on Arrays and Array-likes easier.
The Array.from method let’s you create an array from any array-like and iterable object. It is ES6’s solution to the commonplace practice of using Array.prototype.slice in ES5 to convert array-likes into proper arrays:
1 // (in this case it'd better to use the rest syntax ...items)
2 function sortItems(){
3 var items = Array.from(arguments);
4 return items.sort();
5 }
6 console.log(sortItems('mandragora', 'amber', "elf's tongue"));
7 // => ["amber", "elf's tongue", "mandragora"]
Any object that can be iterated over can be converted into an array using Array.from. For instance, a Map:
1 var library = new Map();
2 library.set('horror', ['It', 'The thing', 'horrors of Swarland']);
3 library.set('love', ['Romance and Betrayal', 'Beauty I']);
4 library.set('history', ['The fall of the Kraagg Empire']);
5
6 console.log('Welcome to the library of Anriva!' +
7 ' These are our most valuable books');
8 Array.from(library)
9 .forEach(keyValuePair => {
10 console.log(keyValuePair);
11 });
12 // => ["horror", ["It", "The thing", "horrors of Swarland"]]
13 // ["love", ["Romance and Betrayal", "Beauty I"]]
14 // ["history", ["The fall of the Kraagg Empire"]]
Array.from also takes a second optional argument, a map function that just like LINQ’s Select let’s you transform each element within the source array into something else of your own choosing:
1 function sortItemsProperty(selector, ...args){
2 var items = Array.from(args, selector);
3 return items.sort();
4 }
5
6 console.log(sortItemsProperty(i => i.price,
7 {name: 'mandragora', price: 2},
8 {name: 'amber', price: 10}));
9 // => [10, 2]
The Array.isArray method provides a more convenient and safer 2 way to check whether an object is an array or not. Prior to ES6 we used to use the following approach:
1 console.log('Shop is an array: ' + (shop instanceof Array));
With Array.isArray it’s more straightforward:
1 console.log('Shop is an array: ' + Array.isArray(shop));
The Array.of method lets you create an array from a variable number of arguments and is equivalent to []:
1 let ingredients = Array.of('bat wings', 'unicorn horn',
2 'sesame seeds');
3 // => ['bat wings', 'unicorn horn', 'sesame seeds']
Why would you want to use Array.of instead of [] then? There is a corner case application where Array.of is essential, when creating Array subclasses:
1 class ItemsArray extends Array{
2 price(){
3 return this.map(i => i.price).reduce((a, p) => a + p, 0);
4 }
5 }
6 // how can you instantiate an array of ItemsArray in a consistent way
7 let itemsArray = ItemsArray.of(
8 {name: 'bat wings', price: 10},
9 {name: 'unicorn horn', price: 10000},
10 {name: 'sesame seeds', price: 1}
11 )
12 console.log(`the price of all your wares is ` +
13 `${itemsArray.price()} golden coins`);
14 // => the price of all your wares is 10011 golden coins
Array.prototype.copyWithin() provides a way to copy items within the same array, that is, pick a portion of an array and copy it within the same array. Let’s illustrate it with an example:
1 [1, 2, 3, 4, 5].copyWithin(/* target index */ 0,
2 /* start */ 3, /* end */ 4);
3 // copies the items between indexes 3 and 4 => the item 4
4 // into the index 0 of the array
5 // [4, 1, 3, 4, 5]
6
7 // if you leave the end out, it defaults to the length of the array
8 [1, 2, 3, 4, 5].copyWithin(/* target index */ 0, /* start */ 3);
9 // [4, 5, 3, 4, 5]
Array.prototype.fill() provides a convenient way to fill an existing array with a specific item:
1 // [].fill(item, start=0, end=this.length)
2 [1, 2, 3].fill(':)'); // [':)', ':)', ':)']
3 [1, 2, 3].fill(':)', 1); // [1, ':)', ':)']
4 [1, 2, 3].fill(':)', 1, 2); // [1, ':)', 3]
New Array methods in ES7
ES7, while being a very small incremental release of JavaScript, brings a very convenient way to check whether an item exists within an array, the Array.prototype.includes() method:
1 if (!rightPocket.includes('red stone'))
2 {
3 console.log("You don't have a precious red stone in your pocket");
4 }
This provides a much better developer experience than the indexOf method that we saw previously in this chapter:
1 // indexOf returns -1 when it can't find an item
2 if (rightPocket.indexOf('red stone') === -1)
3 {
4 console.log("You don't have a precious red stone in your pocket");
5 }
In addition to providing which item within the array you are looking for, you can specify an starting index for the search:
1 let herbs = ['sage', 'salvia', 'aloe vera'];
2 console.log('Is sage the last item in my herb poach?:',
3 herbs.includes('sage', herbs.length);
4 // => is sage the last item in my herb poach? : false
Array Cheatsheet
| Basics | description |
|---|---|
[] |
Create an empty array |
[1, 2, 3] |
Create an array |
Array(n) |
Create array with n undefined elements |
Array(1, 2, 3) |
Equivalent to [1, 2, 3]
|
Array Unsafe Methods ES5
| method name | superpower |
|---|---|
Array.prototype.push(n1, n2...) |
Append item to the end of an array |
- [].push(1)
|
|
- [].push(1, 2, 3)
|
|
Array.prototype.pop() |
Remove item from the end of an array |
- let n = [1].pop()
|
|
Array.prototype.shift() |
Remove item from the beginning of an array |
- let n = [1].shift()
|
|
Array.prototype.unshift(n1, n2...) |
Insert item to the beginning of an array |
- [].unshift(1)
|
|
- [].unshift(1, 2, 3)
|
|
Array.prototype.splice(start, length, n1, n2) |
Remove items from any arbitrary position and insert new ones |
- [1,2].splice(0, 1)
|
- remove first item |
- [1,2].splice(-1, 1)
|
- remove last item |
- [1,2,3,4].splice(1,2)
|
- remove two items in the middle |
- [1,2].splice(0, 1, 'ash')
|
- change first item for 'ash'
|
- [1,2,3,4].splice(1,2, 'ash', 'gold')
|
- change two middle items from 'ash' and 'gold'
|
Array.prototype.sort(compareFn) |
Sort array |
- [1,2,3].sort()
|
- sort according to character UNICODE code point value |
- [1,2,3].sort((a,b) => a-b)
|
- sort numbers |
| - a > b ⇒ return > 0 | |
| - a < b ⇒ return < 0 | |
| - a === b ⇒ return 0 | |
Array.prototype.reverse() |
Reverse order of items within an array |
- [1,2,3].reverse()
|
Array Safe Methods ES5
| method name | superpower |
|---|---|
Array.prototype.concat(arr) |
Concatenates two arrays |
- [1,2,3].concat([5,6])
|
|
Array.prototype.join(separator) |
Join items of the array using a separator
|
- [1,2,3].join(', ')
|
- "1, 2, 3"
|
Array.prototype.indexOf(n) |
Returns index of the first ocurrence of an item within an array |
- [1,2,3].indexOf(1)
|
|
- [1,2,3].indexOf(55)
|
- returns -1 if the item is not in the array |
Array.prototype.lastIndexOf(n) |
Returns index of the last ocurrence of an item within an array |
- [1,1,1].lastIndexOf(1)
|
|
- [1,1,1].lastIndexOf(22)
|
- returns -1 if the item is not in the array |
Array.prototype.slice(start, end) |
Returns subarray between start and end indexes. end indexed item is not included. |
- [1,2,3].slice(1,2)
|
- returns [2]
|
- [1,2,3].slice(1)
|
- returns [2, 3]
|
- [1,2,3].slice(-1)
|
- returns [3]
|
Iterating Arrays
| method | superpower |
|---|---|
for/in loop |
Loops over the indexes of an array |
- for(var i in arr)
|
|
for/of loop |
Loops over the items of an array |
- for(let i of arr)
|
|
Array.prototype.forEach |
Loops over the items of an array |
- arr.forEach(doSomething)
|
Array LINQ-like Methods
- See to Chapter LINQ chapter in the Functional Programming Tome of the Series.
New Array Methods in ES6
| method name | superpower |
|---|---|
Array.from |
Convert any iterable in an array. Also works on array-likes. |
- Array.from(arguments)
|
|
Array.isArray(obj) |
Check whether an object is an array. |
- Array.isArray([1,2,3])
|
|
Array.prototype.of() |
Instantiate a new array. Useful when subclassing Array
|
- MyArray.of(1,2,3)
|
|
Array.prototype.copyWithin(target, start, end) |
Copy array subset in place, that is, within the same array. |
- [1,2,3].copyWithin(0, 1, 2)
|
- [2,2,3]
|
Array.prototype.fill(item, start, end) |
Fill array with items |
- [1,2,3].fill(1)
|
-[1,1,1]
|
- [1,2,3].fill(1,2)
|
-[1,2,1]
|
- [1,2,3].fill(1,1,2)
|
-[1,1,3]
|
ES7
| method name | superpower |
|---|---|
Array.prototype.includes(item, start) |
Check whether an array contains an item
|
- [1,1,1].includes(2)
|
Concluding
JavaScript’s array is an all-purpose collection, a extremely and versatile data structure that will cover most of you application needs. You can use it as a stack, a queue, a list, you can easily perform destructive and non-destructive operations on it. It also has support for LINQ-like functionality that will make working with collections of items a breeze.
Even though JavaScript’s array is awesome, there’s a couple of use cases that are best suited for other data structures: storing items by an arbitrary key and managing collections of unique items. And that’s what we will learn in the next two chapters since both Maps (like a Dictionary<T,T>) and Sets are two new data structures available from ES6 onwards.
Exercises
Organizing Your Data With ES6 Maps
It is unknown who designed the first map.
But it is said that he got tired of traversing
a whole array of shoes every time he decided
to go for a walk.
- Ckor Srich
Royal Buffoon 2nd Age
Take a Look at These Maps
ES6 brings two new data structures to JavaScript, the Map and the Set. This chapter is devoted to the Map, which is fundamentally a HashTable. We often refer to it as Dictionary in C#. JavaScript’s Map provides a simple API to store objects by an arbitrary key, a very essential functionality required in many JavaScript programs.
JavaScript’s Map
You can create a Map in JavaScript using the new operator:
1 const wizardsArchive = new Map();
Once created the Map offers two fundamental methods: get and set. As you can probably guess using your wizardy intuition, you use set to add an object to the Map:
1 wizardsArchive.set( /* key */ 'jaime', /* value */ {
2 name: 'jaime',
3 title: 'The Bold',
4 race: 'ewok',
5 traits: ['joyful', 'hairless']
6 });
And get to retrieve it:
1 console.log('Wizard with key jaime => ', wizardsArchive.get('jaime')\
2 );
3 /* => Item with key jaime =>
4 [object Object] {
5 name: "jaime",
6 race: "ewok",
7 trait: ["joyful", "hairless"]
8 }
9 */
This being JavaScript you can use any type as key or value, and the same Map can hold disparate types for both keys and values. Yey! Freedom!:
1 wizardsArchive.set(42, "What is the answer to life, the universe and\
2 everything?")
3 console.log(wizardsArchive.get(42));
4 // => What is the answer to life, the universe and everything?
5
6 wizardsArchive.set('firebolt', (target) => console.log(`${target} is\7 consumed by fire`));
8 wizardsArchive.get('firebolt')('frigate');
9 // => frigate is consumed by fire
You can easily find how many elements are stored within a Map using the size property:
1 console.log(`there are ${wizardsArchive.size} thingies in the archiv\2 e`)
3 // => there are 3 thingies in the archive
Removing items from a Map is very straightforward as well, you use the delete method with the item’s key. Let’s do some cleanup and remove those nonsensical items from the last example:
1 wizardsArchive.delete(42);
2 wizardsArchive.delete('firebolt');
Now that we have removed them, we can verify that indeed they are gone using the has method:
1 console.log(`Wizards archive has info on '42': ` +
2 `${wizardsArchive.has(42)}`);
3 // => Wizards archive has info on '42': false
4 console.log(`Wizards archive has info on 'firebolt':
5 ${wizardsArchive.has('firebolt')}`);
6 // => Wizards archive has info on 'firebolt': false
And when we are done for the day and want to remove every item at once, the Map offers the clear method:
1 wizardsArchive.clear();
2 console.log(`there are ${wizardsArchive.size} wizards in the archive\3 `);
4 // => there are 0 wizards in the archive
Iterating Over the Elements of a Map
Just like with arrays you can iterate over the elements of a Map using the for/of loop:
1 // let's add some items back so we have something to iterate over...
2 // the set method is chainable by the by!
3 wizardsArchive
4 .set('jaime', {name: 'jaime', title: 'The Bold', race: 'ewok',
5 traits: ['joyful', 'hairless']})
6 .set('theRock', {name: 'theRock', race: 'giant',
7 traits: ['big shoulders']});
8
9 for(let keyValue of wizardsArchive){
10 console.log(`${keyValue[0]} : ${JSON.stringify(keyValue[1])}`);
11 }
12 /*
13 "jaime : {\"name\":\"jaime\",\"race\":\"....
14 "theRock : {\"name\":\"theRock\",\"race\....
15 */
The default Map iterator (also available via the entries property) lets you traverse a Map using key-value pairs. Each pair is an array with two items, the first being the key and the second the value. The example above is equivalent to:
1 for(let keyValue of wizardsArchive.entries()){
2 console.log(`${keyValue[0]} : ${JSON.stringify(keyValue[1])}`);
3 }
Both examples above are a little displeasing to the eye, aren’t they? You can improve them greatly if you use the destructuring syntax to extract the key and the value from the key-value array:
1 for(let [key, value] of wizardsArchive){
2 console.log(`${key} : ${JSON.stringify(value)}`);
3 }
Much nicer right? Alternatively you can use the Map.prototype.forEach method analogous to Array.prototype.forEach but with keys and values:
1 wizardsArchive.forEach((key,value) =>
2 console.log(`${key} : ${JSON.stringify(value)}`)
3 );
4 // => jaime: {\"name\" ...
5 // => theRock: {\"name\" ...
In addition to iterating over key-value pairs, you can also traverse the keys:
1 console.log(Array.from(wizardsArchive.keys()).join(', '));
2 // => jaime, theRock"
And the values:
1 console.log(Array.from(wizardsArchive.values())
2 .map(i => i.race).join(', '));
3 // => ewok, giant
Both the keys and values iterators provide a better developer experience in those cases where you just need the keys or the values.
Note that in the examples above we created an Array from the keys and the values iterators and concatenated its elements using join. This resulted in us “iterating” over the whole Map at once, but we could have just as well used a for/of loop and operated on each item separately.
Creating a Map From an Iterable Collection
In addition to creating empty Maps and filling them with information, you can create Maps from any iterable collection. For instance, let’s say that you have an array of wizards:
1 let jaimeTheWizard = {name: 'jaime', title: 'The Bold',
2 race: 'ewok', traits: ['joyful', 'hairless']};
3 let theRock = {name: 'theRock', title: 'The Mighty',
4 race: 'giant', trait: ['big shoulders']};
5 let randalfTheRed = {name: 'randalf', title: 'The Red',
6 race: 'human', traits: ['pyromaniac']};
7
8 let wizards = [jaimeTheWizard, theRock, randalfTheRed];
And you want to group them by race and put them on a dictionary where you can easily find them. You can do that by passing a suitably shaped collection into the Map constructor:
1 var wizardsByRace = new Map(wizards
2 .map(w => [/*key*/ w.race, /*value*/ w]));
3
4 console.log(Array.from(wizardsByRace.keys()));
5 // => ["ewok", "giant", "human"]
6 console.log(wizardsByRace.get("human").name);
7 // => randalf
The Map constructor expects to find an iterator that goes through key-value pairs represented as an array where the first element is the key and the second element is the value:
1 [[key1, value1], [key2, value2], ...]
In the example above we used map over the wizards array to transform each element of the original array into a new one that represents key-value pairs, which are the race of the wizard and the wizard itself.
1 [["ewok", jaimeTheWizard], ["giant", theRock],
2 ["human", randalfTheRed]]
We could create a helper method toKeyValue to make this transformation easier:
1 function* toKeyValue(arr, keySelector){
2 for(let item of arr)
3 yield [keySelector(item), item];
4 }
The toKeyValue function above is a generator, a special function that helps you build iterators. You’ll learn more about generators later in this tome on data structures. For the time being, you just need to understand that we are transforming each element of an array into a key value pair.
When we call the generator we effectively transform the array into an iterator of key value pairs:
1 var keyValues = toKeyValue(wizards, w => w.name)
We can pass this new iterator to the to the Map constructor and obtain the desired Map of wizards:
1 var keyValues = toKeyValue(wizards, w => w.name);
2 var wizardsByName = new Map(keyValues);
3
4 console.log(Array.from(wizardsByName.keys()));
5 // => ["jaime", "theRock", "randalf"]
We still need to perform the transformation in two separate steps which is not very developer friendly. We can improve this by extending the Array.prototype with a toKeyValue method:
1 Array.prototype.toKeyValue = function* toKeyValue(keySelector){
2 for(let item of this)
3 yield [keySelector(item), item];
4 }
This would allow you to rewrite the previous example like this:
1 var wizardsByTitle = new Map(wizards.toKeyValue(w => w.title));
2 console.log(Array.from(wizardsByTitle.keys()));
3 // => ["The Bold", "The Mighty", "The Red"]
You could even bring it one step further by creating a toMap function:
1 Array.prototype.toMap = function(keySelector) {
2 return new Map(this.toKeyValue(keySelector));
3 }
4 var wizardsByTitle = wizards.toMap(w => w.title);
5 console.log(Array.from(wizardsByTitle.keys()));
6 // => ["The Bold", "The Mighty", "The Red"]
Map Cheatsheet
Basic Operations
| Basics | description |
|---|---|
| var map = new Map() | Create an empty map |
| var map = new Map(iterator) | Create a map from an iterator |
| var value = map.get(‘key’) | Get a value from the map by key. If the key is not in the map it returns undefined. The key can be of any type. |
| map.set(‘key’, ‘value’) | Add an item to the map. If the key already exists within the map the value is overwritten. The key and value can be of any type. Chainable. |
| map.delete(‘key’) | Remove item by key if it exists. Returns true if an item has been removed and false otherwise. |
| map.has(‘key’) | Check whether a key exists in the map. Returns true or false whether the key exists or not respectively. |
| map.size | Returns the number of items in the map |
| map.clear() | Remove all items within the map |
Iterating a Map
| Methods of Iteration | description |
|---|---|
| map.forEach((key,value,map) ⇒ {}) | Iterate over every key value pair within a map |
| map.entries() | Returns a key/value pair iterator. This is the default iterator in Map.prototype[Symbol.iterator] |
| map.keys() | Returns a key iterator |
| map.values() | Returns a values iterator |
Concluding
In this chapter you learnt how you can take advantage of the new Map data structure to store data by an arbitrary key of your choice. Map is JavaScript’s implementation of a HashTable, or a Dictionary in C#, where you can use any type as key and as value.
You also learnt about the basic operations you can perform with a Map, how you can store, retrieve and remove data, check whether or not a key exists within the Map and how to iterate it in different ways.
Exercises
Sets, For When There Can Only Be One
We live in a world
that celebrates personality.
Enjoy your uniqueness,
wear it on your sleeve,
wherever you go.
People will love you for it.
- Lenrolc Srich
Be yourself
You Are One of a Kind
A Set is a data structure used to represent a distinct collection of items where each item is unique and only appears once. This is such a common need that, if you have been working with JavaScript for a little while, chances are that you have needed to roll your own implementation at some point. Well, you’ll need to do that no more because ES6 comes with a native Set implementation. Hurrah!!
Working With Sets
You can create a new set using the Set constructor:
1 let set = new Set();
Or from an iterable collection like an array:
1 let elementsOfMagic = new Set([
2 'earth', 'fire', 'air',
3 'earth', 'fire', 'water'
4 ]);
5
6 console.log(`These are the elements of magic: ` +
7 `${[...elementsOfMagic]}`);
8 // => These are the elements of magic: earth, fire, air, water
As you can appreciate from the example above, the array had a duplicated value of earth that is removed when creating the Set. That’s because a Set will automatically remove any duplicated items and only store each specific item once.
You can easily add more items to a Set using the add method:
1 elementsOfMagic.add('aether');
2
3 console.log(`More magic!: ${[...elementsOfMagic]}`);
4 // => More magic!: earth, fire, air, water, aether
The add method is chainable, so adding multiple new items is very convenient:
1 elementsOfMagic.add('earth').add('air').add('water');
You can check whether an item exists within a Set by using the has method:
1 console.log(`Is water one of the sacred elements of magic?` +
2 ` ${elementsOfMagic.has('water')}`)
3 // => Is water one of the sacred elements of magic? true
And you can remove items from a set using delete:
1 elementsOfMagic.delete('aether');
2
3 console.log(`The aether element flows like the tides and
4 like the tides sometimes disappears:
5 ${[...elementsOfMagic]}`);
6
7 // => The aether element flows
8 // like the tides and sometimes disappears:
9 // earth,fire,air,water
Additionally, you can get the number of elements within a set using the size property:
1 console.log(`${elementsOfMagic.size} are the elements of magic`);
And remove all the items from a set using clear:
1 const castMagicShield = () => elementsOfMagic.clear();
2 castMagicShield();
3
4 console.log(`ups! I can't feel the elements: ` +
5 `${elementsOfMagic.size}`);
6 // => ups! I can't feel the elements: 0
If you take a minute to reflect about the Set API and try to remember the Map from the previous chapter you’ll realize that both APIs are exceptionally consistent with each other. Consistency is awesome, it will help you learn these APIs in a heartbeat and write less error-prone code.
Let’s see how we iterate over the elements of a Set.
Iterating Sets
Just like Map you can iterate over the elements of a Set using the for/of loop:
1 elementsOfMagic.add('fire').add('water').add('air').add('earth');
2 for(let element of elementsOfMagic){
3 console.log(`element: ${element}`);
4 }
5 // => element: fire
6 // element: water
7 // element: air
8 // element: earth
In this case, instead of key/value pairs you iterate over each item within a Set. Notice how the elements are iterated in the same order as they were inserted. The default iterator for a Set is the values iterator. The next snippet of code is equivalent to the one above:
1 for(let element of elementsOfMagic.values()){
2 console.log(`element: ${element}`);
3 }
The Set also has iterators for keys and entries just like the Map although you probably won’t need to use them. The keys iterator is equivalent to values. The entries iterator transforms each item into a key/value pair where both the key and the value are each item in the Set. So if you use the entries iterator you’ll just iterate over [value, value] pairs.
In addition to using either of these iterators, you can take advantage of the Set.prototype.forEach method to traverse the items in a Set:
1 elementsOfMagic.forEach((value, alsoValue, set) => {
2 console.log(`element: ${value}`);
3 })
4 // => element: fire
5 // element: water
6 // element: air
7 // element: earth
Using Array Methods With Sets
The conversion between Sets to Arrays and back is so straightforward that using all the great methods available in the Array.prototype object is one little step away:
1 function filterSet(set, predicate){
2 var filteredItems = [...set].filter(predicate);
3 return new Set(filteredItems);
4 }
5
6 var aElements = filterSet(elementsOfMagic, e => e.startsWith('a'));
7 console.log(`Elements of Magic starting with a: ${[...aElements]}`);
8 // => Elements of Magic starting with a: air
We saw many of these methods in the Array’s chapter but we will see many more in the functional programming tome where we discover its secret LINQ-like abilities.
How Do Sets Understand Equality?
So far you’ve seen that a Set removes duplicated items whenever we try to add them to the Set. But how does it know whether or not two items are equal?
Well… It uses strict equality comparison (which you may also known as === or !==). This is important to understand because it poses a very big limitation to using Sets in real world applications today. That’s because even though strict equality comparison works great with numbers and strings, it compares objects by reference, that is, two objects are only equal if they are the same object.
Let’s illustrate this problematic situation with an example. Let’s say that we have a Set of persons which, of course, are unique entities (we are all beautiful individual wonders just like precious stones):
1 let persons = new Set();
We create a person object randalf and we attempt to add it twice to the Set:
1 let randalf = {id: 1, name: 'randalf'};
2
3 persons
4 .add(randalf)
5 .add(randalf);
6
7 console.log(`I have ${persons.size} person`)
8 // => I have 1 person
9
10 console.log([...persons]);
11 // => [[object Object] {
12 // id: 1,
13 // name: "randalf"
14 //}]
The Set has our back and only adds the person once. Since it is the same object, using strict equality works in this scenario. However, what would happen if we were to add an object that we considered to be equal in our problem domain?
So let’s say that in a new and innovative view of the world two persons are equal if they have the same properties, and particularly the same id (Imagine randalf meeting randalf from the future, they are equal, but not the same):
1 persons.add({id: 1, name: 'randalf'});
2 console.log(`I have ${person.size} persons?!?`)
3
4 // => I have 2 persons?!?
5 console.log([...persons]);
6 /*
7 *= [[object Object] {
8 id: 1,
9 name: "randalf"
10 }, [object Object] {
11 id: 1,
12 name: "randalf"
13 }]
14 */
Well, in that case, the object would be added to the Set and as a result, and for all intents and purposes, we would have the same person twice. Unfortunately there’s no way to specify equality for the elements within a Set as of today and we’ll have to wait to see this feature introduced into the language some time in the future.
We are free to imagine how it would look though, and something like this would work wonderfully:
1 let personsSet = new Set([], p => p.id);
In the meantime, if you need to use Set-like functionality for objects your best bet is to use a dictionary indexing objects by a key that represents their uniqueness.
1 var fakeSetThisIsAHack = new Map();
2 fakeSetThisIsAHack
3 .set(randalf.id, randalf)
4 .set(1, {id: 1, name: 'randalf'});
5 console.log(`fake set has ${fakeSetThisIsAHack.size} item`);
6 // => fake set has 1 item
Sets Cheatsheet
Basic Operations
| Basics | description |
|---|---|
| var set = new Set() | Create an empty set |
| var set = new Set(iterator) | Create a set from an iterator |
| set.add(‘value’) | Add an item to the set if it is not in the set already. The items added to the set can be of any type. It uses strict equality comparison to determine that. Chainable. |
| set.delete(‘value’) | Remove item if it exists. Returns true if an item has been removed and false otherwise. |
| set.has(‘value’) | Check whether an item exists in the set. Returns true or false whether the key exists or not respectively. |
| set.size | Returns the number of items in the set |
| set.clear() | Remove all items within the set |
Iterating a Set
| Methods of Iteration | description |
|---|---|
| set.forEach((value,value,map) ⇒ {}) | Iterate over every item within a set |
| set.value() | Returns a value iterator. This is the Set default iterator |
| set.keys() | Returns a key iterator which just lets you iterate over the items within a set (just like values) |
| set.entries() | Returns a key/value pair iterator which lets you iterate over pairs of value/value for those items within a set |
Concluding
The Set is a new data structure in ES6 that lets you easily remove duplicates from a collection of items. It offers a very simple API very consistent with the Map API and it’s going to be a great addition to your arsenal and save you the need to roll your own.
Unfortunately, at present, it has a big limitation that is that it only supports strict equality comparison to determine whether two items are equal. Hopefully in the near future we will be able to define our own custom version of equality and that day Sets will achieve their true potential. Until then use Set with numbers and strings, and rely on Map when you are working with objects.