(recommended intensive reading) native JS soul of the question (middle), check whether they are really familiar with JavaScript?

The author has been systematically combing the knowledge of native JS recently, because I think JS is the fundamental technology of front-end engineers, and it is too much to learn. I plan to do a series of three rounds, driven by a series of questions, of course, there will also be questioning and expansion, the content is systematic and complete, the junior and intermediate players will have a good improvement, advanced players will also be reviewed and consolidated. This is the second article in this series.

After glancing at the list, you might say: Why should I have something I haven’t used in 800 years? Yes, I admit that real business scenarios such as handwritten Splice, deep copy are not often encountered, but I will say that the original purpose of asking these questions is not to get you to use, but to check whether your understanding of the JS language has reached that level, whether there are certain boundary cases that can be considered, Do you have basic computer literacy (e.g. do you understand basic sorting methods) and the potential to design better products or frameworks in the future? If you just want an article to solve a temporary problem in your business, then please go out and turn left. This article is not for you. But if you feel you need to improve your native programming skills and want to take your thinking skills to the next level, I hope my 16,000-word article will help you grow. In addition, this article is not intended for an interview, but any of the following would be amazing in an interview 🙂

Why is arguments not an array? How do I convert to an array?

Arguments does not call array methods by itself. It is a different object type, but the properties are sorted from 0, 0, 1, 2… Finally, we have the Callee and length properties. We also refer to such objects as class arrays.

Common class arrays include:

1. Using getElementsByTagName/ClassName HTMLCollection ()
1. The nodeList obtained by querySelector

So that makes a lot of the array methods unavailable, and we need to convert them to an array if we need to. What are the methods?

1. Array.prototype.slice.call()

function sum(a, b) {
  let args = Array.prototype.slice.call(arguments);
  console.log(args.reduce((sum, cur) = > sum + cur));//args can call methods native to the array
}
sum(1.2);/ / 3
Copy the code

2. Array.from()

function sum(a, b) {
  let args = Array.from(arguments);
  console.log(args.reduce((sum, cur) = > sum + cur));//args can call methods native to the array
}
sum(1.2);/ / 3
Copy the code

This method can also be used to transform sets and maps.

3. ES6 expansion operator

function sum(a, b) {
  let args = [...arguments];
  console.log(args.reduce((sum, cur) = > sum + cur));//args can call methods native to the array
}
sum(1.2);/ / 3
Copy the code

4. Use the concat + the apply

function sum(a, b) {
  let args = Array.prototype.concat.apply([], arguments);// The apply method expands the second argument
  console.log(args.reduce((sum, cur) = > sum + cur));//args can call methods native to the array
}
sum(1.2);/ / 3
Copy the code

Of course, the original method is to create another array and use a for loop to put the values of each attribute in the array. It’s too simple to waste space.

Does return work in forEach? How do I break a forEach loop?

Using a return in forEach does not return, and the function continues.

let nums = [1.2.3];
nums.forEach((item, index) = > {
  return;/ / is invalid
})
Copy the code

Interrupt method:

Use try to monitor blocks of code and throw exceptions where interrupts are needed.
Official recommended method (substitution method) : Replace the forEach function with every and some. Every terminates the loop when it hits return false. Some terminates the loop when it hits return true

JS determines whether an array contains a value

Method 1: array.indexOf

This method determines whether a value exists in the array and returns the index of the array element if so, or -1 otherwise.

var arr=[1.2.3.4];
var index=arr.indexOf(3);
console.log(index);
Copy the code

Method 2: array.includes(searcElement[,fromIndex])

This method determines whether a value exists in the array and returns true if so, false otherwise

var arr=[1.2.3.4];
if(arr.includes(3))
    console.log("There");
else
    console.log("Nonexistent");
Copy the code

Array. find(callback[,thisArg])

Return the value of the first element in the array that satisfies the condition, or undefined if none exists

var arr=[1.2.3.4];
var result = arr.find(item= >{
    return item > 3
});
console.log(result);
Copy the code

Array.findeindex (callback[,thisArg])

Return the index of the first element in the array that satisfies the condition, or -1 if not found]

var arr=[1.2.3.4];
var result = arr.findIndex(item= >{
    return item > 3
});
console.log(result);
Copy the code

Of course, there’s no problem with the for loop, but we’re talking about array methods here, so I won’t expand them.

Part 10: JS array flat– flat

For front-end projects that occasionally have arrays of cascading data structures, we need to convert the multilevel array into a one-level array (that is, extract the nested array elements and merge them into a single array) so that their contents are merged and expanded. So how do you do that?

Requirements: Multidimensional arrays => one-dimensional arrays

let ary = [1[2[3[4.5]]].6];// -> [1, 2, 3, 4, 5, 6]
let str = JSON.stringify(ary);
Copy the code

1. Call the flat method in ES6

ary = ary.flat(Infinity);
Copy the code

2. replace + split

ary = str.replace(/(\[|\])/g.' ').split(', ')
Copy the code

3. replace + JSON.parse

str = str.replace(/(\[|\])/g.' ');
str = '[' + str + '] ';
ary = JSON.parse(str);
Copy the code

4. Ordinary recursion

let result = [];
let fn = function(ary) {
  for(let i = 0; i < ary.length; i++) {
    let item = ary[i];
    if (Array.isArray(ary[i])){
      fn(item);
    } else{ result.push(item); }}}Copy the code

5. Use reduce function to iterate

function flatten(ary) {
    return ary.reduce((pre, cur) = > {
        return pre.concat(Array.isArray(cur) ? flatten(cur) : cur); } []); }let ary = [1.2[3.4], [5[6.7]]]
console.log(flatten(ary))
Copy the code

6: Extension operators

// As long as one of the elements has an array, the loop continues
while (ary.some(Array.isArray)) { ary = [].concat(... ary); }Copy the code

This is a practical and easy to be asked the question, welcome to exchange and supplement.

Part 11: Higher order functions of JS array — Basic

1. What is a higher-order function

The concept is very simple, as follows:

A function that can take another function as a parameter or return a function is called a higher-order function.

So what are the methods that correspond to arrays?

2. Higher-order functions in arrays

1.map

Arguments: Takes two arguments, the callback function and (optional) the value of this.

By default, the callback function is passed three values: the current element, the current index, and the entire array.

Creates a new array with the result of calling one of the provided functions for each element in the array
It has no effect on the original array

let nums = [1.2.3];
let obj = {val: 5};
let newNums = nums.map(function(item,index,array) {
  return item + index + array[index] + this.val; 
  // For the first element, 1 + 0 + 1 + 5 = 7
  For the second element, 2 + 1 + 2 + 5 = 10
  For the third element, 3 + 2 + 3 + 5 = 13
}, obj);
console.log(newNums);/ / [7, 10, 13]
Copy the code

Of course, the following parameters are optional and can be omitted if not needed.

2. reduce

