深入探索:用 TypeScript 手寫(xiě) 20 個(gè)常見(jiàn)數(shù)組方法
一口氣寫(xiě)出20個(gè)數(shù)組方法有點(diǎn)難度，我們可以在腦海里對(duì)數(shù)組方法進(jìn)行分類(lèi)，同一類(lèi)操作歸為一類(lèi)，這樣寫(xiě)是不是更加簡(jiǎn)單了呢？
- 添加元素類(lèi)：push、unshift
- 刪除元素類(lèi)：pop、shift、splice
- 數(shù)組轉(zhuǎn)字符串類(lèi)：toString、join
- 遍歷類(lèi)：forEach、reduce、reduceRight、map、filter、some、every
- 排序：sort
- 拼接：concat
- 索引：indexOf、lastIndexOf
一口氣寫(xiě)了整整19個(gè)，就是不夠那20個(gè)，看來(lái)我不夠資格說(shuō)”前端已死“，來(lái)查一查差哪些：
- 翻轉(zhuǎn)：reverse
- 淺拷貝：slice
為什么寫(xiě)這些？因?yàn)檫@些是vscode中lib.es5.d.ts中定義的數(shù)組方法
數(shù)組需要接收一個(gè)泛型參數(shù)，用來(lái)動(dòng)態(tài)獲取數(shù)組中元素類(lèi)型
interface MyArray<T> {
}
第三步：方法定義
首先是元素添加類(lèi)方法:push、unshift，千萬(wàn)不要忘了他們有返回值，返回值是新數(shù)組的length
push(...args: T[]): number;
unshift(...args: T[]): number;
刪除元素類(lèi)方法，前兩個(gè)比較好寫(xiě)，它們的返回值都是刪除的那個(gè)元素，但是需要注意的是空數(shù)組調(diào)用后返回undefined；
pop(): T | undefined;
shift(): T | undefined;
/**錯(cuò)誤的寫(xiě)法：splice(start: number, deleteNum: number, ...args: T[]): T[];**/
splice這樣寫(xiě)還有問(wèn)題，因?yàn)閟plice只有第一個(gè)參數(shù)是必傳，這樣就需要寫(xiě)多個(gè)聲明了
splice(start: number, deleteNum?: number): T[];
splice(start: number, deleteNum: number, ...args: T[]): T[];
然后是數(shù)組轉(zhuǎn)字符串類(lèi)：toString、join，沒(méi)有難度直接寫(xiě)
join(param?: string): string;
toString(): string;
遍歷類(lèi)：forEach、reduce、reduceRight、map、filter、some、every 我們一個(gè)一個(gè)地來(lái)寫(xiě)，首先是forEach方法，這個(gè)方法我們常用的就只有回調(diào)函數(shù)，但是其實(shí)還有一個(gè)參數(shù)可以指定回調(diào)函數(shù)的this
forEach(callbackFn: (value: T, index: number, array: T[]) => void, thisArg?: any): void;
reduce這個(gè)方法可以實(shí)現(xiàn)累加器，也是我們最常用的方法之一,reduceRight與reduce的區(qū)別就在于它是從右往左遍歷
reduce(callbackFn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T, initialValue: T): T;
map方法遍歷數(shù)組并且會(huì)返回一個(gè)新的數(shù)組，它是一個(gè)純函數(shù)
map(callbackFn: (value: T, index: number, array: T[]) => T, thisArg?: any): T[];
后面的一些遍歷方法我們就不再贅述，基本上都遵從回調(diào)函數(shù)，this綁定參數(shù)，這種固定模式
后面的一些方法都比較簡(jiǎn)單，最后把寫(xiě)好的方法定義都匯總起來(lái)：
interface MyArray<T> {
length: number;
// 數(shù)組添加元素
push(...args: T[]): number;
unshift(...args: T[]): number;
// 數(shù)組刪除元素
pop(): T | undefined;
shift(): T | undefined;
splice(start?: number, deleteNum?: number): T[];
splice(start: number, deleteNum?: number): T[];
splice(start: number, deleteNum: number, ...args: T[]): T[];
// 數(shù)組索引
indexOf(item: T): number;
lastIndexOf(item: T): number;
// 數(shù)組遍歷
forEach(callbackFn: (value: T, index: number, array: T[]) => void, thisArg?: any): void;
reduce(callbackFn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T, initialValue: T): T;
reduceRight(callbackFn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T): T;
some(callbackFn: (value: T, index: number, array: T[]) => boolean, thisArg?: any): boolean;
every(callbackFn: (value: T, index: number, array: T[]) => boolean, thisArg?: any): boolean;
map(callbackFn: (value: T, index: number, array: T[]) => T, thisArg?: any): T[];
// 數(shù)組與字符串
join(param?: string): string;
toString(): string;
toLocalString(): string;
// 數(shù)組排序
sort(callbackFn: (a: T, b: T) => number): T[];
// 數(shù)組扁平化
flat(deepSize: number): T[];
// 數(shù)組的拼接
concat(...args: T[]): T[];
// 數(shù)組的拷貝
slice(start?: number, end?: number): T[];
// 數(shù)組翻轉(zhuǎn)
reverse(): T[];
}
前面都是前奏，現(xiàn)在開(kāi)始今天的正題，手寫(xiě)數(shù)組的這些方法。
第四步 實(shí)現(xiàn)這些方法首先我們修改一下接口定義的名稱(chēng)：IMyArray，然后定義MyArray類(lèi)實(shí)現(xiàn)該接口，編輯器會(huì)自動(dòng)將上面的方法注入
class MyArray<T> implements IMyArray<T> {
}
先實(shí)現(xiàn)push方法:
push(...args: T[]): number {
const len = args.length;
for (let i = 0; i < len; i++) {
this[this.length++] = args[i];
}
return this.length;
}
其實(shí)我們實(shí)現(xiàn)的是一個(gè)類(lèi)數(shù)組，只不過(guò)含有數(shù)組的所有方法，這里經(jīng)常會(huì)使用類(lèi)數(shù)組來(lái)考察對(duì)push的理解，比如這道題：
const obj = {
0:1,
3:2,
length:2,
push:[].push
}
obj.push(3);
然后實(shí)現(xiàn)一個(gè)splice，注意splice是一個(gè)原地修改數(shù)組的方法，所以我們不能借助額外的空間實(shí)現(xiàn)，這里我們還是使用Array.prototype.splice的方式來(lái)實(shí)現(xiàn)，類(lèi)數(shù)組不能通過(guò)length屬性刪除元素
Array.prototype.splice = function splice(start: number, deleteNum = 1, ...rest: any[]) {
if (start === undefined) {
return [];
}
const that = this;
let returnValue: any[] = [];
// 將begin到end的元素全部往前移動(dòng)
function moveAhead(begin: number, end: number, step: number) {
const deleteArr: any[] = [];
// 可以從前往后遍歷
for (let i = begin; i < end && i + step < end; i++) {
if (i < begin + step) {
deleteArr.push(that[i]);
}
that[i] = that[i + step];
}
return deleteArr;
}
function pushAtIdx(idx: number, ...items: any[]) {
const len = items.length;
const lenAfter = that.length;
// 在idx處添加len個(gè)元素，首先需要把所有元素后移len位，然后替換中間那些元素
for (let i = idx; i < idx + len; i++) {
if (i < lenAfter) {
that[i + len] = that[i];
}
if (i - idx < len) {
that[i] = items[i - idx];
}
}
}
if (deleteNum >= 1) {
returnValue = moveAhead(Math.max(start, 0), that.length, deleteNum);
that.length -= deleteNum;
}
pushAtIdx(start, ...rest);
return returnValue;
};
后面的實(shí)現(xiàn)我們都是用數(shù)組來(lái)實(shí)現(xiàn)，比如實(shí)現(xiàn)其中某一個(gè)遍歷的方法，我們就實(shí)現(xiàn)比較復(fù)雜的比如reduce，reduce的實(shí)現(xiàn)比較簡(jiǎn)單
Array.prototype.reduce = function <T>(
callbackFn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T,
initialValue?: T
): T {
// reduce如果有初始值那么以初始值開(kāi)始計(jì)算，如果沒(méi)有初始值那么用數(shù)組第一項(xiàng)作為初始值
let startIndex = 0;
const len = this.length;
let ans = initialValue;
if (initialValue === undefined) {
ans = this[0];
startIndex = 1;
}
for (let i = startIndex; i < len; i++) {
ans = callbackFn(ans, this[i], i, this);
}
return ans;
};
然后再實(shí)現(xiàn)一個(gè)reverse數(shù)組翻轉(zhuǎn)方法，我們可以遍歷前一半的數(shù)據(jù)，然后分別與后面一半進(jìn)行交換，這樣就完成了原地翻轉(zhuǎn)：
Array.prototype.reverse = function () {
const len = this.length;
const that = this;
function swap(a, b) {
const tmp = that[a];
that[a] = that[b];
that[b] = tmp;
}
for (let i = 0; i < len >> 1; i++) {
swap(i, len - i - 1);
}
return this;
};
至于sort和flat方法這些都有很多實(shí)現(xiàn)方式，我們可以參考一下V8官方的文檔；從文檔中我們可以發(fā)現(xiàn)：
之前的sort方法是基于快排，并且是一種不穩(wěn)定的排序算法，后來(lái)V8將sort遷移到了Torque，tq是一種特殊的DSL，利用Timsort算法實(shí)現(xiàn)了穩(wěn)定的排序，Timsort可以看成一種穩(wěn)定的歸并排序
總結(jié)我們先從數(shù)組的20個(gè)方法為切入點(diǎn)，研究了這些方法的ts定義，用法，順便手寫(xiě)模擬了一下它們，然后對(duì)于比較復(fù)雜的sort算法我們了解了一下它的原理，顯然sort算法已經(jīng)不是那個(gè)以前用快排實(shí)現(xiàn)的不穩(wěn)定的排序算法了，現(xiàn)在是一種穩(wěn)定的排序算法，并且基于歸并排序，所以歸并排序我們一定要掌握好；另外這種由淺入深的學(xué)習(xí)方法，值得大家去實(shí)踐。
作者：螞小蟻 https://juejin.cn/post/7216994437246844985
? ?