A lot of anxiety is caused by thinking too much

concise

  1. JS only supports shallow replication at the language level, and deep replication needs to be implemented manually
  2. Instanceof determines whether a and A are related by blood
  3. The extension operator defines new attributes directly in the replica
  4. Object.assign()throughThe way the value is assignedTo process the corresponding properties in the copy
  5. The assignment operation calls itself or inheritssetterFunction, while defining properties are not
  6. __proto__Is made up ofObjectThe class passes through agetterAnd asetterImplementation of the
  7. '__proto__' in {} // true

    '__proto__' in { __proto__: null }
  8. Deep copy of data through JSON only deals with what JSON recognizeskeyandvalue
  9. The deep copy stack burst problem is solved by cyclic processing
  10. Traversing the tree structure,

    1. Stack for depth-first non-recursive traversal (stack) implementation

    2. Breadth-first non-recursive traversal (sequential traversal) using queues (queue)

The article summary

  1. Shallow replication VS deep replication
  2. On shallow replication
  • Extended operator (.) copies objects and arrays
  • Object.assign()
  • Object.getOwnPropertyDescriptors()andObject.defineProperties()
  1. Deep copy
  2. Nuggets article

1. Shallow replication VS deep replication

There are two processing modes for replication of JS reference type data (complex data).

  • Shallow Copying: Copying only objects or array typesAt the topVariable, and the value of the variable and the value of the original data is the same copy
  • Deep Copying: Copies all key-values of the original data, traversing a complete data tree (the root being the value to be copied) and Copying all nodes.

JS only supports shallow replication at the language level, and deep replication needs to be implemented manually

2. Shallow replication

In JS, there are several built-in properties that naturally support shallow data replication, but each property has its own applicable conditions and scope.

2.1 Extended Operators (.) copies objects and arrays

constcopyOfObject = {... originalObject};const copyOfArray = [...originalArray];
Copy the code

Let’s briefly describe the shortcomings and characteristics of the extension operators. Before we begin, let’s make a quick summary:

Deficiencies & characteristics
Extension operators cannot copy normal objectsprototypeattribute
Extension operators cannot be copiedBuilt-in objectstheSpecial attributesThe internal slots)
The extension operator copies only the attributes of the object itself (not inherited)
The extension operator copies only the object’s enumerable properties.
The data properties copied by the extension operator areCan be written(writable) andconfigurable(configurable)

The extension operator cannot copy the Prototype property of a normal object

class MyClass {}

const original = new MyClass();
original instanceof MyClass // true

constcopy = {... original}; copyinstanceof MyClass  //false
Copy the code

A instanceof a is used to determine if the corresponding constructor a exists in the prototype chain of instance A, and if it does, instanceof returns true. Instanceof determines whether A and A are related by blood, rather than just by father and son.

let ar = [];
ar instanceof Array // true
ar instanceof Object // true
Copy the code

We have been introduced to this aspect in the JS article data types those things, you can refer to it yourself.

Also, as an extra bit of nagging, the following statements are equivalent.

obj instanceof SomeClass

SomeClass.prototype.isPrototypeOf(obj)
Copy the code

From the above analysis, if the prototype property of the copied object is set to the same as the original data, we can solve the problem that the extended operator cannot copy object Prototype.

const original = new MyClass();

const copy = {
  __proto__: Object.getPrototypeOf(original), ... original, }; copyinstanceof MyClass //true
Copy the code

It is also possible to make a copy of the copy Object and then modify the __proto__ property of the Object by specifying object.setProtoTypeof ().

Extension operators cannot copy special properties of built-in objects

JS = ECMAScript + DOM + BOM in browser-hosted environment. ECMAScript is the language core, with built-in objects such as Date/RegExp.

For these built-in objects, the extension operator cannot copy their special attributes (which are also called internal slots in the language standard).

let originalReg = new RegExp('789'.'g'); 
letcopyReg = {... originalReg}/ / {}
Copy the code

originalReg, its value is/789/gIs a template for expressing text patterns (that is, string structures), sort of like strings. But by.To access its properties and find that there are many types of the propertyInternal properties 而copyRegFailed to copyoriginalRegInternal properties of.

The extension operator copies only the attributes of the object itself (not inherited)

In the example below, the inheritedProp property of Original does not appear in the copy.

In fact, it all boils down to the fact that an object copied by the extension operator cannot copy __proto__ of the original data. (Prototype chain direction)

const proto = { inheritedProp: 'a' };
const original = {
  __proto__: proto, 
  ownProp: 'b' 
};
constcopy = {... original}; copy.inheritedProp// undefined
copy.ownProp // 'b'
Copy the code

The extension operator copies only the object’s enumerable properties.

Although some properties belong to the object itself, they are not enumerable and cannot be copied.

For example, the length of an array instance is its own property, but not enumerable.

const arr = ['a'.'b'];
arr.length / / 2
({}.hasOwnProperty).call(arr, 'length') // true