Arguments: Takes two arguments, one for the callback function and one for the initial value. The four default arguments in the callback function are the accumulated value, the current value, the current index, and the entire array.

let nums = [1.2.3];
// The sum of multiple numbers
let newNums = nums.reduce(function(preSum,curVal,currentIndex,array) {
  return preSum + curVal; 
}, 0);
console.log(newNums);/ / 6
Copy the code

What happens if I don’t pass the default?

Not passing the default value automatically starts with the first element and accumulates from the second.

3. filter

Argument: A function argument. This function takes a default argument, which is the current element. The return value of this function as an argument is a Boolean type that determines whether the element is retained.

The filter method returns a new array containing all the retained items of the argument.

let nums = [1.2.3];
// Keep the odd entries
let oddNums = nums.filter(item= > item % 2);
console.log(oddNums);
Copy the code

4. sort

Argument: A function for comparison that has two default arguments, one for the two elements that represent the comparison.

Here’s an example:

let nums = [2.3.1];
// Compare the two elements a and b respectively
nums.sort(function(a, b) {
  if(a > b) return 1;
  else if(a < b) return -1;
  else if(a == b) return 0;
})
Copy the code

When the comparison function returns a value greater than 0, then a comes after b, i.e. a’s index should be greater than b’s.

Otherwise, a comes after B, that is, a has a lower index than B.

The whole process completes an ascending order.

The other thing to notice, of course, is that when the comparison function is not passed, how does it sort?

The answer is to convert the number to a string and then sort it in ascending order according to alphabetic Unicode values, that is, according to the comparison rules of strings.

Can we implement the array map method?

According to the ecMA262 draft, the implementation of the MAP specification is as follows:

The following is a step by step simulation of the map function according to the provisions of the draft:

Array.prototype.map = function(callbackFn, thisArg) {
  // Handle an array type exception
  if (this= = =null || this= = =undefined) {
    throw new TypeError("Cannot read property 'map' of null or undefined");
  }
  // Handle callback type exceptions
  if (Object.prototype.toString.call(callbackfn) ! ="[object Function]") {
    throw new TypeError(callbackfn + ' is not a function')}// The draft mentions converting to an object first
  let O = Object(this);
  let T = thisArg;

  
  let len = O.length >>> 0;
  let A = new Array(len);
  for(let k = 0; k < len; k++) {
    // Remember in the prototype chain section? In means look in the prototype chain
    // If using hasOwnProperty is problematic, it can only find private properties
    if (k in O) {
      let kValue = O[k];
      // Pass this, the current item, the current index, and the entire array
      letmappedValue = callbackfn.call(T, KValue, k, O); A[k] = mappedValue; }}return A;
}
Copy the code

Length >>> 0, literally means “shift 0 to the right”, but in fact it fills the space with 0, so that len is a number and an integer.

A few exceptions:

null >>> 0  / / 0

undefined >>> 0  / / 0

void(0) > > >0  / / 0

function a (){};  a >>> 0  / / 0[] > > >0  / / 0

var a = {}; a >>> 0  / / 0

123123 >>> 0  / / 123123

45.2 >>> 0  / / 45

0 >>> 0  / / 0

-0 >>> 0  / / 0

-1 >>> 0  / / 4294967295

-1212 >>> 0  / / 4294966084
Copy the code

The overall implementation is not that difficult, but it is important to note that in is used for prototype chain lookup. At the same time, if not found, not processed, can effectively handle the sparse array case.

Finally give you a V8 source code, refer to the source code to check, in fact, or a very complete implementation.

function ArrayMap(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this."Array.prototype.map");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);
  if(! IS_CALLABLE(f))throw %make_type_error(kCalledNonCallable, f);
  var result = ArraySpeciesCreate(array, length);
  for (var i = 0; i < length; i++) {
    if (i in array) {
      varelement = array[i]; %CreateDataProperty(result, i, %_Call(f, receiver, element, i, array)); }}return result;
}
Copy the code

Reference:

V8 source

Array prototype method source code implementation big reveal

The draft ecma262

Is it possible to implement the Array Reduce method?

According to the ecMA262 draft, the specifications of reduce are as follows:

There are a few key points:

1. What if the initial value is not passed

2. What are the parameters of the callback function and how to handle the return value?

Array.prototype.reduce  = function(callbackfn, initialValue) {
  // Exception handling, same as map
  // Handle an array type exception
  if (this= = =null || this= = =undefined) {
    throw new TypeError("Cannot read property 'reduce' of null or undefined");
  }
  // Handle callback type exceptions
  if (Object.prototype.toString.call(callbackfn) ! ="[object Function]") {
    throw new TypeError(callbackfn + ' is not a function')}let O = Object(this);
  let len = O.length >>> 0;
  let k = 0;
  let accumulator = initialValue;
  if (accumulator === undefined) {
    for(; k < len ; k++) {
      // Find the prototype chain
      if (k in O) {
        accumulator = O[k];
        k++;
        break; }}}// Indicates that the array is empty
  if(k === len && accumulator === undefined) 
    throw new Error('Each element of the array is empty');
  for(; k < len; k++) {if (k in O) {
      // Note, core!
      accumulator = callbackfn.call(undefined, accumulator, O[k], k, O); }}return accumulator;
}
Copy the code

You actually start with the last item and go through the prototype chain and skip the empty items.

Finally, I give you the V8 source code for you to check:

function ArrayReduce(callback, current) {
  CHECK_OBJECT_COERCIBLE(this."Array.prototype.reduce");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);
  return InnerArrayReduce(callback, current, array, length,
                          arguments.length);
}

function InnerArrayReduce(callback, current, array, length, argumentsLength) {
  if(! IS_CALLABLE(callback)) {throw %make_type_error(kCalledNonCallable, callback);
  }

  var i = 0;
  find_initial: if (argumentsLength < 2) {
    for (; i < length; i++) {
      if (i in array) {
        current = array[i++];
        breakfind_initial; }}throw %make_type_error(kReduceNoInitial);
  }

  for (; i < length; i++) {
    if (i in array) {
      varelement = array[i]; current = callback(current, element, i, array); }}return current;
}
Copy the code

Reference:

V8 source

The draft ecma262

Can we implement array push and pop methods?

According to the provisions of ECMA262 draft, the specifications of push and POP are shown in the figure below:

First, implement the push method:

Array.prototype.push = function(. items) {
  let O = Object(this);
  let len = this.length >>> 0;
  let argCount = items.length >>> 0;
  // 2 ** 53-1 is the maximum positive integer that can be represented by JS
  if (len + argCount > 2支那53 - 1) {
    throw new TypeError("The number of array is over the max value restricted!")}for(let i = 0; i < argCount; i++) {
    O[len + i] = items[i];
  }
  let newLength = len + argCount;
  O.length = newLength;
  return newLength;
}
Copy the code

