How to write a deep copy that will impress your interviewer?

Shallow copy

Creates a new object with an exact copy of the original object property values. If the property is a primitive type, it copies the value of the primitive type, and if the property is a reference type, it copies the memory address, so if one object changes the address, it affects the other object.

Deep copy

To make a complete copy of an object out of memory, a new area of heap memory is created to hold the new object, and modification of the new object does not affect the original object

The minimalist version

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

This deep-copy approach has the following problems:

  • If there is a time object in obj, the time object will be serialized as a string by json.stringify
  • If there are RegExp or Error objects in obj, they will be serialized as empty objects
  • Obj has function and undefined, and when serialized, function and undefined are lost
  • Obj has NaN, Infinity, and -infinity, and the serialized result is null
  • Objects in obj that have constructors generated by using json.parse (json.stringify (obj)) deep copy discard the object’s constructor
  • Deep copy cannot be implemented correctly with circular references in OBJ

Basic version

If it is a shallow copy, it simply iterates through all the properties in the target object and assigns them to the target object. The basic type can be assigned directly, and the reference type can be assigned to the memory address as follows:

function shallowClone(target) {
    let clone = {};
    for(let i in target) {
        clone[i] = target[i];
    }
    return clone;
}
Copy the code

If it is a deep copy, it is resolved recursively, with the base type directly assigned and the reference type through for… In traversal assignment

function deepClone(target) { if(typeof target === 'object') { let clone = {}; for(let key in target) { clone[key] = deepClone(target[key]) } return clone; } else { return target; }}Copy the code
const target = {
    a: 1,
    b: {
        c: true,
        d: {
            e: 3
        }
    }
}
Copy the code

Obviously, this approach can meet the requirements of basic deep copy. But we don’t take into account arrays.

Consider a deep copy of an array

function deepClone(target) {
    if (typeof target === 'object') {
        let clone = Array.isArray(target) ? [] : {};
        for(let key in clone) {
            clone[key] = deepClone(target[key]);
        }
        return clone;
    } else {
        return target;
    }
}
const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: [
            {
                a: 1
            }
        ]
    },
    field4: [
        { 
            c: { d: 4 } 
        },
        4, 
        8
    ]
};
Copy the code

Deep copies of target objects, including objects and arrays, are implemented.

A circular reference

We execute the following test case:

const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8]
};
target.target = target;
Copy the code

You can see the following result:

Obviously, the stack ran out of memory because the recursion went into an infinite loop.

The reason is that the above object has a circular reference, that is, the object’s attributes refer to itself indirectly or directly:

Solve the problem of circular reference, we can create a extra storage space, to store the current objects and copy the object correspondence, when need to copy the current object, go to the storage space, find ever copy this object, if any direct return, if not to copy, so clever resolve problem of circular references.

This storage space needs to be able to store key-value data, and key can be a reference type, we can choose Map data structure:

  • Check whether objects have been cloned in the map
  • Yes. – Straight back
  • None – Stores the current object as key and the cloned object as value
  • Continue to clone
function clone(target, map = new Map()) { if (typeof target === 'object') { let clone = Array.isArray ? [] : {} if (map.get(target)) { return map.get(target); } map.set(target, clone) for(let key in target) { clone[key] = clone(target[key]); } return clone; } else { return target; }}Copy the code

Other data types

Currently, only the plain Object and array data types are considered, as well as the basic data types. There are more data types to consider. The correct type is judged by the Object. The prototype. ToString. Call to judge.

/ / getType access various data types function getType (target) {return Object. The prototype. ToString. Call (target); Function isObject(target) {const type = typeof target; return type ! == null && (type === 'object' || type === 'function'); } function deepClone(target, map = new Map()) { if (! isObject(target)) { return target; } const type = getType(target); let clone; // Avoid circular references if (map.get(target)) {return map.get(target); } map.set(target, clone); // clone set if (type === '[object Set]') { target.forEach(value => { clone.add(deepClone(value, map)); }); return clone; } // clone map if (type === '[object Map]') { target.forEach((value, key) => { clone.set(key, deepClone(value, map)) }) return clone; } / / clone objects and arrays if (type = = = [' object Array '] | | type = = = [' object object ']) {clone = Array. IsArray (target)? [] : {} for(let key in target) { clone[key] = deepClone(target[key], map); } } return clone; }Copy the code
const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8],
    empty: null,
    map,
    set,
};
Copy the code

conclusion

Object, array, set, map and other reference types are copied, as well as circular reference copies.

Refer to the article

How to write a deep copy that will impress your interviewer?

Parse (json.stringify (obj)) to implement deep copy