constcopy = {... arr};// (A)
({}.hasOwnProperty).call(copy, 'length') // false
Copy the code

This is a rare limitation, because most attributes of an object are enumerable.

If we want to copy a non-enumerable property, we can use it at the same time

  1. Object.getOwnPropertyDescriptors()
  2. Object.defineProperties()

Whether an enumerable Object. GetOwnPropertyDescriptors () is not enumerated attribute can be accessed. And not only can you access values, but you can access getter/setter functions as well as read-only properties.

Extend the default behavior of the operator

When an object is copied using an extension operator, the data attributes copied are writable and configurable.

The data properties of the property

Internal properties explain The default value
Configurable 1. Check whether attributes can be deleted and redefined by delete

2. Check whether its features can be modified

3. Whether it can be changed to an accessor property		 true
Enumerable Whether the property can be returned through a for-in loop true
Writable Whether the value of the property can be modified true
Value Contains the actual value of the property undefined

For example, make the prop property unwritable and unconfigurable with Object.defineProperties().

const original = Object.defineProperties(
  {}, {
    prop: {
      value: 1.writable: false.configurable: false.enumerable: true,}}); original.prop =789; // Assignment failed (writable :false)
  delete original.prop; //删除失败 (configurable: false)
Copy the code

However, if the object is copied via an extension operator, the writable and 64x are reset to true

constcopy = {... original};Object.getOwnPropertyDescriptors(copy)
/* { prop: { value: 1, writable: true, configurable: true, enumerable: true, }, } */
copy.prop = 789; // Assignment succeeded (writable :true)
delete copy.prop; // Deletes successfully (64x: true)
Copy the code

A similar effect is achieved for accessor properties (getters/setters).

2.2 Object.assign()

Object.assign() works like the extension operator.

constcopy1 = {... original};const copy2 = Object.assign({}, original);
Copy the code

Object.assign() is not exactly the extension operator; there are some subtle differences.

  • The extension operator defines new attributes directly in the replica
  • Object.assign()throughThe way the value is assignedTo process the corresponding properties in the copy

Assignment calls itself or an inherited setter function, while defining a property does not.

const original = {['__proto__'] :null}; // (A)
constcopy1 = {... original};//copy1 has its own attribute (__proto__)
Object.keys(copy1) // ['__proto__']

const copy2 = Object.assign({}, original);
// copy2 Prototype is null
Object.getPrototypeOf(copy2)// null
Copy the code

Using the expression as the property name in line A, creates A __proto__ property without calling the inherited setter function. Then, the property copied by object.assign () calls setter functions (set __proto__).

One more thing: __proto__ is implemented by the Object class with a getter and a setter.

class Object {
  get __proto__() {
    return Object.getPrototypeOf(this);
  }
  set __proto__(other) {
    Object.setPrototypeOf(this, other);
  }
  / /...
}
Copy the code

This means that you can create an Object that has no Object. Prototype on the prototype chain by manually configuring __proto__:null for the Object.

In other words, you break the prototype chain of an object by manually configuring __proto__: NULL

'__proto__' in {} // true

'__proto__' in { __proto__: null } //false Manually close the connection
Copy the code

2.3 Object.getOwnPropertyDescriptors()andObject.defineProperties()

JavaScript allows us to create properties through property descriptors.

function copyAllOwnProperties(original) {
  return Object.defineProperties(
    {}, Object.getOwnPropertyDescriptors(original));
}
Copy the code

Two problems with copying objects by extension operators are solved

1. Be able to copy all of your own properties

Resolve that extension operators cannot copy setter/getter functions of the original object

const original = {
  get myGetter() { return 789 },
  set mySetter(x) {}}; copy = copyAllOwnProperties(original); copy.myGetter/ / 789
Copy the code

2. Ability to copy non-enumerated properties

const arr = ['a'.'b'];
arr.length / / 2
({}.hasOwnProperty).call(arr, 'length') // true


const copy = copyAllOwnProperties(arr);
({}.hasOwnProperty).call(copy, 'length') // true

Copy the code

3. Deep copy

Deep copy in JS needs to be implemented manually.

3.1 Deep replication through nested extension operators

const original = {name: '789'.work: {address: 'BeiJing'}};
const copy = {name: original.name, work: {... original.work}}; original.work ! == copy.work// point to a different reference address
Copy the code

When using nested extension operators for deep copy, it is important that the template data is simple and that you know exactly where to use the extension operators. For complex data, this is not so true.

3.2 Deep Data Replication Using JSON

We first convert an ordinary object into a JSON string (stringify), and then parse (parse) the string.

function jsonDeepCopy(original) {
  return JSON.parse(JSON.stringify(original));
}
const original = {name: '789'.work: {address: 'BeiJing'}};
constcopy = jsonDeepCopy(original); original.work ! == copy.work// point to a different reference address
Copy the code

There is an obvious downside to this approach:

Only keys and values recognized by JSON can be processed. Unsupported types are ignored.

