What is a set?

  • A set is an unordered set of unique items. You can think of a set as an array with no repeating elements and no notion of order. There’s another concept called empty sets. An empty set is a set that does not contain any elements. The empty set is represented by {}.

Creating a collection Class

  • ECMAScript2015 introduces the Set class as part of the Javascript API, and we will implement our own Set class based on ES2015’s Set class. We will also implement some set operations not provided by native ES2015, such as union, intersection, and difference sets.
class Set {
    constructor() {
        this.items = {}; }}Copy the code
  • We use objects instead of arrays to represent collections for two reasons:
    • The first is because most methods have O(n) time complexity when using arrays. That is, we need to iterate through the entire array until we find the element we’re looking for, or in the worst case, all of the array. If the array has more elements, it takes longer. In addition, an array is an ordered collection of elements. To keep the elements organized, it takes up more memory.
    • Another is that because Javascript objects don’t allow a key to point to two different properties, it also ensures that the elements in the collection are unique.

Old fashioned – Let’s do some Set methods

1. Has () tests whether an element exists in the set

has(element) {
    return Object.prototype.hasOwnProperty.call(this.items, element); // Returns a Boolean value indicating whether the object has a particular property
  }
Copy the code
  • The Object prototype has the hasOwnProperty method. This method returns a Boolean value indicating whether the object has a particular property.
  • Can also use this. Items. HasOwnProperty (element), but this code inspection tools such as (ESLint) will throw an error. The error is that not all objects inherit from Object.prototype and even the hasOwnProperty method on the inherited Object may be overridden, causing the code to not work properly.
  • Element in Items also works. The IN operator returns a Boolean value indicating whether the object has a particular property on the stereotype chain.

2. add() adds a new element to the collection

add(element) {
    if (!this.has(element)) { / / check
      this.items[element] = element; // If it does not exist, add element to the collection, returning true {element:element}
      return true;
    }
    return false; // If there are identical elements in the collection, return false
  }
Copy the code
  • When you add an element, store it as both a key and a value, because it makes it easier to find the element

3. delete () deletes an element from the collection

delete(element) {
    if (this.has(element)) { // Select * from (select * from (select * from));
      delete this.items[element]; // Remove element from the collection
      return true; / / return true
    }
    return false; // If there is none in the collection, return false
  }
Copy the code
  • Since we use objects to store the items object of the collection, we can simply use the DELETE operator to remove properties from the Items object.

4. Size () returns how many elements there are in the collection

size() { // Returns the number of elements in the collection
    return Object.keys(this.items).length; // Use the native built-in method to convert the object's key to an array and return its length
  }
Copy the code

5. values() returns an array containing all the values in the collection

values() { // Returns an array containing all the values in the collection
    return Object.values(this.items); // Use native methods as well (it was added in ECMAscript2017 and is only available in current browsers)
  }
Copy the code
  • You now have an implementation of the Set class that is very similar to the one in ECMASscript2015.

Set operations

  • We can perform the following operation on the set:
    • Union: For a given set of two sets, a new set containing all the elements of both sets is returned.
    • Intersection: For a given set of two sets, returns a new set containing elements in both sets.
    • Difference set: For a given set of two sets, return a new set containing all elements that exist in the first set and not in the second.
    • Subset: Verifies whether a given set is a subset of another set.

1. And set

  • The set is defined as x (an element) in A, or x in B. The implementation code is as follows:
union(otherSet) {
    const unionSet = new Set(a);// Create a new collection
    this.values().forEach(value= > unionSet.add(value)); // Get all the values of the first set (the current instance of the set class) and add them to the new set
    otherSet.values().forEach(value= > unionSet.add(value)); // Get all the values of the second set (the passed instance of the set class) and add them to the new set
    return unionSet; // Finally returns the new collection created
  }
Copy the code

2. The intersection

  • The set consisting of all the elements that belong to set A and belong to set B is called the intersection of set A and set B. The implementation code is as follows:
