Collection of JavaScript data structures and algorithms of Set
- 2020-12-09 00:42:39
- OfStack
Collection (Set)
Speaking of sets, I think of just entering high school, math lesson 1 is about sets. Therefore, when learning the data structure of collection, it is very intimate.
A basic property of a set is that its elements are not repeated. Because of this nature, we chose objects as containers for collections rather than arrays.
Although the array can also do not repeat all, but ultimately too cumbersome, as a set.
Operation of sets
The basic operation of set has intersection, union, difference set and so on. Here we introduce the implementation of intersection, union and difference sets in JavaScipt set.
An implementation of a collection in JavaScipt
First, create a constructor.
/**
* The constructor of the set
*/
function Set methods {
/**
* A container of collection elements, represented as objects
* @type {Object}
*/
var items = {};
}
The collection needs to have the following methods:
has method:
Description: Elements in a collection are not duplicated. So before doing anything else, you must use the has method to verify that there is an element in the collection. The hasOwnProperty method is used here to detect this.
Implementation:
/**
* Detects if there is an element in the collection
* @param {Any} value Elements to detect
* @return {Boolean} If so, return true
*/
this.has = function(value) {
// hasOwnProperty The problem is that
// It is a 1 Method, so it might be overwritten
return items.hasOwnProperty(value)
};
add method:
Adds an element to a collection.
Implementation:
/**
* Adds an element to the collection
* @param {Any} value The element to be added
* @return {Boolean} Add success return True .
*/
this.add = function(value) {
// First check if the element exists.
if (!this.has(value)) {
items[value] = value;
return true;
}
// Returns if the element already exists false
return false;
};
remove method:
Description: Removes an element from a collection
Implementation:
/**
* Removes an element from the collection
* @param {Any} value The element to remove
* @return {Boolean} Removal successful return True .
*/
this.remove = function(value) {
// First check if the element exists.
if (this.has(value)) {
delete items[value];
return true;
}
// If the element does not exist, the delete failure returns false
return false;
};
clear method:
Description: Empty the collection
Implementation:
/**
* Empty the collection
*/
this.clear = function() {
this.items = {};
};
size method
Description: Return the length of the collection. There are two ways to do this. The first method uses Object.keys, Api, but only supports IE9 and above. The second applies to all browsers.
Implementation:
/**
* Returns the length of the collection, available only for IE9 And above
* @return {Number} Set the length of the
*/
this.size = function() {
// Object.keys Method converts an object to an array
// Only can be used to IE9 And above, but very convenient
return Object.keys(items).length;
}
/**
* Returns the length of the collection, available for all browsers
* @return {Number} Set the length of the
*/
this.sizeLegacy = function() {
var count = 0;
for (var prop in items) {
if (items.hasOwnProperty(prop)) {
++count;
}
}
return count;
}
values method
Description: Returns an array of collection transformations. There are also two methods. For the same reason. Object. keys is used and can only support IE9 and above.
Implementation:
/**
* Returns an array of collection transformations, available only for IE9 And above
* @return {Array} The converted array
*/
this.values = function() {
return Object.keys(items);
};
/**
* Returns an array of collection transformations available to all browsers
* @return {Array} The converted array
*/
this.valuesLegacy = function() {
var keys = [];
for (var key in items) {
keys.push(key)
};
return keys;
};
union method
Description: Returns the union of two sets
Implementation:
/**
* Returns the union of two sets
* @param {Set} otherSet A collection of operations to union
* @return {Set} The union of two sets
*/
this.union = function(otherSet) {
// Initialize the 1 Two new sets, used to represent the union.
var unionSet = new Set();
// Converts the current collection to an array and adds it in turn unionSet
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
// Converts other collections to arrays and adds them in turn unionSet .
// In the loop add Method ensures that no duplicate elements will occur
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
return unionSet;
};
intersection method
Description: Returns the intersection of two collections
Implementation:
/**
* Returns the intersection of two sets
* @param {Set} otherSet The set to perform an intersection operation
* @return {Set} The intersection of two sets
*/
this.intersection = function(otherSet) {
// Initialize the 1 Three new sets for representing the intersection.
var interSectionSet = new Set();
// Converts the current collection to an array
var values = this.values();
// Iterate over the groups if otherwise 1 A set also has the element, then interSectionSet Add this element.
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
interSectionSet.add(values[i])
}
}
return interSectionSet;
};
difference method
Description: Returns the difference set of two sets
Implementation:
/**
* Returns the difference set of two sets
* @param {Set} otherSet The set of operations to be performed
* @return {Set} The difference set of two sets
*/
this.difference = function(otherSet) {
// Initialize the 1 Two new sets, used to represent the difference set.
var differenceSet = new Set();
// Converts the current collection to an array
var values = this.values();
// Iterate over the groups if otherwise 1 Sets without the element, then differenceSet Add this element.
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet;
};
subset method
Description: determines whether the collection is a subset of the incoming collection. After Writing this code myself, I compared it to book 1 and found myself super low. What I wrote needs to be repeated three times, and what I wrote in the book only needs to be repeated once, so the algorithm complexity is much lower than mine.
Implementation:
/**
* Detects if there is an element in the collection
* @param {Any} value Elements to detect
* @return {Boolean} If so, return true
*/
this.has = function(value) {
// hasOwnProperty The problem is that
// It is a 1 Method, so it might be overwritten
return items.hasOwnProperty(value)
};
The collection in ES6
ES6 also provides collections, but the previous ES6 collection operation 1 was confusing. After the realization of 1 time to see, feel the concept of a lot clearer.
I don't have a good command of the details. I'm still learning, so I won't write them down. Please refer to the introduction of ES6 Set in Ruan 1feng's Introduction to ECMAScript 6.
Introduction to ECMAScript 6 - Set and Map data structures
feeling
At this point, you have mastered 1 of the basic data structures. The rest is tough (for me).
Hash table, graph, tree, sorting algorithm of dictionary. It's the big four, so the recent series of articles on data structures and algorithms may be slow to update. For me, it's a bit of a hurdle. I hope I can get over this obstacle this winter holiday.