jsonDeepCopy({
    // Values of the Symbols type are not supported as keys
    [Symbol('a')]: 'abc'.// Unsupported value
    b: function () {},
    // Unsupported value
    c: undefined,})// Return an empty object
Copy the code

What’s more, JSON does not recognize some new data types and will report errors directly.

jsonDeepCopy({a: 123n}) 
//Uncaught TypeError: Do not know how to serialize a BigInt
Copy the code

3.3 Manual Implementation

Recursive functions implement deep copy

function clone(source) {
    let target = {};
    for(let i in source) {
        if (source.hasOwnProperty(i)) {
            if (typeof source[i] === 'object') {
                target[i] = clone(source[i]); // recursive processing
            } else{ target[i] = source[i]; }}}return target;
}

Copy the code

I’m sure you’re familiar with this code. The implementation logic is

  1. usingfor-inIterate over properties of an object (own properties + inherited properties)
  2. source.hasOwnProperty(i)Determine whether or notThe inheritancetheCan be enumeratedattribute
  3. typeof source[i] === 'object'Determine the type of the value and, if it is an object, recurse

The above code, however, can only be said to be a basic version of deep copy, which still has some bugs.

  • Parameters are not validated
  • Array compatibility is not considered
  • Determine if the object’s logic is not rigorous enough

We simply put the above code to do a simple optimization. (There are many ways to traverse objects, we use Object.entries())

function deepCopy(original) {
  if (Array.isArray(original)) {
     // Handle arrays
    const copy = [];
    for (const [index, value] of original.entries()) {
      copy[index] = deepCopy(value);
    }
    return copy;
  } else if (typeof original === 'object'&& original ! = =null) {
     // Process objects
    const copy = {};
    for (const [key, value] of Object.entries(original)) {
      // Using object. entries returns self-enumerable key-value pairs
      copy[key] = deepCopy(value);
    }
    return copy;
  } else {
    // Basic data type, return directly
    returnoriginal; }}Copy the code

Then, we can do a more minimalist version: use map() instead of for-of. Wrap the processed Object with object.fromentries ().

function deepCopy(original) {
  if (Array.isArray(original)) {
    return original.map(elem= > deepCopy(elem));
  } else if (typeof original === 'object'&& original ! = =null) {
    return Object.fromEntries(
      Object.entries(original)
        .map(([k, v]) = > [k, deepCopy(v)]));
  } else {
    // Basic data type, return directly
    returnoriginal; }}Copy the code

The loop function implements deep copy

There is a very tricky problem to deal with in the way objects are copied recursively: recursive stack bursting.

There are two ways to solve recursive stack bursting

  1. Eliminate tail recursion
  2. Switch to cycle treatment

Obviously, our recursive handler is not suitable for the first method, so we use the second method, which is to change the recursive function to a loop function.

At this point, we need to maintain a simple data agency to track the direct correlation of the data.

field explain
parent Save data directly associated

Default root = {}
key Key of the current traversal

The default value is undefined
data Value of the current traversal

Default value x (initial data)		 
function deepCopyWithLoop(x) {
    const root = {};

    / / stack
    const loopList = [
        {
            parent: root,
            key: undefined.data: x,
        }
    ];

    while(loopList.length) {
        // Depth first
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // Initialize the assignment target,
        // if key is undefined, copy to parent element, otherwise copy to child element
        let res = parent;
        if (typeofkey ! = ='undefined') {
            res = parent[key] = {};
        }

        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // If k is an object, loopList needs to be updated
                    // parent:res stores data associations
                    loopList.push({
                        parent: res,
                        key: k,
                        data: data[k],
                    });
                } else {
                    // Simple data types: direct assignmentres[k] = data[k]; }}}}return root;
}

Copy the code

There’s a little bit more to say about changing recursive functions with cyclic functions.

How to traverse a tree structure data type. I’m sure you’ll blurt it out. Use BFS/DFS. There are three types of BFS, Preorder/Inorder/Postorder.

Tree structure/depth-first/sequential traversal/recursive

function preOrderTraverseR(node) {
    if (node == null)  return;    // Baseline condition (jump out of recursion condition)
    console.log(node.data + "");
    preOrderTraverse(node.left);
    preOrderTraverse(node.right);
}
Copy the code

And let’s say instead of recursion, let’s say you walk through a tree. How do you deal with it. Remember one thing.

Traversal tree structure, 1. Depth-first non-recursive traversal using stack 2. Breadth-first non-recursive traversal (sequential traversal) is implemented using queues

Tree structure/depth-first/sequential traversal/non-recursive

function preOrderTraverser(nodes) {
    let result = [];
    let stack = [nodes];

    while(stack.length) { 
        let node = stack.pop(); 

        result.push(node.value);
        // The left and right trees are pushed in reverse order of traversal
        if(node.right) stack.push(node.right); 
        if(node.left) stack.push(node.left);

    }
    return result;
}

Copy the code

Note: The push order of the left and right trees is the opposite of the traversal order