The hands-on test has passed all test cases on the MDN. MDN link

Then we implement the POP method:

Array.prototype.pop = function() {
  let O = Object(this);
  let len = this.length >>> 0;
  if (len === 0) {
    O.length = 0;
    return undefined;
  }
  len --;
  let value = O[len];
  delete O[len];
  O.length = len;
  return value;
}
Copy the code

The hands-on test has passed all test cases on the MDN. MDN link

Reference links:

V8 array source code

Draft specification for ecma262

MDN document

Can we implement the array filter method?

The code is as follows:

Array.prototype.filter = function(callbackfn, thisArg) {
  // Handle an array type exception
  if (this= = =null || this= = =undefined) {
    throw new TypeError("Cannot read property 'filter' of null or undefined");
  }
  // Handle callback type exceptions
  if (Object.prototype.toString.call(callbackfn) ! ="[object Function]") {
    throw new TypeError(callbackfn + ' is not a function')}let O = Object(this);
  let len = O.length >>> 0;
  let resLen = 0;
  let res = [];
  for(let i = 0; i < len; i++) {
    if (i in O) {
      let element = O[i];
      if(callbackfn.call(thisArg, O[i], i, O)) { res[resLen++] = element; }}}return res;
}
Copy the code

All test cases on the MDN pass the manual test.

Reference:

The V8 array part source is line 1025

The filter document in the MDN

Can we implement the array splice method?

Splice is arguably one of the most popular array methods, with a flexible API and easy to use. Now to comb through the usage:

1. Splice (position, count) deletes a count of elements from the position index
1. splice(position, 0, ele1, ele2, …) Inserts a sequence of elements from the elements of the position index
1. splice(postion, count, ele1, ele2, …) Delete a count of elements from the position index, and then insert a sequence of elements
1. The return value isDeleted elementConsisting of aAn array of.

Now let’s implement this method.

Refer to draft ecma262 for details.

First, let’s look at the implementation.

The preliminary implementation

Array.prototype.splice = function(startIndex, deleteCount, ... addElements)  {
  let argumentsLen = arguments.length;
  let array = Object(this);
  let len = array.length;
  let deleteArr = new Array(deleteCount);
   
  // Copy the deleted element
  sliceDeleteElements(array, startIndex, deleteCount, deleteArr);
  // Move the element after the deleted element
  movePostElements(array, startIndex, len, deleteCount, addElements);
  // Insert the new element
  for (let i = 0; i < addElements.length; i++) {
    array[startIndex + i] = addElements[i];
  }
  array.length = len - deleteCount + addElements.length;
  return deleteArr;
}
Copy the code

Copy the deleted elements first, as shown below:

const sliceDeleteElements = (array, startIndex, deleteCount, deleteArr) = > {
  for (let i = 0; i < deleteCount; i++) {
    let index = startIndex + i;
    if (index in array) {
      letcurrent = array[index]; deleteArr[i] = current; }}};Copy the code

Then move the element after the deleted element. There are three cases of movement:

The number of elements added is equal to the number of elements removed
The number of added elements is smaller than the number of deleted elements
The number of added elements is greater than the number of deleted elements

When these two are equal,

const movePostElements = (array, startIndex, len, deleteCount, addElements) = > {
  if (deleteCount === addElements.length) return;
}
Copy the code

When the number of added elements is less than the number of deleted elements, as shown in the figure:

const movePostElements = (array, startIndex, len, deleteCount, addElements) = > {
  / /...
  // If the number of added elements is not equal to the number of deleted elements, then the next element is moved
  if(deleteCount > addElements.length) {
    // If more elements are deleted than added, then the following elements will move forward
    // A total of len - startIndex - deleteCount elements need to be moved
    for (let i = startIndex + deleteCount; i < len; i++) {
      let fromIndex = i;
      // The target position to be moved
      let toIndex = i - (deleteCount - addElements.length);
      if (fromIndex in array) {
        array[toIndex] = array[fromIndex];
      } else {
        deletearray[toIndex]; }}// Pay attention! Here we're moving the next element forward, so we're reducing the size of the array, so we need to remove the redundant elements
    // The current length is len + addElements - deleteCount
    for (let i = len - 1; i >= len + addElements.length - deleteCount; i --) {
      deletearray[i]; }}};Copy the code

When the number of added elements is greater than the number of deleted elements, as shown in the figure:

const movePostElements = (array, startIndex, len, deleteCount, addElements) = > {
  / /...
  if(deleteCount < addElements.length) {
    // If the number of deleted elements is smaller than the number of added elements, then the following elements are moved back
    // Why do you want to iterate backwards? What problems will arise in the future?
    for (let i = len - 1; i >= startIndex + deleteCount; i--) {
      let fromIndex = i;
      // The target position to be moved
      let toIndex = i + (addElements.length - deleteCount);
      if (fromIndex in array) {
        array[toIndex] = array[fromIndex];
      } else {
        deletearray[toIndex]; }}}};Copy the code

Optimization 1: boundary case of parameter

When the user sends an invalid startIndex and deleteCount or negative index, we need to do something special.

const computeStartIndex = (startIndex, len) = > {
  // Handle negative indexes
  if (startIndex < 0) {
    return startIndex + len > 0 ? startIndex + len: 0;
  } 
  return startIndex >= len ? len: startIndex;
}

const computeDeleteCount = (startIndex, len, deleteCount, argumentsLen) = > {
  // Delete number is not passed, default delete startIndex and all after
  if (argumentsLen === 1) 
    return len - startIndex;
  // The number of deletions is too small
  if (deleteCount < 0) 
    return 0;
  // The number of deletes is too large
  if (deleteCount > len - startIndex) 
    return len - startIndex;
  return deleteCount;
}

Array.prototype.splice = function (startIndex, deleteCount, ... addElements) {
  / /,...
  let deleteArr = new Array(deleteCount);
  
  // Clean the following parameters
  startIndex = computeStartIndex(startIndex, len);
  deleteCount = computeDeleteCount(startIndex, len, deleteCount, argumentsLen);
   
  // Copy the deleted element
  sliceDeleteElements(array, startIndex, deleteCount, deleteArr);
  / /...
}
Copy the code

Optimization two: Arrays are sealed objects or frozen objects

What is a sealed object?

Sealed objects are non-extensible objects, and the [[signals]] property of an existing member is set to false, which means that methods and properties cannot be added or removed. But attribute values can be modified.

What is a frozen object?

Frozen objects are the most stringent tamper-proof level, and in addition to the restrictions on containing sealed objects, attribute values cannot be modified.

Now, let’s rule out both.

// Determine sealed objects and frozen objects
if (Object.isSealed(array) && deleteCount ! == addElements.length) {throw new TypeError('the object is a sealed object! ')}else if(Object.isFrozen(array) && (deleteCount > 0 || addElements.length > 0)) {
  throw new TypeError('the object is a frozen object! ')}Copy the code

