Arrays have long been the only collection type in JavaScript. JS arrays function just as they do in other languages, but prior to ES6, they were often used to create queues and stacks due to the limited collection types available and the use of numeric indexes for arrays. If developers needed to use non-numeric indexes, they used non-array objects to create the data structures they needed, and this was an early implementation of sets and maps. Then follow me to understand these two data structures, and finally to personally implement a Set and Map in ES6.

Map set in ES6

A collection of

  • A set is a set of unordered and unique (that is, unrepeatable) items. We can think of it as an unordered array where each element is unique
  • Set provided by ES6. It is similar to an array, but the values of the members are unique and there are no duplicate values
  • The Set itself is a constructor used to generate the Set data structure

Let’s look at the description of the use of Set in MDN

Let array = [1,2,1,4,5,3]; [...new Set(array)] // [1, 2, 4, 5, 3]Copy the code

Next, take a look at the collection implemented based on the Set class (data structure) in ES6

Properties and methods of a Set instance

  • Set attributes:

    • Size: Returns the number of elements contained in the collection

  • The Set method:

    • Operation method

      • Add (value) : Adds a new item to the collection
      • Delete (value) : Removes a value from the collection
      • Has (value) : Returns true if the value exists in the collection, false otherwise
      • Clear (): Removes all items in the set

    • Traversal methods

      • Keys () : Returns an array containing all the keys in the collection
      • Values () : Returns an array containing all the values in the collection
      • Entries: Return an array of all key-value pairs in the collection
      • ForEach () : Used to perform an operation on a collection member, with no return value

Create a Set

The constructor of a Set can take any iterable, such as an array, a Set, or a Map.

Const set = new set () set.add(5) set.add('5') // Repeated additions will be ignored set.add(5) console.log(set.size) // 2Copy the code

From the way

The first thing to implement is the HAS method, which is called in other methods like Add and DELETE, so let’s look at its implementation

function Set() { let items = {}; this.size = 0; This. Has = function(val) {return items.hasownProperty (val); }; }Copy the code

Delete and clear methods

So let’s go ahead and write both this time

