René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"字节：模拟实现 Array.prototype.splice","articleBody":"## splice\r\n\r\n\u003e ```\r\n\u003e array.splice(start[, deleteCount[, item1[, item2[, ...]]]])\r\n\u003e ```\r\n\u003e\r\n\u003e MDN：**splice()** 方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组\r\n\r\n**[Array.prototype.splice()](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/splice) 的用法如下：**\r\n\r\n- `array.splice(start)` ：删除数组中从下标 `start` 开始（包含 `start` ）的所有元素\r\n- `array.splice(start, deleteCount)` ：删除数组中从下标 `start` 开始（包含 `start` ）的 `deleteCount` 元素\r\n- `array.splice(start, deleteCount, item1, item2, ...)` ：删除数组中从下标 `start` 开始（包含 `start` ）的 `deleteCount` 元素，然后在相同位置上插入 `item1, item2, ...`\r\n\r\n**特征包括如下：**\r\n\r\n- `start` ：可正可负，正数表示从下标为 `start` 的位置开始修改，如果 `start \u003e  array.length - 1 ` ，则表示从数组末尾处开始修改；负数表示从数组末位开始的第几位（从-1计数，这意味着-n是倒数第n个元素并且等价于`array.length-n`）\r\n- `deleteCount` ：表示从 `start` 开始要移除的元素个数，省略则表示把 `start` 之后的所有元素都移除，如果是 `0` 或负数，则不移除元素\r\n- `item1, item2, ...` ：要添加进数组的元素,从`start` 位置开始。如果不指定，则 `splice()` 将只删除数组元素\r\n- 返回：被删除的元素组成的一个数组\r\n\r\n**实现思路：**\r\n\r\n- 处理 `start` 负数或超出边界问题，计算真实有效的开始位置 `startIndex`\r\n\r\n- 处理 `deleteCount` 负数问题，计算真实有效的删除元素个数 `delCount`\r\n\r\n- 从 `startIndex` 开始删除 `delCount` 个元素并原地添加 `item1, item2, …` （添加元素个数为 `addCount` ）\r\n\r\n  - 拷贝删除的 `delCount` 到新数组 `deletedElements` ，用于 `array.splice` 函数返回\r\n  - 如果 `delCount \u003e addCount` （删除的元素个数大于添加元素）：将数组中 `startIndex + delCount` 后的元素向前移动 `delCount - addCount` 个位置，将添加元素拷贝进来\r\n\r\n  ![](http://resource.muyiy.cn/image/20201220212226.png)\r\n\r\n  - 如果 `delCount = addCount` （删除的元素个数等于添加元素）：直接将添加元素覆盖删除元素即可\r\n\r\n\r\n  ![](http://resource.muyiy.cn/image/20201220212238.png)\r\n\r\n  - 如果 `delCount \u003c addCount` （删除的元素个数小于添加元素）：将数组中 `startIndex + delCount` 后的元素向后移动 `addCount - delCount` 个位置，将元素拷贝进来 \r\n\r\n  ![](http://resource.muyiy.cn/image/20201220212158.png)\r\n\r\n- 返回 `deletedElements`\r\n\r\n**代码实现：**\r\n\r\n```js\r\nArray.prototype._splice = function(start, deleteCount) {\r\n    // 入参元素个数\r\n    let argumentsLen = arguments.length\r\n    // 数组\r\n    let array = Object(this)\r\n    // 数组长度\r\n    let len = array.length\r\n    // 添加元素个数\r\n    let addCount = argumentsLen \u003e 2 ? argumentsLen -2 : 0\r\n    // 计算有效的 start\r\n    let startIndex = computeSpliceStartIndex(start, array)\r\n    // 计算有效的 deleteCount\r\n    let delCount = computeSpliceDeleteCount(startIndex, deleteCount, len)\r\n    // 记录删除的数组元素\r\n    let deletedElements = new Array(delCount)\r\n    \r\n    // 将待删除元素记录到 deletedArray\r\n    recordDeleteElements(startIndex, delCount, array, deletedElements)\r\n    \r\n    // 移动数组元素\r\n    moveElements(startIndex, delCount, array, addCount)\r\n    \r\n    let i = startIndex\r\n    let argumentsIndex = 2\r\n    \r\n    // 插入新元素\r\n    while (argumentsIndex \u003c argumentsLen) {\r\n        array[i++] = arguments[argumentsIndex++]\r\n    }\r\n    \r\n    array.length = len - delCount + addCount\r\n\r\n    // 返回删除元素数组\r\n    return deletedElements;\r\n}\r\n\r\n// 计算真实的 start\r\nfunction computeSpliceStartIndex(start, len) {\r\n    // 处理负值，如果负数的绝对值大于数组的长度，则表示开始位置为第0位\r\n    if(start \u003c 0) {\r\n        start += len\r\n        return start \u003c 0 ? 0 : start\r\n    }\r\n    // 处理超出边界问题\r\n    return start \u003e len - 1 ? len - 1: start\r\n} \r\n\r\n// 计算真实的 deleteCount\r\nfunction computeSpliceDeleteCount(startIndex, deleteCount, len) {\r\n    // 超出边界问题\r\n    if(deleteCount \u003e len - startIndex) deleteCount = len - startIndex\r\n    // 负值问题\r\n    if(deleteCount \u003c 0) deleteCount = 0\r\n    return deleteCount\r\n}\r\n\r\n// 记录删除元素，用于 Array.prototype.splice() 返回\r\nfunction recordDeleteElements(startIndex, delCount, array, deletedElementd) {\r\n    for(let i = 0; i \u003c delCount; i++) {\r\n        deletedElementd[i] = array[startIndex + i]\r\n    }\r\n}\r\n\r\n// 移动数组元素，便于插入新元素\r\nfunction moveElements(startIndex, delCount, array, addCount) {\r\n    let over = addCount - delCount\r\n    if(over) {\r\n        // 向后移\r\n        for(let i = array.length - 1; i \u003e= startIndex + delCount; i--) {\r\n            array[i+over] = array[i]\r\n        }\r\n    } else if (over \u003c 0) {\r\n        // 向前移\r\n        for(let i = startIndex + delCount; i \u003c= array.length - 1; i++) {\r\n            if(i + Math.abs(over) \u003e array.length - 1) {\r\n                // 删除冗于元素\r\n                delete array[i]\r\n                continue\r\n            }\r\n            array[i] = array[i + Math.abs(over)]\r\n        }\r\n    }\r\n}\r\n\r\nlet months = ['Jan', 'March', 'April', 'June']\r\nconsole.log(months._splice(1, 1, 'Feb'))\r\n// [\"March\"]\r\nconsole.log(months)\r\n// [\"Jan\", \"Feb\", \"April\", \"June\"]\r\n```\r\n\r\n### 补充：密封对象与冻结对象\r\n\r\n\u003e 密封对象：通常一个对象是[可扩展的](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Object/isExtensible)（可以添加新的属性）。密封一个对象会让这个对象变的不能添加新属性，且所有已有属性会变的不可配置。属性不可配置的效果就是属性变的不可删除，以及一个数据属性不能被重新定义成为访问器属性，或者反之。但属性的值仍然可以修改。尝试删除一个密封对象的属性或者将某个密封对象的属性从数据属性转换成访问器属性，结果会静默失败或抛出[`TypeError`](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/TypeError)（在[严格模式](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Strict_mode) 中最常见的，但不唯一）\r\n\u003e\r\n\u003e --MDN\r\n\r\n```js\r\nif(delCount !== addCount \u0026\u0026 Object.isSealed(array)) {\r\n    throw new TypeError('the array is sealed')\r\n}\r\n```\r\n\r\n\u003e 冻结对象：数组作为一种对象，被冻结，其元素不能被修改。没有数组元素可以被添加或移除。\r\n\u003e\r\n\u003e --MDN\r\n\r\n```js\r\nif(delCount \u003e 0 \u0026\u0026 addCount \u003e 0 \u0026\u0026 Object.isFrozen(array)) {\r\n    throw new TypeError('the array is frozen')\r\n}\r\n```\r\n\r\n### V8源码\r\n\r\n```js\r\nfunction ArraySplice(start, delete_count) {\r\n  CHECK_OBJECT_COERCIBLE(this, \"Array.prototype.splice\");\r\n    \r\n  // 参数\r\n  var num_arguments = arguments.length;\r\n  // 数组\r\n  var array = TO_OBJECT(this);\r\n  // 数组长度\r\n  var len = TO_LENGTH(array.length);\r\n  // 计算有效的 start_i\r\n  var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);\r\n  // 计算有效的 del_count\r\n  var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,\r\n                                           start_i);\r\n  // 返回数组\r\n  var deleted_elements = ArraySpeciesCreate(array, del_count);\r\n  deleted_elements.length = del_count;\r\n  // 添加元素个数\r\n  var num_elements_to_add = num_arguments \u003e 2 ? num_arguments - 2 : 0;\r\n    \r\n  // 如果是密封对象且删除元素个数与添加元素个数不一致，报错\r\n  if (del_count != num_elements_to_add \u0026\u0026 %object_is_sealed(array)) {\r\n    throw %make_type_error(kArrayFunctionsOnSealed);\r\n  } else if (del_count \u003e 0 \u0026\u0026 %object_is_frozen(array)) {\r\n    // 如果是冻结对象且删除元素个数大于0，报错\r\n    throw %make_type_error(kArrayFunctionsOnFrozen);\r\n  }\r\n    \r\n  // 计算变更元素\r\n  var changed_elements = del_count;\r\n  if (num_elements_to_add != del_count) {\r\n    // If the slice needs to do a actually move elements after the insertion\r\n    // point, then include those in the estimate of changed elements.\r\n    changed_elements += len - start_i - del_count;\r\n  }\r\n    \r\n  // 移动元素\r\n  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {\r\n    %NormalizeElements(array);\r\n    if (IS_ARRAY(deleted_elements)) %NormalizeElements(deleted_elements);\r\n    SparseSlice(array, start_i, del_count, len, deleted_elements);\r\n    SparseMove(array, start_i, del_count, len, num_elements_to_add);\r\n  } else {\r\n    SimpleSlice(array, start_i, del_count, len, deleted_elements);\r\n    SimpleMove(array, start_i, del_count, len, num_elements_to_add);\r\n  }\r\n\r\n  // 将添加元素插入到删除元素的位置\r\n  var i = start_i;\r\n  var arguments_index = 2;\r\n  var arguments_length = arguments.length;\r\n  while (arguments_index \u003c arguments_length) {\r\n    array[i++] = arguments[arguments_index++];\r\n  }\r\n  array.length = len - del_count + num_elements_to_add;\r\n\r\n  // Return the deleted elements.\r\n  return deleted_elements;\r\n}\r\n```\r\n\r\n[Array.prototype.splice源码地址](https://github.com/v8/v8/blob/ad82a40509c5b5b4680d4299c8f08d6c6d31af3c/src/js/array.js#L660)\r\n\r\n### 总结\r\n\r\n`splice` 实现原理很简单，核心就是移动删除元素的边界，使无效元素个数与添加元素个数一致，然后用添加元素覆盖进去， **注意**  `splice` 是原地操作，不创建新数组，需要判读数组是否被密封或冻结\r\n\r\n**完整代码实现**\r\n\r\n```js\r\nArray.prototype._splice = function(start, deleteCount) {\r\n    // 入参元素个数\r\n    let argumentsLen = arguments.length\r\n    // 数组\r\n    let array = Object(this)\r\n    // 数组长度\r\n    let len = array.length\r\n    // 添加元素个数\r\n    let addCount = argumentsLen \u003e 2 ? argumentsLen -2 : 0\r\n    // 计算有效的 start\r\n    let startIndex = computeSpliceStartIndex(start, array)\r\n    // 计算有效的 deleteCount\r\n    let delCount = computeSpliceDeleteCount(startIndex, deleteCount, len)\r\n    // 记录删除的数组元素\r\n    let deletedElements = new Array(delCount)\r\n    \r\n    // 将待删除元素记录到 deletedArray\r\n    recordDeleteElements(startIndex, delCount, array, deletedElements)\r\n    \r\n    // 密封对象\r\n    if(delCount !== addCount \u0026\u0026 Object.isSealed(array)) {\r\n        throw new TypeError('the array is sealed')\r\n    }\r\n    // 冻结对象\r\n    if(delCount \u003e 0 \u0026\u0026 addCount \u003e 0 \u0026\u0026 Object.isFrozen(array)) {\r\n        throw new TypeError('the array is frozen')\r\n    }\r\n    \r\n    // 移动数组元素\r\n    moveElements(startIndex, delCount, array, addCount)\r\n    \r\n    let i = startIndex\r\n    let argumentsIndex = 2\r\n    \r\n    // 插入新元素\r\n    while (argumentsIndex \u003c argumentsLen) {\r\n        array[i++] = arguments[argumentsIndex++]\r\n    }\r\n    \r\n    array.length = len - delCount + addCount\r\n\r\n    // 返回删除元素数组\r\n    return deletedElements;\r\n}\r\n\r\n// 计算真实的 start\r\nfunction computeSpliceStartIndex(start, len) {\r\n    // 处理负值，如果负数的绝对值大于数组的长度，则表示开始位置为第0位\r\n    if(start \u003c 0) {\r\n        start += len\r\n        return start \u003c 0 ? 0 : start\r\n    }\r\n    // 处理超出边界问题\r\n    return start \u003e len - 1 ? len - 1: start\r\n} \r\n\r\n// 计算真实的 deleteCount\r\nfunction computeSpliceDeleteCount(startIndex, deleteCount, len) {\r\n    // 超出边界问题\r\n    if(deleteCount \u003e len - startIndex) deleteCount = len - startIndex\r\n    // 负值问题\r\n    if(deleteCount \u003c 0) deleteCount = 0\r\n    return deleteCount\r\n}\r\n\r\n// 记录删除元素，用于 Array.prototype.splice() 返回\r\nfunction recordDeleteElements(startIndex, delCount, array, deletedElementd) {\r\n    for(let i = 0; i \u003c delCount; i++) {\r\n        deletedElementd[i] = array[startIndex + i]\r\n    }\r\n}\r\n\r\n// 移动数组元素，便于插入新元素\r\nfunction moveElements(startIndex, delCount, array, addCount) {\r\n    let over = addCount - delCount\r\n    if(over) {\r\n        // 向后移\r\n        for(let i = array.length - 1; i \u003e= startIndex + delCount; i--) {\r\n            array[i+over] = array[i]\r\n        }\r\n    } else if (over \u003c 0) {\r\n        // 向前移\r\n        for(let i = startIndex + delCount; i \u003c= array.length - 1; i++) {\r\n            if(i + Math.abs(over) \u003e array.length - 1) {\r\n                // 删除冗于元素\r\n                delete array[i]\r\n                continue\r\n            }\r\n            array[i] = array[i + Math.abs(over)]\r\n        }\r\n    }\r\n}\r\n\r\nconst months = ['Jan', 'March', 'April', 'June']\r\nconsole.log(months._splice(1, 0, 'Feb'))\r\n// []\r\nconsole.log(months)\r\n// [\"Jan\", \"Feb\", \"March\", \"April\", \"June\"]\r\n\r\nconsole.log(months._splice(4, 1, 'May'))\r\n// [\"June\"]\r\nconsole.log(months)\r\n// [\"Jan\", \"Feb\", \"March\", \"April\", \"May\"]\r\n```\r\n","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-12-13T23:02:35.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":4},"url":"https://github.com/138/JavaScript-Algorithms/issues/138"}