Here’s a complete splice:

const sliceDeleteElements = (array, startIndex, deleteCount, deleteArr) = > {
  for (let i = 0; i < deleteCount; i++) {
    let index = startIndex + i;
    if (index in array) {
      letcurrent = array[index]; deleteArr[i] = current; }}};const movePostElements = (array, startIndex, len, deleteCount, addElements) = > {
  // If the number of added elements is equal to the number of deleted elements, it is equivalent to the replacement of the element, the length of the array remains the same, and the elements after the deleted element do not need to be moved
  if (deleteCount === addElements.length) return;
  // If the number of added elements is not equal to the number of deleted elements, then the next element is moved
  else if(deleteCount > addElements.length) {
    // If more elements are deleted than added, then the following elements will move forward
    // A total of len - startIndex - deleteCount elements need to be moved
    for (let i = startIndex + deleteCount; i < len; i++) {
      let fromIndex = i;
      // The target position to be moved
      let toIndex = i - (deleteCount - addElements.length);
      if (fromIndex in array) {
        array[toIndex] = array[fromIndex];
      } else {
        deletearray[toIndex]; }}// Pay attention! Here we're moving the next element forward, so we're reducing the size of the array, so we need to remove the redundant elements
    // The current length is len + addElements - deleteCount
    for (let i = len - 1; i >= len + addElements.length - deleteCount; i --) {
      deletearray[i]; }}else if(deleteCount < addElements.length) {
    // If the number of deleted elements is smaller than the number of added elements, then the following elements are moved back
    // Why do you want to iterate backwards? What problems will arise in the future?
    for (let i = len - 1; i >= startIndex + deleteCount; i--) {
      let fromIndex = i;
      // The target position to be moved
      let toIndex = i + (addElements.length - deleteCount);
      if (fromIndex in array) {
        array[toIndex] = array[fromIndex];
      } else {
        deletearray[toIndex]; }}}};const computeStartIndex = (startIndex, len) = > {
  // Handle negative indexes
  if (startIndex < 0) {
    return startIndex + len > 0 ? startIndex + len: 0;
  } 
  return startIndex >= len ? len: startIndex;
}

const computeDeleteCount = (startIndex, len, deleteCount, argumentsLen) = > {
  // Delete number is not passed, default delete startIndex and all after
  if (argumentsLen === 1) 
    return len - startIndex;
  // The number of deletions is too small
  if (deleteCount < 0) 
    return 0;
  // The number of deletes is too large
  if (deleteCount > len - startIndex) 
    return len - startIndex;
  return deleteCount;
}

Array.prototype.splice = function(startIndex, deleteCount, ... addElements)  {
  let argumentsLen = arguments.length;
  let array = Object(this);
  let len = array.length >>> 0;
  let deleteArr = new Array(deleteCount);

  startIndex = computeStartIndex(startIndex, len);
  deleteCount = computeDeleteCount(startIndex, len, deleteCount, argumentsLen);

  // Determine sealed objects and frozen objects
  if (Object.isSealed(array) && deleteCount ! == addElements.length) {throw new TypeError('the object is a sealed object! ')}else if(Object.isFrozen(array) && (deleteCount > 0 || addElements.length > 0)) {
    throw new TypeError('the object is a frozen object! ')}// Copy the deleted element
  sliceDeleteElements(array, startIndex, deleteCount, deleteArr);
  // Move the element after the deleted element
  movePostElements(array, startIndex, len, deleteCount, addElements);

  // Insert the new element
  for (let i = 0; i < addElements.length; i++) {
    array[startIndex + i] = addElements[i];
  }

  array.length = len - deleteCount + addElements.length;

  return deleteArr;
}
Copy the code

The above code is personally tested against all the test cases in the MDN documentation.

Related test code please go to: Portal

Finally give you the V8 source code, for you to check: V8 array splice source code line 660

Can we implement the array sort method?

It is estimated that we are not unfamiliar with the JS array sort method, before it is used to do a detailed summary. So, how does it work on the inside? If we can get into its interior to have a look and understand the design behind it, our thinking and literacy will be improved.

The SORT method is a relatively advanced algorithm in V8 compared to other methods, with repeated optimizations for many boundary cases, but we won’t go directly into the source code here. We will come according to the source code idea, implement a sorting algorithm with the same engine performance, and step by step to unravel the mystery.

Analysis of V8 engine

First of all, let’s sort out the idea of sorting the source code:

Let the number of elements to sort be n:

When n <= 10, adoptInsertion sort
When n is greater than 10, useThree-way quicksort
- 10 < n <= 1000, using the median as the sentinel element
- If n > 1000, take one element every 200 to 215 elements, put it in a new array, sort it, find the number in the middle, and use that as the median

Before we do anything, I think we need to find out why we’re doing this.

First, why use insertion sort when the number of elements is small?

While insertion sort is theoretically an O(n^2) algorithm, quicksort is an O(nlogn) level algorithm. But remember, this is just a theoretical estimate, but in practice both algorithms have a coefficient in front of them, and as n is small enough, the advantage of quicksort nlogn is going to get smaller and smaller, and if the coefficient in front of insertion O(n^2) is small enough, then it’s going to outpace quicksort. As a matter of fact, insertion sort is optimized for sorting small data sets with superior performance, even exceeding quicksort in many cases.

Therefore, for small amounts of data, applying insertion sort is a very good choice.

Second, why go to so much effort to select the sentry element?

Because the performance bottleneck of quicksort is the depth of recursion, the worst case is that every time the sentinel is the smallest or the largest element, then partition(on one side of the elements less than the sentinel, on the other side of the elements greater than the sentinel), one side will be empty. The number of levels of recursion is n, and the complexity of each level is O(n), so the quicksort is reduced to O(n^2).

This is something to be avoided! What if to avoid?

The sentinel element is placed in the middle of the array as far as possible, with the maximum and minimum cases as few as possible. At this point, you can understand all the optimizations in V8.

Next, let’s step by step implement such an official sorting algorithm.

Insertion sort and optimization

The initial insertion sort might read something like this:

const insertSort = (arr, start = 0, end) = > {
  end = end || arr.length;
  for(let i = start; i < end; i++) {
    let j;
    for(j = i; j > start && arr[j - 1] > arr[j]; j --) {
      let temp = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = temp; }}return;
}
Copy the code

It seems that sorting can be done correctly, but in fact, swapping elements will cost a considerable amount of performance. We can completely complete this by overwriting variables, as shown in the figure:

The optimized code is as follows:

const insertSort = (arr, start = 0, end) = > {
  end = end || arr.length;
  for(let i = start; i < end; i++) {
    let e = arr[i];
    let j;
    for(j = i; j > start && arr[j - 1] > e; j --)
      arr[j] = arr[j-1];
    arr[j] = e;
  }
  return;
}
Copy the code

Next, enter the sort method formally.