intersection(otherSet) {
    const intersectionSet = new Set(a);// Create a new collection
    const values = this.values(); // Get the first set (the current set instance)
    const otherValues = otherSet.values(); // Get the second set (the passed instance of the set class)
    let biggerSet = values; // Suppose the current collection has more elements
    let smallerSet = otherValues; // Fewer elements are passed into the collection
    if (otherValues.length - values.length > 0) { // Compare the number of elements in two sets
      biggerSet = otherValues; // If the number of elements passed into the set is greater than the number of elements in the current set, swap more elements equal to the number of elements passed in
      smallerSet = values; // Less equals the current set
    }
    smallerSet.forEach(value= > { // The last iteration has fewer collections
      if (biggerSet.includes(value)) { // If the larger set also has this element
        intersectionSet.add(value); // Add to the new collection}});return intersectionSet; // return the new collection
  }
Copy the code
  • We first create a new collection to hold the results returned by the Intersection method.
  • You then get the values in the current collection instance and the values in the incoming collection.
  • Let’s assume there are more elements in the current collection and fewer elements in the incoming collection.
  • Then compare the number of elements in the two sets. If the other set has more elements than the current set, swap the more elements to the passed in, and the less elements to the current set.
  • Iterate over smaller sets, and if both sets have the current element, insert it into the new set
  • Finally return the new collection
  • The purpose of comparing the number of elements in the two sets is to minimize the number of iterations. Fewer iterations means less process consumption.

3. The difference set

  • The element exists in A, and x does not exist in B. The implementation code is as follows:
difference(otherSet) {
    const differenceSet = new Set(a);// Create a new collection
    this.values().forEach(value= > { // The value of the current collection is converted to an array and looped through
      if(! otherSet.has(value)) {// If this element is not in the collection passed in
        differenceSet.add(value); // Add it to the new collection}});return differenceSet; // return a new collection
  }
Copy the code

4. The subset

  • Every member of set A also needs to be in set B. The implementation code is as follows:
isSubsetOf(otherSet) {
    if (this.size() > otherSet.size()) { // If the current collection has more elements than the incoming collection, it is definitely not a subset of the incoming collection, returns false
      return false;
    }
    let isSubset = true; // Assume that the current collection is a subset of the incoming collection
    // Iterate through the current collection. If one returns false, no more execution.
    this.values().every(value= > {
      if(! otherSet.has(value)) {// Verify that the iterated elements also exist in the incoming collection
        isSubset = false; // Change the variable as long as one is not
        return false; // Return false and do not proceed further
      }
      return true; // If so, return true
    });
    return isSubset; // Finally return the variable isSubset
  }
Copy the code
  • Verify that the current set has fewer elements than the incoming set. If the current set has more elements than the incoming set, it is definitely not a subset of the incoming set. Return false
  • We then assume that the current set is a subset of the incoming set.
  • Iterate over all the elements of the current collection, verifying that these elements also exist in the incoming collection.
  • If there is any element that does not exist in the incoming collection, that means it is not a subset, return false.
  • Return true if all elements exist in the passed in set, isSubset variable does not change.
  • In the subset method we use the every method. When we find that a value does not exist in the incoming set, we can stop iterating over the value to indicate that it is not a subset.

ECMAScript2015 – Set class

  • Let’s start with the native set class:
const set = new Set(a); set.add(1);
console.log(set.values()); / / output @ Iterator
console.log(set.has(1)); / / output true
console.log(set.values()); / / output 1
Copy the code
  • The values method of ES2015’s set returns an Iterator (an Iterator object containing key-value pairs) rather than an array of values.
  • Another difference is that the size method we implemented returns the number of values stored in the set, whereas ES2015 sets have a size attribute.
  • Our set class implements mathematical operations such as union, intersection, difference, and subset, whereas ES6 native sets do not.

ES6Set operation simulation

  • Let’s start by creating two collections, which we’ll use later
const setA = new Set(a); setA.add(1);
setA.add(2);
setA.add(3);

const setB = new Set(a); setB.add(2);
setB.add(3);
setB.add(4);
Copy the code
  1. Simulate union operation
const union = (set1, set2) = > { // Normal simulation
  const unionAb = new Set(a); set1.forEach(value= > unionAb.add(value));
  set2.forEach(value= > unionAb.add(value));
  return unionAb;
};
console.log(union(setA, setB)); / / [1, 2, 3, 4]

console.log(new Set([...setA, ...setB]));  // use extended operators to simulate [1,2,3,4]
Copy the code
  1. Simulated intersection operation
const intersection = (set1, set2) = > { // Normal simulation, not optimized
  const intersectionSet = new Set(a); set1.forEach(value= > {
    if(set2.has(value)) { intersectionSet.add(value); }});return intersectionSet;
};
console.log(intersection(setA, setB)); / / [2, 3]

console.log(new Set([...setA].filter(x= > setB.has(x)))); // simulate with extended operators [2,3]
Copy the code
  1. Simulation of difference set operation
const difference = (set1, set2) = > { // Normal simulation
  const differenceSet = new Set(a); set1.forEach(value= > {
    if (!set2.has(value)) {
      differenceSet.add(value);
    }
  });
  return differenceSet;
};
console.log(difference(setA, setB));/ / [1]

console.log(new Set([...setA].filter(x= >! setB.has(x))));// Use extended operator emulation [1]
Copy the code

The last

All right, that’s all for today’s notes. The content of this article is from my reading “Learning Javascript data structures and algorithms” chapter 7 after a little collation.