This. delete = function(val) {if (this.has(val)) {delete items[val]; // Delete the items property this.size--; return true; } return false; }; This. Clear = function() {items = {}; This. size = 0; };Copy the code

All of the above is the operation method, let’s implement the traversal method again

Keys, values methods

These two methods can be implemented together, because it is easy to implement the corresponding method through the ES6 extension of Object, let’s see the concrete implementation, above code:

This. Keys = function() {return object.keys (items); // Return an array of keys iterating through the collection}; // values() method this.values = function() {return object.values (items); // Return an array of keys iterating through the collection};Copy the code

Let’s use it and see

// set.js const Set = require('./Set.js'); Let Set = new Set(); set.add(1); set.add(3); set.add(2); console.log(set.keys()); // [ '1', '2', '3' ] console.log(set.values()); // [1, 2, 3]Copy the code

The forEach method

ForEach = forEach = forEach = forEach = forEach = forEach = forEach = forEach = forEach = forEach = forEach = forEach

ForEach = forEach = forEach = forEach = forEach = forEach

ForEach = function(fn, context = this) {for (let I = 0; i < this.size; i++) { let item = Object.keys(items)[i]; fn.call(context, item, item, items); }};Copy the code

Use the forEach method

// set.js const Set = require('./Set.js'); let set = new Set(); set.add(1); set.add(4); set.add('3'); set.forEach((value, key) => console.log(key + ' : ' + value)); // 1:1, 3:3, 4:4 let arr = set.values(); // [ 1, 3, 4 ] arr = new Set(arr.map(x => x * 2)).values(); console.log(arr); // [2, 6, 8]Copy the code

Basically implement the Set structure method, however, found a problem, that is, every time you add an element to add this is really cumbersome to write, Set can accept an array as a parameter, so let’s implement this

Function Set(arr = []) {function Set(arr = []) {// Let items = {}; this.size = 0; This. Has = function (val) {return items. HasOwnProperty (val); }; This. add = function (val) {// If (! this.has(val)) { items[val] = val; this.size++; return true; } return false; }; Arr. ForEach ((val, I) => {// iterate over the array passed this.add(val); // add each item to the collection}); }Copy the code

Let’s see if we can now support arrays passed in

// use map and filter const Set = require('./ set.js '); let arr = new Set([1, 2, 3]).values(); m = new Set(arr.map(x => x * 2)); f = new Set(arr.filter(x => x>1)); console.log(m.values()); // [ 2, 4, 6 ] console.log(f.values()); / / [2, 3] / / array to heavy let arr2 = new Set ([3, 5, 2, 1, 2, 5, 5)). The values (); console.log(arr2); // [1, 2, 3, 5]Copy the code

In addition, Set can also implement union, intersection, difference.

We have to do the whole thing, so let’s do it one at a time

Union and INTERSECT

  • The mathematical concept of A union, the union of A and B, is denoted as A∪B
  • The mathematical concept of intersection, the intersection of sets A and B, is expressed as A∩B

As shown in the figure:

Now let’s implement the union method

This. union = function (other) {let union = new Set(); let values = this.values(); for (let i = 0; i < values.length; i++) { union.add(values[i]); } values = other.values(); For (let I = 0; i < values.length; i++) { union.add(values[i]); } return union; }; // intersection this.intersect = function (other) {let intersect = new Set(); let values = this.values(); for (let i = 0; i < values.length; I ++) {if (other.has(values[I])) {intersect. Add (values[I]); }} return intersect; };Copy the code

Let’s see how the difference sets are implemented, and then let’s test them together

Difference difference set

  • The mathematical concept of the difference set, the difference set of A and B, is represented as A minus B

// this. Difference = function (other) {let difference = new Set(); let values = this.values(); for (let i = 0; i < values.length; i++) { if (! Other.has (values[I])) {// Add (values[I]); // add(values[I]); } } return difference; };Copy the code

Full implementation of Set

In this, first to you stick a complete implementation code

function Set(arr = []) { let items = {}; this.size = 0; This. Has = function (val) {return items. HasOwnProperty (val); }; This. add = function (val) {// If (! this.has(val)) { items[val] = val; this.size++; return true; } return false; }; arr.forEach((val, i) => { this.add(val); }); This. delete = function (val) {if (this.has(val)) {delete items[val]; // Delete the items property this.size--; return true; } return false; }; This. Clear = function () {items = {}; this.size = 0; }; This. Keys = function () {return object.keys (items); }; // values method this.values = function () {return object.values (items); ForEach = function (fn, context = this) {for (let I = 0; i < this.size; i++) { let item = Object.keys(items)[i]; fn.call(context, item, item, items); }} this.union = function (other) {let union = new Set(); let values = this.values(); for (let i = 0; i < values.length; i++) { union.add(values[i]); } values = other.values(); For (let I = 0; i < values.length; i++) { union.add(values[i]); } return union; }; // intersection this.intersect = function (other) {let intersect = new Set(); let values = this.values(); for (let i = 0; i < values.length; i++) { if (other.has(values[i])) { intersect.add(values[i]); } } return intersect; }; // this. Difference = function (other) {let difference = new Set(); let values = this.values(); for (let i = 0; i < values.length; i++) { if (! other.has(values[i])) { difference.add(values[i]); } } return difference; }; Subset = function(other) {if (this.size > other.size) {return false; } else { let values = this.values(); for (let i = 0; i < values.length; i++) { console.log(values[i]) console.log(other.values()) if (! other.has(values[i])) { return false; } } return true; }}; } module.exports = Set;Copy the code

Let’s test it out

const Set = require('./Set.js'); let set = new Set([2, 1, 3]); console.log(set.keys()); // [ '1', '2', '3' ] console.log(set.values()); // [ 1, 2, 3 ] console.log(set.size); // 3 set.delete(1); console.log(set.values()); // [ 2, 3 ] set.clear(); console.log(set.size); // let a = [1, 2, 3]; let b = new Set([4, 3, 2]); let union = new Set(a).union(b).values(); console.log(union); / / [1, 2, 3, 4] / / intersection let c = new Set ([4, 3, 2)); Let intersect = new Set([1,2,3]).intersect(c).values(); console.log(intersect); // [2, 3] // let d = new Set([4, 3, 2]); Let difference = new Set([1,2,3]).difference(d).values(); // the difference set between [1,2,3] and [4,3,2] is 1 console.log(difference); / / [1]Copy the code

So far we have used the Set data structure to implement a similar ES6 Set class.

Now that we’ve done the Set implementation, let’s go ahead and write the Map as well.

The dictionary

Another structure in the data structure is called a dictionary, which implements the Map class based on ES6

So what’s the difference between a set and a dictionary?

  • Common: Collections and dictionaries can store values that are not duplicated
  • Differences: Collections store elements as values, dictionaries as keys

Therefore, it is clear that Map is also used to store data. Compared with Object, Map only provides “string-value” mapping, whereas Map provides “value-value” mapping. That is, if you need key-value data structures, Map is better than Object

Here’s a look at the basics:

const m = new Map();
const o = {p: 'Hello World'};
m.set(o, 'content')
m.get(o) // "content"

m.has(o) // true
m.delete(o) // true
m.has(o) // false
Copy the code

This is the basic use of Map, and more useful methods will be shown later as the implementation progresses

Map properties and methods

Properties:

  • Size: Returns the number of elements contained in the dictionary

Operation method:

  • Set (key, val): Adds a new element to the dictionary
  • Get (key): Finds a specific value by key value and returns it
  • Has (key): Returns true if the key exists in the dictionary, false otherwise
  • Delete (key): Removes the corresponding data from the dictionary by key value
  • Clear (): Removes all elements from this dictionary

Traversal method:

  • Keys (): Returns all the key names contained in the dictionary as an array
  • Values (): Returns all values contained in the dictionary as an array
  • ForEach () : Traverses all the members of the dictionary

Now that you know what properties and methods are available, start by creating a dictionary

Create a dictionary

function Map() { let items = {}; } module.exports = Map; / / exportCopy the code

Now that you’ve created the skeleton of a dictionary, start adding some methods

From the way

The first is of course has, because it’s used in both set and get, and the implementation is very similar to the set I wrote earlier

function Map() { let items = {}; This. Has = function(val) {return items. HasOwnProperty (val); }; }Copy the code

Once we have implemented the HAS method, we can determine whether the dictionary contains the property and proceed to implement other methods

Set and get methods

Set (key, val); // Set (key, val);  new Map().set({}, 'a') this.set = function(key, val) { items[key] = val; }; This. get = function(key) {// If an unknown key is read, undefined return this.has(key)? items[key] : undefined; };Copy the code

Set and get, delete and clear, no nonsense

Delete and clear methods

This. delete = function(key) {if (this.has(key)) {// delete items[key]; // Delete the items attribute this.size--; Return true; } return false; }; // clear() this.clear = function() {items = {}; this.size = 0; };Copy the code

The above attributes and operation methods are respectively completed, there are still the last traversal method, continue to write, adhere to the end is victory, you see the officer is not easy, refueling refueling!!

Traversal method (keys,values,forEach)

This. Keys = function() {return object.keys (items); }; // values() method this.values = function() {return object.values (items); }; ForEach = function(fn, context = this) {for (let I = 0; i < this.size; i++) { let key = Object.keys(items)[i]; let value = Object.values(items)[i]; fn.call(context, value, key, items); }};Copy the code

Now has finally completed the implementation of the Map class. I will post the complete code and test cases for you to study and analyze in your spare time

Map complete implementation

function Map() { let items = {}; this.size = 0; This. Has = function(val) {return items. HasOwnProperty (val); }; // set(key, val) this.set = function(key, val) {items[key] = val; this.size++; }; Get = function(key) {return this.has(key)? items[key] : undefined; }; This. delete = function(key) {if (this.has(key)) {delete items[key]; this.size--; return true; } return false; }; // clear() this.clear = function() {items = {}; this.size = 0; }; This. Keys = function() {return object.keys (items); }; // values() method this.values = function() {return object.values (items); }; ForEach = function(fn, context = this) {for (let I = 0; i < this.size; i++) { let key = Object.keys(items)[i]; let value = Object.values(items)[i]; fn.call(context, value, key, items); }}; } module.exports = Map;Copy the code

Take a look at the following test chestnut

// map.js // use map class const map = require('./ map.js '); let m = new Map(); Margaret spellings et (' Jay ', 'Jay Chou'); M.et (true, 'true '); console.log(m.has('Chou')); // false console.log(m.size); // 2 console.log(m.keys()); // [ 'Jay', 'true' ] console.log(m.values()); / / [' Jay Chou ', 'really'] the console. The log (m.g et (' Jay ')); // undefined m.delete(true); console.log(m.keys()); // [ 'Jay' ] console.log(m.values()); // ['Jay Chou']Copy the code