Look for the Sentry element

The skeleton of sort is as follows:

Array.prototype.sort = (comparefn) = > {
  let array = Object(this);
  let length = array.length >>> 0;
  return InnerArraySort(array, length, comparefn);
}

const InnerArraySort = (array, length, comparefn) = > {
  // The comparison function was not passed
  if (Object.prototype.toString.call(callbackfn) ! = ="[object Function]") {
    comparefn = function (x, y) {
      if (x === y) return 0;
      x = x.toString();
      y = y.toString();
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
  }
  const insertSort = () = > {
    / /...
  }
  const getThirdIndex = (a, from, to) = > {
    // Look for the sentinel element when the number of elements is greater than 1000
  }
  const quickSort = (a, from, to) = > {
    // Sentinel position
    let thirdIndex = 0;
    while(true) {
      if(to - from< =10) {
        insertSort(a, from, to);
        return;
      }
      if(to - from > 1000) {
        thirdIndex = getThirdIndex(a, from , to);
      }else {
        // If the value is less than 1000, take the midpoint
        thirdIndex = from + ((to - from) > >2); }}// Let's start quickqueuing}}Copy the code

Let’s get the sentry position code to implement:

const getThirdIndex = (a, from, to) = > {
  let tmpArr = [];
  // The increment is between 200 and 215, because any positive number and 15 will not exceed 15, which of course is greater than 0
  let increment = 200 + ((to - from) & 15);
  let j = 0;
  from+ =1;
  to -= 1;
  for (let i = from; i < to; i += increment) {
    tmpArr[j] = [i, a[i]];
    j++;
  }
  // Sort the temporary array with the middle value, making sure the sentry is close to the average position
  tmpArr.sort(function(a, b) {
    return comparefn(a[1], b[1]);
  });
  let thirdIndex = tmpArr[tmpArr.length >> 1] [0];
  return thirdIndex;
}
Copy the code

To complete the fast line

Next, let’s complete the specific code for quicktypesetting:

const _sort = (a, b, c) = > {
  let arr = [a, b, c];
  insertSort(arr, 0.3);
  return arr;
}

const quickSort = (a, from, to) = > {
  / /...
  // Above we get thirdIndex
  // Now we have three elements, from, thirdIndex, to
  // To make sure again that thirdIndex is not the best value, sort the three values
  [a[from], a[thirdIndex], a[to - 1]] = _sort(a[from], a[thirdIndex], a[to - 1]);
  // Now officially use thirdIndex as a sentinel
  let pivot = a[thirdIndex];
  // Enter express platoon
  let lowEnd = from + 1;
  let highStart = to - 1;
  ThirdIndex is now officially a sentinel, and lowEnd is exchanged with thirdIndex
  let pivot = a[thirdIndex];
  a[thirdIndex] = a[lowEnd];
  a[lowEnd] = pivot;
  
  // [lowEnd, I] is equal to pivot
  // The elements of [I, highStart] need to be processed
  for(let i = lowEnd + 1; i < highStart; i++) {
    let element = a[i];
    let order = comparefn(element, pivot);
    if (order < 0) {
      a[i] = a[lowEnd];
      a[lowEnd] = element;
      lowEnd++;
    } else if(order > 0) {
      do{
        highStart--;
        if(highStart === i) break;
        order = comparefn(a[highStart], pivot);
      }while(order > 0)
      // Now a[highStart] <= pivot
      // a[i] > pivot
      // The two are exchanged
      a[i] = a[highStart];
      a[highStart] = element;
      if(order < 0) {
        // A [I] and a[lowEnd] exchangeelement = a[i]; a[i] = a[lowEnd]; a[lowEnd] = element; lowEnd++; }}}// Always slice large intervals
  if (lowEnd - from > to - highStart) {
    // Continue to shard lowEnd ~ from this interval
    to = lowEnd;
    // Treat the cells separately
    quickSort(a, highStart, to);
  } else if(lowEnd - from <= to - highStart) {
    from = highStart;
    quickSort(a, from, lowEnd); }}Copy the code

The test results

The test results are as follows:

10,000 pieces of data:

100,000 pieces of data:

One million pieces of data:

10 million pieces of data:

The results are for your reference only, as some of the details may be implemented differently by different versions of Node. My current version is V10.15.

It can be seen from the results that the current version of Node is not good enough to process the data with a high degree of order, and the sorting we just implemented can effectively avoid the disadvantages of fast sorting in this scenario by repeatedly determining the position of the sentinel.

Finally give you the complete version of sort code:

const sort = (arr, comparefn) = > {
  let array = Object(arr);
  let length = array.length >>> 0;
  return InnerArraySort(array, length, comparefn);
}

const InnerArraySort = (array, length, comparefn) = > {
  // The comparison function was not passed
  if (Object.prototype.toString.call(comparefn) ! = ="[object Function]") {
    comparefn = function (x, y) {
      if (x === y) return 0;
      x = x.toString();
      y = y.toString();
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
  }
  const insertSort = (arr, start = 0, end) = > {
    end = end || arr.length;
    for (let i = start; i < end; i++) {
      let e = arr[i];
      let j;
      for (j = i; j > start && comparefn(arr[j - 1], e) > 0; j--)
        arr[j] = arr[j - 1];
      arr[j] = e;
    }
    return;
  }
  const getThirdIndex = (a, from, to) = > {
    let tmpArr = [];
    // The increment is between 200 and 215, because any positive number and 15 will not exceed 15, which of course is greater than 0
    let increment = 200 + ((to - from) & 15);
    let j = 0;
    from+ =1;
    to -= 1;
    for (let i = from; i < to; i += increment) {
      tmpArr[j] = [i, a[i]];
      j++;
    }
    // Sort the temporary array with the middle value, making sure the sentry is close to the average position
    tmpArr.sort(function (a, b) {
      return comparefn(a[1], b[1]);
    });
    let thirdIndex = tmpArr[tmpArr.length >> 1] [0];
    return thirdIndex;
  };

  const _sort = (a, b, c) = > {
    let arr = [];
    arr.push(a, b, c);
    insertSort(arr, 0.3);
    return arr;
  }

  const quickSort = (a, from, to) = > {
    // Sentinel position
    let thirdIndex = 0;
    while (true) {
      if (to - from< =10) {
        insertSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        thirdIndex = getThirdIndex(a, from, to);
      } else {
        // If the value is less than 1000, take the midpoint
        thirdIndex = from + ((to - from) > >2);
      }
      let tmpArr = _sort(a[from], a[thirdIndex], a[to - 1]);
      a[from] = tmpArr[0]; a[thirdIndex] = tmpArr[1]; a[to - 1] = tmpArr[2];
      // Now officially use thirdIndex as a sentinel
      let pivot = a[thirdIndex];
      [a[from], a[thirdIndex]] = [a[thirdIndex], a[from]].// Enter express platoon
      let lowEnd = from + 1;
      let highStart = to - 1;
      a[thirdIndex] = a[lowEnd];
      a[lowEnd] = pivot;
      // [lowEnd, I] is equal to pivot
      // The elements of [I, highStart] need to be processed
      for (let i = lowEnd + 1; i < highStart; i++) {
        let element = a[i];
        let order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[lowEnd];
          a[lowEnd] = element;
          lowEnd++;
        } else if (order > 0) {
          do{
            highStart--;
            if (highStart === i) break;
            order = comparefn(a[highStart], pivot);
          }while (order > 0);// Now a[highStart] <= pivot
          // a[i] > pivot
          // The two are exchanged
          a[i] = a[highStart];
          a[highStart] = element;
          if (order < 0) {
            // A [I] and a[lowEnd] exchangeelement = a[i]; a[i] = a[lowEnd]; a[lowEnd] = element; lowEnd++; }}}// Always slice large intervals
      if (lowEnd - from > to - highStart) {
        // Treat the cells separately
        quickSort(a, highStart, to);
        // Continue to shard lowEnd ~ from this interval
        to = lowEnd;
      } else if (lowEnd - from <= to - highStart) {
        quickSort(a, from, lowEnd);
        from = highStart;
      }
    }
  }
  quickSort(array, 0, length);
}
Copy the code

Reference links:

V8 sort source code (click on line 997)

Hu feather sorting source topic

Is it possible to simulate a new effect?

New does three things when it is called:

Make instances accessible to private properties
Gives the instance access to properties on the stereotype chain where the constructor. Prototype resides
If the constructor returns a result that is not a reference data type

function newOperator(ctor, ... args) {
    if(typeofctor ! = ='function') {throw 'newOperator function the first param must be a function';
    }
    let obj = Object.create(ctor.prototype);
    let res = ctor.apply(obj, args);
    
    let isObject = typeof res === 'object'&& res ! = =null;
    let isFunction = typoof res === 'function';
    return isObect || isFunction ? res : obj;
};
Copy the code

Is it possible to simulate a bind effect?

Before we can implement bind, we first need to know what it does.

For normal functions, bind this to
For constructors, ensure that the properties on the prototype object of the original function are not lost

Function.prototype.bind = function (context, ... args) {
    // Exception handling
    if (typeof this! = ="function") {
      throw new Error("Function.prototype.bind - what is trying to be bound is not callable");
    }
    // Save the value of this, which represents the function that calls bind
    var self = this;
    var fNOP = function () {};

    var fbound = function () {
        self.apply(this instanceof self ? 
            this : 
            context, args.concat(Array.prototype.slice.call(arguments)));
    }

    fNOP.prototype = this.prototype;
    fbound.prototype = new fNOP();

    return fbound;
}
Copy the code

You can also use object.create to handle prototypes this way:

Function.prototype.bind = function (context, ... args) {
    if (typeof this! = ="function") {
      throw new Error("Function.prototype.bind - what is trying to be bound is not callable");
    }

    var self = this;

    var fbound = function () {
        self.apply(this instanceof self ? 
            this : 
            context, args.concat(Array.prototype.slice.call(arguments)));
    }

    fbound.prototype = Object.create(self.prototype);

    return fbound;
}
Copy the code

Can I implement a Call /apply function?

Quoted from hu plume big guy code, can be said to be more complete.

Function.prototype.call = function (context) {
    let context = context || window;
    let fn = Symbol('fn');
    context.fn = this;

    let args = [];
    for(let i = 1, len = arguments.length; i < len; i++) {
        args.push('arguments[' + i + '] ');
    }

    let result = eval('context.fn(' + args +') ');

    delete context.fn
    return result;
}
Copy the code

But I think the ES6 syntax is a little more concise:

Function.prototype.call = function (context, ... args) {
  let context = context || window;
  let fn = Symbol('fn');
  context.fn = this;

  let result = eval('context.fn(... args)');

  delete context.fn
  return result;
}
Copy the code

Similarly, there is a corresponding implementation for apply:

Function.prototype.apply = function (context, args) {
  let context = context || window;
  context.fn = this;
  let result = eval('context.fn(... args)');

  delete context.fn
  return result;
}
Copy the code

What is your understanding of this in JS?

In fact, this in JS is a very simple thing, just need to understand its execution rules OK.

I don’t want to display too many code examples like other blogs, but it is not easy to understand.

Call /apply/bind can be explicitly bound, which I won’t mention here.

The main scenarios for these fields implicit binding are discussed:

Global context
Call function directly
Object. Method
DOM event binding (special)
New constructor binding
Arrow function

1. Global context

The global context defaults this to window, and strict mode to undefined.

2. Call the function directly

Such as:

let obj = {
  a: function() {
    console.log(this); }}let func = obj.a;
func();
Copy the code

In this case it’s a direct call. This is equivalent to the global context case.

3. Object. Method call in form

Again, if I write it like this:

obj.a();
Copy the code

So that’s the case of object, method, this refers to this object

4. DOM event binding

By default, this in onClick and addEventerListener points to the element bound to the event.

IE is a bit weird. It uses attachEvent, where this points to window by default.

5. New + constructor

This in the constructor refers to the instance object.

6. Arrow function?

The arrow function does not have this and therefore cannot be bound. The “this” will point to the current nearest non-arrow function. If not found, it will be window(undefined in strict mode). Such as:

let obj = {
  a: function() {
    let do = () = > {
      console.log(this);
    }
    do(a); } } obj.a();// Find the nearest non-arrow function a. A is now bound to obj, so this in the arrow function is obj
Copy the code

Priority: New > Call, Apply, bind > object. Method > Direct call.

What are the means of shallow copy in JS?

Important: What is copying?

First, let’s get a sense of what copying is.

let arr = [1.2.3];
let newArr = arr;
newArr[0] = 100;

console.log(arr);/ / [100, 2, 3]
Copy the code

This is the case of direct assignment, without any copying involved. When you change newArr, since it’s the same reference, the value arr points to also changes.

Now make a shallow copy:

let arr = [1.2.3];
let newArr = arr.slice();
newArr[0] = 100;

console.log(arr);/ / [1, 2, 3]
Copy the code

When you modify newArr, the arR value does not change. What’s the reason? Because newArr is a shallow copy of arR, newArr and ARR now refer to different Spaces.

This is the shallow copy!

But that brings up a potential problem:

let arr = [1.2, {val: 4}];
let newArr = arr.slice();
newArr[2].val = 1000;

console.log(arr);//[ 1, 2, { val: 1000 } ]
Copy the code

Yi! Isn’t it already a reference to the same space? When newArr changes the val value of the second element, arr also changes.

This is where shallow copies are limited. It can only copy one level of objects. If there is nesting of objects, then the shallow copy will do nothing. Fortunately, deep copy is designed to solve this problem. It solves the infinite object nesting problem and makes a complete copy possible. Of course, this is the focus of our next post. Just to give you a basic idea.

Next, let’s explore how many ways to implement shallow copy in JS.

1. Implement it manually

const shallowClone = (target) = > {
  if (typeof target === 'object'&& target ! = =null) {
    const cloneTarget = Array.isArray(target) ? [] : {};for (let prop in target) {
      if(target.hasOwnProperty(prop)) { cloneTarget[prop] = target[prop]; }}return cloneTarget;
  } else {
    returntarget; }}Copy the code

2. Object.assign

Note, however, that object.assgin () copies references to the properties of the Object, not the Object itself.

let obj = { name: 'sy'.age: 18 };
const obj2 = Object.assign({}, obj, {name: 'sss'});
console.log(obj2);//{ name: 'sss', age: 18 }
Copy the code

3. Concat shallow copy array

let arr = [1.2.3];
let newArr = arr.concat();
newArr[1] = 100;
console.log(arr);//[1, 2, 3]
Copy the code

4. Slice a shallow copy

The beginning of the example is not to say this!

5…. Expansion operator

let arr = [1.2.3];
let newArr = [...arr];// The same effect as arr.slice()
Copy the code

Is it possible to write a complete deep copy?

The last post explained what a deep copy is, now let’s implement a full and professional deep copy.

1. Simple version and questions

JSON.parse(JSON.stringify());
Copy the code

This API is expected to cover most application scenarios, and yes, it’s the first thing that comes to mind when it comes to deep copy. But in fact, for some strict scenarios, this approach has huge craters. The questions are as follows:

Unable to resolveA circular referenceThe problem. Here’s an example:

const a = {val:2};
a.target = a;
Copy the code

Copying A will overflow the system stack because of the infinite recursion.

I can’t copy itSpecial object, such as RegExp, Date, Set, Map, etc.

Unable to copyfunction(highlight).

So let’s write a new deep copy of the API. The simple version is as follows:

const deepClone = (target) = > {
  if (typeof target === 'object'&& target ! = =null) {
    const cloneTarget = Array.isArray(target) ? [] : {};for (let prop in target) {
      if(target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop]); }}return cloneTarget;
  } else {
    returntarget; }}Copy the code

For now, let’s take the three issues we just discovered and take steps to refine and optimize our deep-copy code.

2. Resolve circular references

Here’s the question:

let obj = {val : 100};
obj.target = obj;

deepClone(obj);RangeError: Maximum call stack size exceeded
Copy the code

This is circular reference. How can we solve this problem?

Create a Map. Record the object that has been copied, and if it has been copied, return its line.

const isObject = (target) = > (typeof target === 'object' || typeof target === 'function') && target ! = =null;

const deepClone = (target, map = new Map(a)) = > { 
  if(map.get(target))  
    return target; 
 
 
  if (isObject(target)) { 
    map.set(target, true); 
    const cloneTarget = Array.isArray(target) ? [] : {};for (let prop in target) { 
      if(target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop],map); }}return cloneTarget; 
  } else { 
    returntarget; }}Copy the code

Here’s a try:

const a = {val:2};
a.target = a;
let newA = deepClone(a);
console.log(newA)//{ val: 2, target: { val: 2, target: [Circular] } }
Copy the code

There seems to be no problem, and the copy is complete. One potential pitfall, however, is that the key on the map has a strong reference to the map, which can be quite dangerous. To help you understand, let me explain the concept of weak references as the opposite:

In computer programming, weak references are the opposite of strong references,

A reference that cannot be assured that the object it references will not be reclaimed by the garbage collector. An object that is referenced only by weak references is considered inaccessible (or weakly accessible) and may therefore be reclaimed at any time. — Baidu Encyclopedia

A weak reference can be reclaimed at any time, while a strong reference cannot be reclaimed as long as the strong reference is present. In the example above, map and A are always strong references, and the memory occupied by A will not be freed until the end of the program.

How to solve this problem?

Simply let the map key and map form weak references. ES6 provides us with such a data structure called a WeakMap, which is a special Map in which the keys are weakly referenced. The key must be an object, and the value can be arbitrary.

With a little reworking:

const deepClone = (target, map = new WeakMap(a)) = > {
  / /...
}
Copy the code

3. Copy special objects

You can continue traversal

For specific objects, we use the following methods to identify:

Object.prototype.toString.call(obj);
Copy the code

Let’s comb through the results for traversable objects:

["object Map"]
["object Set"]
["object Array"]
["object Object"]
["object Arguments"]
Copy the code

Well, based on these different strings, we can successfully identify these objects.

const getType = Object.prototype.toString.call(obj);

const canTraverse = {
  '[object Map]': true.'[object Set]': true.'[object Array]': true.'[object Object]': true.'[object Arguments]': true};const deepClone = (target, map = new Map(a)) = > {
  if(! isObject(target))return target;
  let type = getType(target);
  let cloneTarget;
  if(! canTraverse[type]) {// Handle objects that cannot be traversed
    return;
  }else {
    // This wave of operations is critical to ensure that the object's prototype is not lost!
    let ctor = target.prototype;
    cloneTarget = new ctor();
  }

  if(map.get(target)) 
    return target;
  map.put(target, true);

  if(type === mapTag) {
    / / the Map processing
    target.forEach((item, key) = >{ cloneTarget.set(deepClone(key), deepClone(item)); })}if(type === setTag) {
    / / handle the Set
    target.forEach(item= >{ target.add(deepClone(item)); })}// Handle arrays and objects
  for (let prop in target) {
    if(target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop]); }}return cloneTarget;
}
Copy the code

An object that is not traversable

const boolTag = '[object Boolean]';
const numberTag = '[object Number]';
const stringTag = '[object String]';
const dateTag = '[object Date]';
const errorTag = '[object Error]';
const regexpTag = '[object RegExp]';
const funcTag = '[object Function]';
Copy the code

For non-traversable objects, different objects have different treatment.

const handleRegExp = (target) = > {
  const { source, flags } = target;
  return new target.constructor(source, flags);
}

const handleFunc = (target) = > {
  // The important part later
}

const handleNotTraverse = (target, tag) = > {
  const Ctor = targe.constructor;
  switch(tag) {
    case boolTag:
    case numberTag:
    case stringTag:
    case errorTag: 
    case dateTag:
      return new Ctor(target);
    case regexpTag:
      return handleRegExp(target);
    case funcTag:
      return handleFunc(target);
    default:
      return newCtor(target); }}Copy the code

4. Copy the function

A function is also an object, but it’s so special that we’ll break it down in its own right.

When it comes to functions, there are two kinds of functions in JS, one is the ordinary function, the other is the arrow function. Whereas every normal Function is an instance of Function, the arrow Function is not an instance of any class and is a different reference every time it is called. So we just have to deal with the normal function, the arrow function just returns itself.

So how do you distinguish between the two?

The answer is: use prototypes. There is no prototype for arrow functions.

The code is as follows:

const handleFunc = (func) = > {
  // The arrow function returns itself directly
  if(! func.prototype)return func;
  const bodyReg = / (? <={)(.|\n)+(? =})/m;
  const paramReg = / (? < = \ () + (? =\)\s+{)/;
  const funcString = func.toString();
  // Match the function parameters and the function body respectively
  const param = paramReg.exec(funcString);
  const body = bodyReg.exec(funcString);
  if(! body)return null;
  if (param) {
    const paramArr = param[0].split(', ');
    return new Function(... paramArr, body[0]);
  } else {
    return new Function(body[0]); }}Copy the code

By now, our deep copy implementation is fairly complete. But in the process of testing, I also found a small bug.

5. Small bugs

As follows:

const target = new Boolean(false);
const Ctor = target.constructor;
new Ctor(target); // The result is Boolean {true} not false.
Copy the code

For such a bug, the simplest modification we can make to the Boolean copy is to call valueOf: new target.constructor(target.valueof ()).

In fact, this is not recommended. In ES6, the new Symbol type cannot be directly new, but only via new Object(SymbelType), because the syntax of new primitive type () is not recommended.

So let’s unify:

const handleNotTraverse = (target, tag) = > {
  const Ctor = targe.constructor;
  switch(tag) {
    case boolTag:
      return new Object(Boolean.prototype.valueOf.call(target));
    case numberTag:
      return new Object(Number.prototype.valueOf.call(target));
    case stringTag:
      return new Object(String.prototype.valueOf.call(target));
    case errorTag: 
    case dateTag:
      return new Ctor(target);
    case regexpTag:
      return handleRegExp(target);
    case funcTag:
      return handleFunc(target);
    default:
      return newCtor(target); }}Copy the code

6. Complete code display

OK! It’s time to release the full deep copy:

const getType = obj= > Object.prototype.toString.call(obj);

const isObject = (target) = > (typeof target === 'object' || typeof target === 'function') && target ! = =null;

const canTraverse = {
  '[object Map]': true.'[object Set]': true.'[object Array]': true.'[object Object]': true.'[object Arguments]': true};const mapTag = '[object Map]';
const setTag = '[object Set]';
const boolTag = '[object Boolean]';
const numberTag = '[object Number]';
const stringTag = '[object String]';
const symbolTag = '[object Symbol]';
const dateTag = '[object Date]';
const errorTag = '[object Error]';
const regexpTag = '[object RegExp]';
const funcTag = '[object Function]';

const handleRegExp = (target) = > {
  const { source, flags } = target;
  return new target.constructor(source, flags);
}

const handleFunc = (func) = > {
  // The arrow function returns itself directly
  if(! func.prototype)return func;
  const bodyReg = / (? <={)(.|\n)+(? =})/m;
  const paramReg = / (? < = \ () + (? =\)\s+{)/;
  const funcString = func.toString();
  // Match the function parameters and the function body respectively
  const param = paramReg.exec(funcString);
  const body = bodyReg.exec(funcString);
  if(! body)return null;
  if (param) {
    const paramArr = param[0].split(', ');
    return new Function(... paramArr, body[0]);
  } else {
    return new Function(body[0]); }}const handleNotTraverse = (target, tag) = > {
  const Ctor = target.constructor;
  switch(tag) {
    case boolTag:
      return new Object(Boolean.prototype.valueOf.call(target));
    case numberTag:
      return new Object(Number.prototype.valueOf.call(target));
    case stringTag:
      return new Object(String.prototype.valueOf.call(target));
    case symbolTag:
      return new Object(Symbol.prototype.valueOf.call(target));
    case errorTag: 
    case dateTag:
      return new Ctor(target);
    case regexpTag:
      return handleRegExp(target);
    case funcTag:
      return handleFunc(target);
    default:
      return newCtor(target); }}const deepClone = (target, map = new WeakMap(a)) = > {
  if(! isObject(target))return target;
  let type = getType(target);
  let cloneTarget;
  if(! canTraverse[type]) {// Handle objects that cannot be traversed
    return handleNotTraverse(target, type);
  }else {
    // This wave of operations is critical to ensure that the object's prototype is not lost!
    let ctor = target.constructor;
    cloneTarget = new ctor();
  }

  if(map.get(target)) 
    return target;
  map.set(target, true);

  if(type === mapTag) {
    / / the Map processing
    target.forEach((item, key) = >{ cloneTarget.set(deepClone(key, map), deepClone(item, map)); })}if(type === setTag) {
    / / handle the Set
    target.forEach(item= >{ cloneTarget.add(deepClone(item, map)); })}// Handle arrays and objects
  for (let prop in target) {
    if(target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop], map); }}return cloneTarget;
}
Copy the code

(recommended intensive reading) native JS soul of the question (middle), check whether they are really familiar with JavaScript?

Why is arguments not an array? How do I convert to an array?

1. Array.prototype.slice.call()

2. Array.from()

3. ES6 expansion operator

4. Use the concat + the apply

Does return work in forEach? How do I break a forEach loop?

JS determines whether an array contains a value

Method 1: array.indexOf

Method 2: array.includes(searcElement[,fromIndex])

Array. find(callback[,thisArg])

Array.findeindex (callback[,thisArg])

Part 10: JS array flat– flat

1. Call the flat method in ES6

2. replace + split

3. replace + JSON.parse

4. Ordinary recursion

5. Use reduce function to iterate

6: Extension operators

Part 11: Higher order functions of JS array — Basic

1. What is a higher-order function

2. Higher-order functions in arrays

1.map

2. reduce

3. filter

4. sort

Can we implement the array map method?

Is it possible to implement the Array Reduce method?

Can we implement array push and pop methods?

Can we implement the array filter method?

Can we implement the array splice method?

The preliminary implementation

Optimization 1: boundary case of parameter

Optimization two: Arrays are sealed objects or frozen objects

Can we implement the array sort method?

Analysis of V8 engine

Insertion sort and optimization

Look for the Sentry element

To complete the fast line

The test results

Is it possible to simulate a new effect?

Is it possible to simulate a bind effect?

Can I implement a Call /apply function?

What is your understanding of this in JS?

1. Global context

2. Call the function directly

3. Object. Method call in form

4. DOM event binding

5. New + constructor

6. Arrow function?

What are the means of shallow copy in JS?

Important: What is copying?

1. Implement it manually

2. Object.assign

3. Concat shallow copy array

4. Slice a shallow copy

5…. Expansion operator

Is it possible to write a complete deep copy?

1. Simple version and questions

2. Resolve circular references

3. Copy special objects

You can continue traversal

An object that is not traversable

4. Copy the function

5. Small bugs

6. Complete code display

Related Posts

Rust implements the sum of two numbers

MAC installation NVM

Vue3– Setup entry function, Reactive reactive function, ref function