深度克隆从C#/C/Java漫谈到JavaScript真复制
Author:zhoulujun Date:
如果只想看js,直接从JavaScript标题开始。
在C#里面,深度clone有System.ICloneable。创建现有实例相同的值创建类的新实例
克隆原理
值类型变量与引用类型变量
如果我们有两个值类型的变量,将其中一个变量的值赋给另一个,实际上会创建该值的一个副本,这个副本与原来的值没有什么关系
——这意味着改变其中一个的值不会影响另一个变量的值。
如果是两个引用类型的变量,其中一个变量的值赋给另一个的话(不包括string类型,CLR会对其有特殊处理),并没有创建值的副本,而是使两个变量执行同一个对象
——这意味着改变对象的值会同时影响两个变量。要真正地创建引用类型的副本,我们必须克隆(clone)变量指向的对象。
C# 深度克隆
实现ICloneable接口使一个类型成为可克隆的(cloneable),这需要提供Clone方法来提供该类型的对象的副本。Clone方法不接受任何参数,返回object类型的对象(不管是何种类型实现该接口)。所以我们获得副本后仍需要进行显式地转换。
实现ICloneable接口的方式取决于我们的类型的数据成员。
如果类型仅包含值类型(int,byte等类型)和string类型的数据成员, 我们只要在Clone方法中初始化一个新的对象,将其的数据成员设置为当前对象的各个成员的值即可。事实上,object类的 MemberwiseClone方法会自动完成该过程。
如果自定义类型包含引用类型的数据成员,必须考虑Clone方法是实现浅拷贝(shallow copy)还是深拷贝(deep copy)。
浅拷贝(shallow copy)是指副本对象中的引用类型的数据成员与源对象的数据成员指向相同的对象。
相当于创建了一个新的对象,只是这个对象的所有内容,都和被拷贝的对象一模一样而已,即两者的修改是隔离的,相互之间没有影响
深拷贝(deep copy)则必须创建整个对象的结构,副本对象中的引用类型的数据成员与源对象的数据成员指向不同的对象。
拷贝者和被拷贝者若是同一个地址,则为浅拷贝,反之为深拷贝。
浅拷贝是容易实现的,就是使用前面提到的MemberwiseClone方法。开发人员往往希望使用的类型能够实现深拷贝,但会发现这样的类型并不 多。这种情况在System.Collections命名空间中尤其常见,这里面的类在其Clone方法中实现的都是浅拷贝。这么做主要出于两个原因:
创建一个大对象的副本对性能影响较大;
通用的集合类型可能会包含各种各样的对象,在这种情况下实现深拷贝并不可行,因为集合中的对象并非都是可克隆的,另外还存在循环引用的情况,这会让深拷贝过程陷入死循环。
C#克隆来自《实现可克隆(Cloneable)的类型》,代码实现参考原文。
C++内存深度克隆
回顾下基础知识,指针和引用主要有以下区别:
引用必须被初始化,但是不分配存储空间。指针不声明时初始化,在初始化的时候需要分配存储空间。
引用初始化后不能被改变,指针可以改变所指的对象。
不存在指向空值的引用,但是存在指向空值的指针——引用不能为空,指针可以为空。
指针指向一块内存,它的内容是所指内存的地址;而引用则是某块内存的别名——指针是一个实体,而引用仅是个别名。
引用没有const,指针有const,const的指针不可变
引用是类型安全的,而指针不是 (引用比指针多了类型检查)
指针和引用的自增(++)运算意义不一样;
引用没有const,指针有const,const的指针不可变;
cont int p 这个p指针不是一个普通的指针,它是个常量指针,即只能对其初始化,而不能赋值
稍微有点c语言基础的人都能看得出深度拷贝和浅拷贝的差异。总而言之,拷贝者和被拷贝者若是同一个地址,则为浅拷贝,反之为深拷贝。
一般的赋值操作是深度拷贝:
//深度拷贝 int a = 5;//在内存中找一块区域,命名为 a,用它来存放整数数据类型 5 int b = a;//在内存中找一块区域,命名为 b,把a拷贝一份,赋给b char str1 = "HelloWorld"; char str2 = str1;
简单的指针指向,则是浅拷贝:
//浅拷贝 int a = 5; int *b = &a; //c指向a的地址; &为取地址符,&a就是a这个变量的地址。 int *b; //int *b:定义了一个变量b,它是指针型的,关联数据类型 为int. b = &a; //int *b=&a表示b指针所指向的数据,等于a的地址. int *b =a 表示b指针指向a,即把a赋值给*b; // *a=b表示a指针所指向的数据,等于b。*a=&b表示a指针所指向的数据,等于b的地址du。 char* str1 = "HelloWorld"; char* str2 = str1;
将上面的浅拷贝改为深度拷贝后:
//深度拷贝 int a = 8; int *p = new int;//new int(a) *p = a; char* str1 = "HelloWorld"; int len = strlen(str1); char *str2 = new char[len]; memcpy(str2, str1, len);
以字符串拷贝为例
浅拷贝后,str1和str2同指向0x123456,不管哪一个指针,对该空间内容的修改都会影响另一个指针。
str1和str2指向不同的内存空间,各自的空间的内容一样。因为空间不同,所以不管哪一个指针,对该空间内容的修改都不会影响另一个指针。
在某些状况下,类内成员变量需要动态开辟堆内存,如果实行位拷贝,也就是把对象里的值完全复制给另一个对象,如A=B。这时,如果B中有一个成员变量指针已经申请了内存,那A中的那个成员变量也指向同一块内存。这就出现了问题:当B把内存释放了(如:析构),这时A内的指针就是野指针了,出现运行错误。
深拷贝和浅拷贝可以简单理解为:如果一个类拥有资源,当这个类的对象发生复制过程的时候,资源重新分配,这个过程就是深拷贝,反之,没有重新分配资源,就是浅拷贝。
深拷贝和浅拷贝的定义可以简单理解成:如果一个类拥有资源(堆,或者是其它系统资源),当这个类的对象发生复制过程的时候,这个过程就可以叫做深拷贝,反之对象存在资源,但复制过程并未复制资源的情况视为浅拷贝。
浅拷贝资源后在释放资源的时候会产生资源归属不清的情况导致程序运行出错。
IplImage *p1 = cvLoadImage( "Lena.jpg" ); IplImage *p2 = p1; p1 = NULL ;//or cvReleaseImage(p1);释放图像
以下的思考不知对不对——编程小翁
IplImage *是OpenCV里面的东西,它代表一张图。经过第二句后,p1与p2指向相同的对象,在底层就是指向同一块内存块。问题就来了,在第三句执行完毕后,p2还指向原来的对象吗?调试表明,YES。以前一直纠结着,p1都被置为空了(NULL),那原来的对象是不是也跟着被销毁了?其实,错了。
首先,我们应该把指针与其所指的对象分开看。指针重定向或者被置为NULL,对于其原先所指的对象的没有影响的。(但其实,应该会造成内存泄露,因为如果没有其他指针“接管”这部分内存块,就成无名的内存块摆在那边了,也就无法释放掉) 在p1重定向后,p2仍旧指向原来的对象。在此刻,p1与p2其实就是两个无关的事务了,也就是“分家”了。
java 深度克隆
java深度拷贝一般都用分装好的工具。没有必要重复造轮子。apache和spring都提供了BeanUtils的深度拷贝工具包。
把对象写到流里的过程是串行化(Serilization)过程,但是在Java程序师圈子里又非常形象地称为“冷冻”或者“腌咸菜(picking)”过程;而把对象从流中读出来的并行化(Deserialization)过程则叫做“解冻”或者“回鲜(depicking)”过程。应当指出的是,写在流里的是对象的一个拷贝,而原对象仍然存在于JVM里面,因此“腌成咸菜”的只是对象的一个拷贝,Java咸菜还可以回鲜。
在Java语言里深复制一个对象,常常可以先使对象实现Serializable接口,然后把对象(实际上只是对象的一个拷贝)写到一个流里(腌成咸菜),再从流里读出来(把咸菜回鲜),便可以重建对象。
在项目中我们需要克隆的对象可能包含多层引用类型,这就要涉及到多层克隆问题,多层克隆不仅要将克隆对象实现序列化接口,引用对象也同样的要实现序列化接口:
翻看JDK源码,Object类里面的clone方法定义如下
protected native Object clone() throws CloneNotSupportedException;
是“bitwise(逐位)的复制, 将该对象的内存空间完全复制到新的空间中去”这样实现的。
JavaScript深度拷贝
JavaScript深度克隆,首先想到是JSON.parse(JSON.stringify(target)),但是
JSON 克隆不支持函数、引用、undefined、Date、RegExp 等
递归克隆要考虑环、爆栈
要考虑 Date、RegExp、Function 等特殊对象的克隆方式
要不要克隆 __proto__,如果要克隆,就非常浪费内存;如果不克隆,就不是深克隆。
循环引用如何深度克隆
JSON.parse(JSON.stringify(target))数据及结构丢失
JSON.stringify() 将值转换为相应的JSON格式:
转换值如果有 toJSON() 方法,该方法定义什么值将被序列化。Date 日期调用了 toJSON() 将其转换为了 string 字符串(同Date.toISOString()),因此会被当做字符串处理。
布尔值、数字、字符串的包装对象在序列化过程中会自动转换成对应的原始值。
非数组对象的属性不能保证以特定的顺序出现在序列化后的字符串中。
undefined和null、任意的函数、正则表达式、symbol 值、NaN 和 Infinity 等,在序列化过程中会被忽略(出现在非数组对象的属性值中时)或者被转换成 null(出现在数组中时)。函数、undefined 被单独转换时,会返回 undefined,如JSON.stringify(function(){}) or JSON.stringify(undefined)。NaN 和 Infinity 格式的数值及 null 都会被当做 null。正则转换为空对象。
对包含循环引用的对象(对象之间相互引用,形成无限循环)执行此方法,会抛出错误。
所有以 symbol 为属性键的属性都会被完全忽略掉,即便 replacer 参数中强制指定包含了它们。
其他类型的对象,包括 Map/Set/WeakMap/WeakSet,仅会序列化可枚举的属性。
循环引用的对象使用 JSON.stringify 为什么会报错
let obj1={},obj2={};
obj1.a = obj2;
obj2.b = obj1;
结果就是 。obj1.a.b.a.b.a.b.a.b.a.b.a……………………无限循环引用
obj1 这个对象和 obj2 会无限相互引用,JSON.tostringify 无法将一个无限引用的对象序列化为 JOSN 字符串。
目前几乎所有的直接深复制对象的都有这样那样的问题 都不是很完美,但实际工作中需要用到完美深复制对象的场景也少之又少,包括jquery提供的extend方法也由于考虑到内存占用问题 在多层嵌套的数据里捉襟见肘。所以我们很多时候需要定制 clone 函数
一般手写的克隆函数都是这个样子
function clone(Obj) { var buf; if (Obj instanceof Array) { buf = []; //创建一个空的数组 var i = Obj.length; while (i--) { buf[i] = clone(Obj[i]); } return buf; } else if (Obj instanceof Object) { buf = {}; //创建一个空对象 for (var k in Obj) { //为这个对象添加新的属性 buf[k] = clone(Obj[k]); } return buf; } else { //普通变量直接赋值 return Obj; } }
精炼下
// 方法一: function clone (obj) { if (typeof obj !== 'object') return obj; var o = obj.constructor === Array ? [] : {}; for (var e in this) { o[e] = typeof obj[e] === "object" ? clone(obj[e]) : obj[e]; } return o; };
增加判断类型
switch (Object.prototype.toString.call(obj).toLowerCase()) { case '[object Array]': // clone array break case '[object Object]': // clone object break case '[object Date]': return new Date(obj) break case '[object RegExp]': retrun =new RegExp(obj) /* let flags = '' if (obj.global) flags += 'g' if (obj.ignoreCase) flags += 'i' if (obj.multiline) flags += 'm' */ // *** break case '[object HTMLBodyElement]': // Dom Element clone,// 遍历Dom树,每个节点 cloneNode(true),个人觉得没有必要。 return obj.cloneNode(true) case '[object Function]': // new function inherit && extent obj // return (new obj()).constructor; break case '[object Symbol]': // Symbol 既然定义为唯一的。那么久没有所谓的复制 throw new Error('') // JavaScript 各种内置对象 类型太多了。不能入戏太深 default: return obj }
其实这个只是造火箭面试的一个考核。实际就是数据复制而已。但是,比较处理循环引用是重点。
解决循环引用的方案探讨
循环引用的问题关键就是 obj1.a.b.a.b.a.b.a.b.a.b.a……………………无限循环引用,溢出问题。
WeakMap解决循环引用死循环
WeakMap 其中的键是弱引用的。其键必须是对象,而值可以是任意的(我一般用此来缓存计算结果,参考java中利用WeakHashMap实现缓存)。
function deepClone(obj, hash = new WeakMap()){ // 检查obj是否为null或者不是一个对象(包括数组、函数等),如果是,则直接返回obj if (obj === null || typeof obj !== 'object') { return obj; } // 检查hash中是否已经存储了当前对象的拷贝以处理循环引用 if (hash.has(obj)) { return hash.get(obj); } // 特殊处理数组情况 const cloneObj = Array.isArray(obj)?[]:Object.create(Object.getPrototypeOf(obj)); // const cloneData = new obj.constructor(); // 存储当前对象以避免循环引用 hash.set(obj, cloneObj); for (let k in obj) { if (obj.hasOwnProperty(k)) { // 确保key是对象自有的属性 cloneObj[k] = deepClone(obj[k], hash); // 递归拷贝 } } return cloneObj; }
WeakMap 健弱引用,帮助我们解决问题。
使用Array循环引用死循环
function deepClone(source,uniqueList=[]){ // determineUnique if(determineIteration){ return uniqueData.target; } uniqueList.push({source:source,target:target}); //TODO deep clone } function determineIteration(uniqueList,target){ retrun uniqueList.find(item=>item.source===target) }
当然也可以 hashmap object 处理
postMessage解决深度克隆
MessageChannel Worker SharedWorker等的 postMessage 可以拷贝undefined和循环引用的对象,只是不可拷贝函数,性能方面也很好。我们可以吧数据处理放到 woker里面去,处理完后到主线程(new Woker js引擎新增一个线程,可参考《Chrom浏览器组件与进程/线程模型分析—优化前端性能》)
deepClone始终有性能问题,如果业务层(大概率)是担心修改引用数据,使用immutable库或者immer库才是解决问题的正路。
目前使用较多还是 lodash deepclone
使用循环遍历替代递归实现深度克隆
其实破解递归爆栈的方法有两条路,第一种是消除尾递归,但在这个例子中貌似行不通,第二种方法就是干脆不用递归,改用循环,
举个例子,假设有如下的数据结构
var a = { a1: 1, a2: { b1: 1, b2: { c1: 1 } } }
这不就是一个树吗,其实只要把数据横过来看就非常明显了
a / \ a1 a2 | / \ 1 b1 b2 | | 1 c1 | 1
用循环遍历一棵树,需要借助一个栈,当栈为空时就遍历完了,栈里面存储下一个需要拷贝的节点
首先我们往栈里放入种子数据,key用来存储放哪一个父元素的那一个子元素拷贝对象
然后遍历当前节点下的子元素,如果是对象就放到栈里,否则直接拷贝
深度优先遍历
用于深度优先遍历(代替递归),使用了一个stack(栈)来存储待处理的节点。每次循环都会从栈中pop(弹出)一个节点进行处理,这个操作移除了并返回数组的最后一个元素,它模仿了栈的后进先出(LIFO)行为,这是深度优先遍历的一个关键特征。
function deepCloneObject(obj) { // 对非对象或null直接返回,因为没必要克隆 if (typeof obj !== 'object' || obj === null) { return obj; } // 存储克隆对象与原对象的映射,以处理循环引用的情况 const cloneMap = new Map(); // 初始化克隆栈 const stack = [{ original: obj, clone: Array.isArray(obj) ? [] : cloneSpecialObject(obj) }]; // 初始化克隆对象映射 cloneMap.set(obj, stack[0].clone); while (stack.length > 0) { // 获取栈顶对象对(包含原始和克隆对象) const { original, clone } = stack.pop(); // 遍历原始对象的所有属性 for (const key in original) { if (!original.hasOwnProperty(key)) continue; // 忽略继承属性 const value = original[key]; // 检查属性值是否为对象 if (typeof value === 'object' && value !== null) { // 检查是否已经克隆过 if (cloneMap.has(value)) { // 已克隆过,则在新对象中使用原先的克隆结果 clone[key] = cloneMap.get(value); } else { // 创建新对象或数组的克隆副本 const valueClone = Array.isArray(value) ? [] : cloneSpecialObject(value); // 将克隆结果添加到栈和映射中,以供后续处理 stack.push({ original: value, clone: valueClone }); cloneMap.set(value, valueClone); // 在克隆对象中设置引用 clone[key] = valueClone; } } else { // 如果属性是基本类型,则简单复制值 clone[key] = value; } } } // 返回根对象的克隆版本 return cloneMap.get(obj); } // 特殊对象的克隆:处理Date和RegExp对象的情况 function cloneSpecialObject(obj) { if (obj instanceof Date) { // 创建一个新的Date对象,其日期和时间与原始对象相同 return new Date(obj.getTime()); } else if (obj instanceof RegExp) { // 使用原始正则表达式和标志创建一个新的RegExp对象 return new RegExp(obj.source, obj.flags); } else { // 不是特殊对象,直接返回传入的参数 return obj; } }
改用循环后,再也不会出现爆栈的问题了,但是对于循环引用依然无力应对!下面的代码更易懂:
function cloneDFS(obj) { if (typeof obj !== 'object' || obj === null) { return obj; // 非对象或null,直接返回 } const root = Array.isArray(obj) ? [] : {}; // 初始化root为数组或对象,依据x的类型 // 栈 const stack = [ { parent: root, key: undefined, data: obj, }, ]; while (stack.length) { // 深度优先 const node = stack.pop(); const parent = node.parent; const key = node.key; const data = node.data; // 初始化赋值目标,key为undefined则拷贝到父元素,否则拷贝到子元素 let res = parent; if (typeof key !== 'undefined') { res = parent[key] = {}; } for (let k in data) { if (data.hasOwnProperty(k)) { if (typeof data[k] === 'object' && data[k] !== null) { // 下一次循环 stack.push({ parent: res, key: k, data: data[k], }); } else { res[k] = data[k]; } } } } return root; }
广度优先遍历实现深度克隆
广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法。在这种策略中,我们从根节点开始,一层一层地遍历。
我们使用一个队列来追踪那些已经被访问但其内部属性尚未被完全探索的对象。我们从顶层对象开始,将其及其对应的克隆对象加入队列。然后,我们迭代队列中的每个对象,访问其每个属性。如果属性值是对象,我们会检查这个对象是否已经被克隆过(通过WeakMap检查)。如果没有,就创建它的克隆,并将其添加到队列中以供后续遍历。
function cloneDeepBFS(obj) { const root = Array.isArray(obj) ? [] : {}; // 队列用于替代递归,实现广度优先遍历 const loopList = [ { parent: root, key: undefined, data: obj, }, ]; while (loopList.length) { // 广度优先处理 const { parent, key, data } = loopList.shift(); // res为当前要操作的目标引用,根据key判定是新对象还是根对象 let res = parent; if (key !== undefined) { res = parent[key] = Array.isArray(data) ? [] : {}; } // 遍历当前节点的所有子节点 for (let k in data) { if (data.hasOwnProperty(k)) { if (typeof data[k] === 'object' && data[k] !== null) { // 如果是对象,添加到队列中,以待后续处理 loopList.push({ parent: res, key: k, data: data[k], }); } else { // 如果是基本类型,直接赋值 res[k] = data[k]; } } } } return root; }
再改写下:
function cloneLoopBFS(obj) { if (typeof obj !== 'object' || obj === null) { return obj; // 非对象或null,直接返回 } const root = Array.isArray(obj) ? [] : {}; // 初始化root为数组或对象,依据x的类型 // 队列 const loopList = [ { parent: root, key: undefined, data: obj, }, ]; while (loopList.length) { // 广度优先遍历,从队列的头部取出元素 const node = loopList.shift(); // 与深度优先遍历主要区别点 const parent = node.parent; const key = node.key; const data = node.data; // 初始化赋值目标,key为undefined则拷贝到父元素,否则拷贝到子元素 let res = parent; if (typeof key !== 'undefined') { res = parent[key] = Array.isArray(data) ? [] : {}; } for (let k in data) { if (data.hasOwnProperty(k)) { if (typeof data[k] === 'object' && data[k] !== null) { // 与深度优先遍历的主要区别:这里采用的是队列,所以使用push将子节点添加到队列的尾部 loopList.push({ parent: res, key: k, data: data[k], }); } else { res[k] = data[k]; } } } } return root; }
其是BFS与DFS就是一行代码的区别而已。
深度克隆解决循环依赖问题
function cloneLoopBFS(obj) { if (typeof obj !== 'object' || obj === null) return obj; // 非对象或null,直接返回 const root = Array.isArray(obj) ? [] : {}; // 初始化root为数组或对象,依据x的类型 const loopList = [ // 队列 { parent: root, key: undefined, data: obj, }, ]; const seenObjects = new Map();// 记录已经克隆过的对象,避免循环引用 seenObjects.set(obj, root); while (loopList.length) { // 广度优先遍历,从队列的头部取出元素 const node = loopList.shift(); // 与深度优先遍历主要区别点 const parent = node.parent; const key = node.key; const data = node.data; // 初始化赋值目标,key为undefined则拷贝到父元素,否则拷贝到子元素 let res = parent; if (typeof key !== 'undefined') { res = parent[key] = Array.isArray(data) ? [] : {}; // 检查是否已经克隆过该对象 if (seenObjects.has(data)) { parent[key] = seenObjects.get(data); continue; // 跳过对已经克隆过的对象的进一步处理 } // 记录克隆过的对象 seenObjects.set(data, res); } for (let k in data) { if (data.hasOwnProperty(k)) { if (typeof data[k] === 'object' && data[k] !== null) { // 检查是否已经克隆过该对象 if (seenObjects.has(data[k])) { res[k] = seenObjects.get(data[k]); } else { // 与深度优先遍历的主要区别:这里采用的是队列,所以使用push将子节点添加到队列的尾部 loopList.push({ parent: res, key: k, data: data[k], }); seenObjects.set(data[k], Array.isArray(data[k]) ? [] : {}); } } else { res[k] = data[k]; } } } } return root; } // 测试 const obj = { a: 1, b: { c: 2, d: 3 } }; obj.b.e = obj; // 循环引用 const clonedObj = cloneLoopBFS(obj); console.log(clonedObj);
Object.create(Object.getPrototypeOf(obj))和new obj.constructor()
Object.create(Object.getPrototypeOf(obj))
优点:
它创建了一个新对象,其原型链与原对象相同。这对于保持对象间继承关系很有用。
对于继承自不同构造函数的对象,这种方式能够更准确地保留对象的“形态”。
缺点:
它只复制对象的原型链,不会复制对象的属性。你需要额外复制这些属性。
对于需要通过构造函数初始化某些状态的对象,这种方法不会调用构造函数来进行初始化。
new obj.constructor()
优点:
这种方法通过调用对象的构造函数来创建一个新的实例,这意味着如果构造函数中有初始化逻辑,这些逻辑会被执行。
对于那些构造函数不需要参数或者可以正确处理没有参数的情况下,它能有效地创建对象的深拷贝。
缺点:
如果构造函数需要特定的参数才能正确初始化新对象,而你没有提供这些参数,那么可能会导致错误或不完全正确的初始化。
并不是所有对象都通过构造函数创建(例如用Object.create创建的对象),在这些情况下,使用new obj.constructor()可能无法正确拷贝对象原型。
总结
如果你需要准确保留对象的原型链,而不太关心对象如何被初始化,或者你计划手动复制对象的可枚举属性,Object.create(Object.getPrototypeOf(obj))是一个好选择。
如果对象的构造过程对你很重要(例如,对象的初始状态由构造函数设置),且你确定无需传递特定参数给构造函数,或者构造函数可以无参数运行,那么new obj.constructor()可能更适合。
参考文章:
实现可克隆(Cloneable)的类型 https://www.cnblogs.com/anderslly/archive/2007/04/08/implementingcloneabletype.html
ICloneable 的方法实现 不要轻易使用ICloneable https://blog.csdn.net/iteye_14608/article/details/82404997
关于c中int a=1; int b=a类型问题的思考 https://www.cnblogs.com/wengzilin/archive/2013/03/25/2980520.html
深拷贝的终极探索 https://yanhaijing.com/javascript/2018/10/10/clone-deep/
转载本站文章《深度克隆从C#/C/Java漫谈到JavaScript真复制》,
请注明出处:https://www.zhoulujun.cn/html/webfront/ECMAScript/js6/2018_1219_8450.html