JavaScript-Algorithms
JavaScript-Algorithms copied to clipboard
Published
20 hours ago •
sisterAn
sisterAn
字节：模拟实现 Array.prototype.splice
splice
array.splice(start[, deleteCount[, item1[, item2[, ...]]]])MDN：splice() 方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组
Array.prototype.splice() 的用法如下：
-
array.splice(start)：删除数组中从下标start开始（包含start）的所有元素 -
array.splice(start, deleteCount)：删除数组中从下标start开始（包含start）的deleteCount元素 -
array.splice(start, deleteCount, item1, item2, ...)：删除数组中从下标start开始（包含start）的deleteCount元素，然后在相同位置上插入item1, item2, ...
特征包括如下：
-
start：可正可负，正数表示从下标为start的位置开始修改，如果start > array.length - 1，则表示从数组末尾处开始修改；负数表示从数组末位开始的第几位（从-1计数，这意味着-n是倒数第n个元素并且等价于array.length-n） -
deleteCount：表示从start开始要移除的元素个数，省略则表示把start之后的所有元素都移除，如果是0或负数，则不移除元素 -
item1, item2, ...：要添加进数组的元素,从start位置开始。如果不指定，则splice()将只删除数组元素 - 返回：被删除的元素组成的一个数组
实现思路：
-
处理
start负数或超出边界问题，计算真实有效的开始位置startIndex -
处理
deleteCount负数问题，计算真实有效的删除元素个数delCount -
从
startIndex开始删除delCount个元素并原地添加item1, item2, …（添加元素个数为addCount）- 拷贝删除的
delCount到新数组deletedElements，用于array.splice函数返回 - 如果
delCount > addCount（删除的元素个数大于添加元素）：将数组中startIndex + delCount后的元素向前移动delCount - addCount个位置，将添加元素拷贝进来
- 如果
delCount = addCount（删除的元素个数等于添加元素）：直接将添加元素覆盖删除元素即可
- 如果
delCount < addCount（删除的元素个数小于添加元素）：将数组中startIndex + delCount后的元素向后移动addCount - delCount个位置，将元素拷贝进来
- 拷贝删除的
-
返回
deletedElements
代码实现：
Array.prototype._splice = function(start, deleteCount) {
// 入参元素个数
let argumentsLen = arguments.length
// 数组
let array = Object(this)
// 数组长度
let len = array.length
// 添加元素个数
let addCount = argumentsLen > 2 ? argumentsLen -2 : 0
// 计算有效的 start
let startIndex = computeSpliceStartIndex(start, array)
// 计算有效的 deleteCount
let delCount = computeSpliceDeleteCount(startIndex, deleteCount, len)
// 记录删除的数组元素
let deletedElements = new Array(delCount)
// 将待删除元素记录到 deletedArray
recordDeleteElements(startIndex, delCount, array, deletedElements)
// 移动数组元素
moveElements(startIndex, delCount, array, addCount)
let i = startIndex
let argumentsIndex = 2
// 插入新元素
while (argumentsIndex < argumentsLen) {
array[i++] = arguments[argumentsIndex++]
}
array.length = len - delCount + addCount
// 返回删除元素数组
return deletedElements;
}
// 计算真实的 start
function computeSpliceStartIndex(start, len) {
// 处理负值，如果负数的绝对值大于数组的长度，则表示开始位置为第0位
if(start < 0) {
start += len
return start < 0 ? 0 : start
}
// 处理超出边界问题
return start > len - 1 ? len - 1: start
}
// 计算真实的 deleteCount
function computeSpliceDeleteCount(startIndex, deleteCount, len) {
// 超出边界问题
if(deleteCount > len - startIndex) deleteCount = len - startIndex
// 负值问题
if(deleteCount < 0) deleteCount = 0
return deleteCount
}
// 记录删除元素，用于 Array.prototype.splice() 返回
function recordDeleteElements(startIndex, delCount, array, deletedElementd) {
for(let i = 0; i < delCount; i++) {
deletedElementd[i] = array[startIndex + i]
}
}
// 移动数组元素，便于插入新元素
function moveElements(startIndex, delCount, array, addCount) {
let over = addCount - delCount
if(over) {
// 向后移
for(let i = array.length - 1; i >= startIndex + delCount; i--) {
array[i+over] = array[i]
}
} else if (over < 0) {
// 向前移
for(let i = startIndex + delCount; i <= array.length - 1; i++) {
if(i + Math.abs(over) > array.length - 1) {
// 删除冗于元素
delete array[i]
continue
}
array[i] = array[i + Math.abs(over)]
}
}
}
let months = ['Jan', 'March', 'April', 'June']
console.log(months._splice(1, 1, 'Feb'))
// ["March"]
console.log(months)
// ["Jan", "Feb", "April", "June"]
补充：密封对象与冻结对象
密封对象：通常一个对象是可扩展的（可以添加新的属性）。密封一个对象会让这个对象变的不能添加新属性，且所有已有属性会变的不可配置。属性不可配置的效果就是属性变的不可删除，以及一个数据属性不能被重新定义成为访问器属性，或者反之。但属性的值仍然可以修改。尝试删除一个密封对象的属性或者将某个密封对象的属性从数据属性转换成访问器属性，结果会静默失败或抛出
TypeError（在严格模式 中最常见的，但不唯一）--MDN
if(delCount !== addCount && Object.isSealed(array)) {
throw new TypeError('the array is sealed')
}
冻结对象：数组作为一种对象，被冻结，其元素不能被修改。没有数组元素可以被添加或移除。
--MDN
if(delCount > 0 && addCount > 0 && Object.isFrozen(array)) {
throw new TypeError('the array is frozen')
}
V8源码
function ArraySplice(start, delete_count) {
CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
// 参数
var num_arguments = arguments.length;
// 数组
var array = TO_OBJECT(this);
// 数组长度
var len = TO_LENGTH(array.length);
// 计算有效的 start_i
var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
// 计算有效的 del_count
var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
start_i);
// 返回数组
var deleted_elements = ArraySpeciesCreate(array, del_count);
deleted_elements.length = del_count;
// 添加元素个数
var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
// 如果是密封对象且删除元素个数与添加元素个数不一致，报错
if (del_count != num_elements_to_add && %object_is_sealed(array)) {
throw %make_type_error(kArrayFunctionsOnSealed);
} else if (del_count > 0 && %object_is_frozen(array)) {
// 如果是冻结对象且删除元素个数大于0，报错
throw %make_type_error(kArrayFunctionsOnFrozen);
}
// 计算变更元素
var changed_elements = del_count;
if (num_elements_to_add != del_count) {
// If the slice needs to do a actually move elements after the insertion
// point, then include those in the estimate of changed elements.
changed_elements += len - start_i - del_count;
}
// 移动元素
if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
%NormalizeElements(array);
if (IS_ARRAY(deleted_elements)) %NormalizeElements(deleted_elements);
SparseSlice(array, start_i, del_count, len, deleted_elements);
SparseMove(array, start_i, del_count, len, num_elements_to_add);
} else {
SimpleSlice(array, start_i, del_count, len, deleted_elements);
SimpleMove(array, start_i, del_count, len, num_elements_to_add);
}
// 将添加元素插入到删除元素的位置
var i = start_i;
var arguments_index = 2;
var arguments_length = arguments.length;
while (arguments_index < arguments_length) {
array[i++] = arguments[arguments_index++];
}
array.length = len - del_count + num_elements_to_add;
// Return the deleted elements.
return deleted_elements;
}
总结
splice 实现原理很简单，核心就是移动删除元素的边界，使无效元素个数与添加元素个数一致，然后用添加元素覆盖进去， 注意 splice 是原地操作，不创建新数组，需要判读数组是否被密封或冻结
完整代码实现
Array.prototype._splice = function(start, deleteCount) {
// 入参元素个数
let argumentsLen = arguments.length
// 数组
let array = Object(this)
// 数组长度
let len = array.length
// 添加元素个数
let addCount = argumentsLen > 2 ? argumentsLen -2 : 0
// 计算有效的 start
let startIndex = computeSpliceStartIndex(start, array)
// 计算有效的 deleteCount
let delCount = computeSpliceDeleteCount(startIndex, deleteCount, len)
// 记录删除的数组元素
let deletedElements = new Array(delCount)
// 将待删除元素记录到 deletedArray
recordDeleteElements(startIndex, delCount, array, deletedElements)
// 密封对象
if(delCount !== addCount && Object.isSealed(array)) {
throw new TypeError('the array is sealed')
}
// 冻结对象
if(delCount > 0 && addCount > 0 && Object.isFrozen(array)) {
throw new TypeError('the array is frozen')
}
// 移动数组元素
moveElements(startIndex, delCount, array, addCount)
let i = startIndex
let argumentsIndex = 2
// 插入新元素
while (argumentsIndex < argumentsLen) {
array[i++] = arguments[argumentsIndex++]
}
array.length = len - delCount + addCount
// 返回删除元素数组
return deletedElements;
}
// 计算真实的 start
function computeSpliceStartIndex(start, len) {
// 处理负值，如果负数的绝对值大于数组的长度，则表示开始位置为第0位
if(start < 0) {
start += len
return start < 0 ? 0 : start
}
// 处理超出边界问题
return start > len - 1 ? len - 1: start
}
// 计算真实的 deleteCount
function computeSpliceDeleteCount(startIndex, deleteCount, len) {
// 超出边界问题
if(deleteCount > len - startIndex) deleteCount = len - startIndex
// 负值问题
if(deleteCount < 0) deleteCount = 0
return deleteCount
}
// 记录删除元素，用于 Array.prototype.splice() 返回
function recordDeleteElements(startIndex, delCount, array, deletedElementd) {
for(let i = 0; i < delCount; i++) {
deletedElementd[i] = array[startIndex + i]
}
}
// 移动数组元素，便于插入新元素
function moveElements(startIndex, delCount, array, addCount) {
let over = addCount - delCount
if(over) {
// 向后移
for(let i = array.length - 1; i >= startIndex + delCount; i--) {
array[i+over] = array[i]
}
} else if (over < 0) {
// 向前移
for(let i = startIndex + delCount; i <= array.length - 1; i++) {
if(i + Math.abs(over) > array.length - 1) {
// 删除冗于元素
delete array[i]
continue
}
array[i] = array[i + Math.abs(over)]
}
}
}
const months = ['Jan', 'March', 'April', 'June']
console.log(months._splice(1, 0, 'Feb'))
// []
console.log(months)
// ["Jan", "Feb", "March", "April", "June"]
console.log(months._splice(4, 1, 'May'))
// ["June"]
console.log(months)
// ["Jan", "Feb", "March", "April", "May"]
function(index, dele) { if(index === undefined || (dele === undefined && typeof dele === 'number')) return '请输入正确完整条件' const arrLeft = [] const arrRight = [] const arrAdd = [] const deleArr = [] for(let i = 0; this.length > i; i++) { if(i < index) { arrLeft.push(this[i]) } else if(i >= index + dele) { arrRight.push(this[i]) } else { deleArr.push(this[i]) } } for(let i = 2; arguments.length > i; i++) { arrAdd.push(arguments[i]) } [...arrLeft, ...arrAdd, ...arrRight].forEach((item, index) => { this[index] = item }) return deleArr }
1、大佬这里的 over 需要 over > 0 吧？
let over = addCount - delCount;
if(over) {
// 向后移
2、这块的逻辑处理好像不太对（稀疏数组也存在类似情况）。
} else if (over < 0) {
// 向前移
for(let i = startIndex + delCount; i <= array.length - 1; i++) {
if(i + Math.abs(over) > array.length - 1) {
// 删除冗于元素
delete array[i]
continue
}
array[i] = array[i + Math.abs(over)]
}
}
}
例如：
var arr = [1,2,3,4,5];
arr.splice(0, 3, 6, 7);
console.log(arr); //
- 预期结果：[6, 7, 4, 5]
- 实际结果：[6, 7, 3, 5]
移动元素函数里 判断over<0的情况 i应该从startIdx+delCount+over开始
/**
数组splice方法实现
arr.splice(startIdx,delCount,add1,add2,...);
*/
Array.prototype._splice = function () {
//1. 记录入参个数
let argumentsLen = arguments.length;
let start = arguments[0], deleteCount = arguments[1];
//2. 数组长度
let arrayLength = this.length;
let arr = Object(this);
//3. 添加元素个数
let addCount = argumentsLen > 2 ? argumentsLen - 2 : 0
console.log('addCount: ', addCount);
//4. 计算有效的开始位置start
let startIdx = computeSpliceStartIdx(start, arrayLength);
//5. 计算有效的删除个数
let delCount = computeSpiceDelCount(startIdx, deleteCount, arrayLength);
console.log('delCount: ', delCount);
//6. 记录删除的元素
let delElements = new Array(delCount);
recordDelElements(startIdx, delCount, arr, delElements);
//7. 判断是否是密封对象
if (delCount !== addCount && Object.isSealed(arr)) {
throw new TypeError('the arr is sealed')
}
//8. 判断是否是冻结对象
if (delCount > 0 && addCount > 0 && Object.isFrozen(arr)) {
throw new TypeError('the arr is frozen')
}
//移动数组元素
moveElements(startIdx, delCount, arr, addCount);
let i = startIdx;
let argumentsIdx = 2;
//插入新的元素
while (argumentsIdx < argumentsLen) {
arr[i++] = arguments[argumentsIdx++];
}
arr.length = arrayLength - delCount + addCount;
return delElements;
}
function computeSpliceStartIdx(start, arrayLength) {
if (start < 0) {
start += arrayLength;
return start < 0 ? 0 : start;
}
//start>0的情况
return start > arrayLength - 1 ? arrayLength - 1 : start;
}
//计算delCount
function computeSpiceDelCount(startIdx, deleteCount, arrayLength) {
if (deleteCount > arrayLength - startIdx) {
deleteCount = arrayLength - startIdx
}
if (deleteCount < 0) deleteCount = 0
return deleteCount;
}
//记录删除的元素
function recordDelElements(startIdx,delCount,arr,delElements) {
for(let i=0;i<delCount;i++) {
delElements[i] = arr[startIdx+i];
}
}
//移动数组
function moveElements(startIdx, delCount, arr, addCount){
let over = addCount - delCount;
console.log('over: ', over);
if(over>0) {
//增加的数大于了删除的数 向后移动
for(let i=arr.length-1;i>=startIdx+delCount;i--) {
arr[i+over] = arr[i];
}
} else if(over<0) {
//增加的数小于删除的数 向前移动
for(let i=startIdx+delCount+over;i<=arr.length-1;i++) {
if(i+Math.abs(over)>arr.length-1) {
delete arr[i]
continue
}
arr[i] = arr[i+Math.abs(over)];
}
console.log('arr: over<0', arr);
}
}
let arr = [1, 2, 3, 4, 5];
arr._splice(1,3,6,7)
console.log('arr: ', arr);//arr: [ 1, 6, 7, 5 ]
Array.prototype.splice_ = function(start,deletecount,...args){
let result = []
if(deletecount===undefined){
for(let i = start;i<this.length;i++){
result.push(this[i])
}
let k = 0,j =start;
let finalLen = this.length-result.length+args.length
if(args.length){
while(k<args.length){
this[j] = args[k]
k++
j++
}
while(this.length>finalLen){
this.pop()
}
}
}else if(deletecount<=0){
if(args.length){
let tempList = []
for(let i = start;i<this.length;i++){
tempList.push(this[i])
}
let k = 0,j = args.length
while(k<tempList.length){
args[j] = tempList[k]
k++
j++
}
let m = 0,n =start;
while(m<args.length){
this[n] = args[m]
m++
n++
}
}
}else if(deletecount>0){
for(let i = start;i<start+deletecount;i++){
result.push(this[i])
}
if(args.length){
let tempList = []
for(let i = start+deletecount;i<this.length;i++){
tempList.push(this[i])
}
let k = 0,j = args.length
while(k<tempList.length){
args[j] = tempList[k]
k++
j++
}
let m = 0,n =start;
let finalLen = this.length-result.length+args.length
while(m<args.length){
this[n] = args[m]
m++
n++
}
while(this.length>finalLen){
this.pop()
}
}
}
return result
}
let arr= [1,2,3,4]
arr.splice_(2,2,'111')
console.log(arr)
