ES6 系列之模拟实现一个 Set 数据结构

简介: ES6 提供了新的数据结构 Set。它类似于数组,但是成员的值都是唯一的,没有重复的值。

1.png


基本介绍


ES6 提供了新的数据结构 Set。


它类似于数组,但是成员的值都是唯一的,没有重复的值。


初始化


Set 本身是一个构造函数,用来生成 Set 数据结构。


let set = new Set();
复制代码


Set 函数可以接受一个数组(或者具有 iterable 接口的其他数据结构)作为参数,用来初始化。


let set = new Set([1, 2, 3, 4, 4]);
console.log(set); // Set(4) {1, 2, 3, 4}
set = new Set(document.querySelectorAll('div'));
console.log(set.size); // 66
set = new Set(new Set([1, 2, 3, 4]));
console.log(set.size); // 4
复制代码


属性和方法


操作方法有:


  1. add(value):添加某个值,返回 Set 结构本身。
  2. delete(value):删除某个值,返回一个布尔值,表示删除是否成功。
  3. has(value):返回一个布尔值,表示该值是否为 Set 的成员。
  4. clear():清除所有成员,无返回值。


举个例子:


let set = new Set();
console.log(set.add(1).add(2)); // Set [ 1, 2 ]
console.log(set.delete(2)); // true
console.log(set.has(2)); // false
console.log(set.clear()); // undefined
console.log(set.has(1)); // false
复制代码


之所以每个操作都 console 一下,就是为了让大家注意每个操作的返回值。


遍历方法有:


  1. keys():返回键名的遍历器
  2. values():返回键值的遍历器
  3. entries():返回键值对的遍历器
  4. forEach():使用回调函数遍历每个成员,无返回值


注意 keys()、values()、entries() 返回的是遍历器


let set = new Set(['a', 'b', 'c']);
console.log(set.keys()); // SetIterator {"a", "b", "c"}
console.log([...set.keys()]); // ["a", "b", "c"]
复制代码


let set = new Set(['a', 'b', 'c']);
console.log(set.values()); // SetIterator {"a", "b", "c"}
console.log([...set.values()]); // ["a", "b", "c"]
复制代码


let set = new Set(['a', 'b', 'c']);
console.log(set.entries()); // SetIterator {"a", "b", "c"}
console.log([...set.entries()]); // [["a", "a"], ["b", "b"], ["c", "c"]]
复制代码


let set = new Set([1, 2, 3]);
set.forEach((value, key) => console.log(key + ': ' + value));
// 1: 1
// 2: 2
// 3: 3
复制代码


属性:


  1. Set.prototype.constructor:构造函数,默认就是 Set 函数。
  2. Set.prototype.size:返回 Set 实例的成员总数。


模拟实现第一版


如果要模拟实现一个简单的 Set 数据结构,实现 add、delete、has、clear、forEach 方法,还是很容易写出来的,这里直接给出代码:


/**
 * 模拟实现第一版
 */
(function(global) {
    function Set(data) {
        this._values = [];
        this.size = 0;
        data && data.forEach(function(item) {
            this.add(item);
        }, this);
    }
    Set.prototype['add'] = function(value) {
        if (this._values.indexOf(value) == -1) {
            this._values.push(value);
            ++this.size;
        }
        return this;
    }
    Set.prototype['has'] = function(value) {
        return (this._values.indexOf(value) !== -1);
    }
    Set.prototype['delete'] = function(value) {
        var idx = this._values.indexOf(value);
        if (idx == -1) return false;
        this._values.splice(idx, 1);
        --this.size;
        return true;
    }
    Set.prototype['clear'] = function(value) {
        this._values = [];
        this.size = 0;
    }
    Set.prototype['forEach'] = function(callbackFn, thisArg) {
        thisArg = thisArg || global;
        for (var i = 0; i < this._values.length; i++) {
            callbackFn.call(thisArg, this._values[i], this._values[i], this);
        }
    }
    Set.length = 0;
    global.Set = Set;
})(this)
复制代码


我们可以写段测试代码:


let set = new Set([1, 2, 3, 4, 4]);
console.log(set.size); // 4
set.delete(1);
console.log(set.has(1)); // false
set.clear();
console.log(set.size); // 0
set = new Set([1, 2, 3, 4, 4]);
set.forEach((value, key, set) => {
  console.log(value, key, set.size)
});
// 1 1 4
// 2 2 4
// 3 3 4
// 4 4 4
复制代码


模拟实现第二版


在第一版中,我们使用 indexOf 来判断添加的元素是否重复,本质上,还是使用 === 来进行比较,对于 NaN 而言,因为:


console.log([NaN].indexOf(NaN)); // -1
复制代码


模拟实现的 Set 其实可以添加多个 NaN 而不会去重,然而对于真正的 Set 数据结构:


let set = new Set();
set.add(NaN);
set.add(NaN);
console.log(set.size); // 1
复制代码


所以我们需要对 NaN 这个值进行单独的处理。


处理的方式是当判断添加的值是 NaN 时,将其替换为一个独一无二的值,比如说一个很难重复的字符串类似于 @@NaNValue,当然了,说到独一无二的值,我们也可以直接使用 Symbol,代码如下:


/**
 * 模拟实现第二版
 */
(function(global) {
    var NaNSymbol = Symbol('NaN');
    var encodeVal = function(value) {
        return value !== value ? NaNSymbol : value;
    }
    var decodeVal = function(value) {
        return (value === NaNSymbol) ? NaN : value;
    }
    function Set(data) {
        this._values = [];
        this.size = 0;
        data && data.forEach(function(item) {
            this.add(item);
        }, this);
    }
    Set.prototype['add'] = function(value) {
        value = encodeVal(value);
        if (this._values.indexOf(value) == -1) {
            this._values.push(value);
            ++this.size;
        }
        return this;
    }
    Set.prototype['has'] = function(value) {
        return (this._values.indexOf(encodeVal(value)) !== -1);
    }
    Set.prototype['delete'] = function(value) {
        var idx = this._values.indexOf(encodeVal(value));
        if (idx == -1) return false;
        this._values.splice(idx, 1);
        --this.size;
        return true;
    }
    Set.prototype['clear'] = function(value) {
        ...
    }
    Set.prototype['forEach'] = function(callbackFn, thisArg) {
        ...
    }
    Set.length = 0;
    global.Set = Set;
})(this)
复制代码


写段测试用例:


let set = new Set([1, 2, 3]);
set.add(NaN);
console.log(set.size); // 3
set.add(NaN);
console.log(set.size); // 3
复制代码


模拟实现第三版


在模拟实现 Set 时,最麻烦的莫过于迭代器的实现和处理,比如初始化以及执行 keys()、values()、entries() 方法时都会返回迭代器:


let set = new Set([1, 2, 3]);
console.log([...set]); // [1, 2, 3]
console.log(set.keys()); // SetIterator {1, 2, 3}
console.log([...set.keys()]); // [1, 2, 3]
console.log([...set.values()]); // [1, 2, 3]
console.log([...set.entries()]); // [[1, 1], [2, 2], [3, 3]]
复制代码


而且 Set 也支持初始化的时候传入迭代器:


let set = new Set(new Set([1, 2, 3]));
console.log(set.size); // 3
复制代码


当初始化传入一个迭代器的时候,我们可以根据我们在上一篇 《ES6 系列之迭代器与 for of》中模拟实现的 forOf 函数,遍历传入的迭代器的 Symbol.iterator 接口,然后依次执行 add 方法。


而当执行 keys() 方法时,我们可以返回一个对象,然后为其部署 Symbol.iterator 接口,实现的代码,也是最终的代码如下:


/**
 * 模拟实现第三版
 */
(function(global) {
    var NaNSymbol = Symbol('NaN');
    var encodeVal = function(value) {
        return value !== value ? NaNSymbol : value;
    }
    var decodeVal = function(value) {
        return (value === NaNSymbol) ? NaN : value;
    }
    var makeIterator = function(array, iterator) {
        var nextIndex = 0;
        // new Set(new Set()) 会调用这里
        var obj = {
            next: function() {
                return nextIndex < array.length ? { value: iterator(array[nextIndex++]), done: false } : { value: void 0, done: true };
            }
        };
        // [...set.keys()] 会调用这里
        obj[Symbol.iterator] = function() {
            return obj
        }
        return obj
    }
    function forOf(obj, cb) {
        let iterable, result;
        if (typeof obj[Symbol.iterator] !== "function") throw new TypeError(obj + " is not iterable");
        if (typeof cb !== "function") throw new TypeError('cb must be callable');
        iterable = obj[Symbol.iterator]();
        result = iterable.next();
        while (!result.done) {
            cb(result.value);
            result = iterable.next();
        }
    }
    function Set(data) {
        this._values = [];
        this.size = 0;
        forOf(data, (item) => {
            this.add(item);
        })
    }
    Set.prototype['add'] = function(value) {
        value = encodeVal(value);
        if (this._values.indexOf(value) == -1) {
            this._values.push(value);
            ++this.size;
        }
        return this;
    }
    Set.prototype['has'] = function(value) {
        return (this._values.indexOf(encodeVal(value)) !== -1);
    }
    Set.prototype['delete'] = function(value) {
        var idx = this._values.indexOf(encodeVal(value));
        if (idx == -1) return false;
        this._values.splice(idx, 1);
        --this.size;
        return true;
    }
    Set.prototype['clear'] = function(value) {
        this._values = [];
        this.size = 0;
    }
    Set.prototype['forEach'] = function(callbackFn, thisArg) {
        thisArg = thisArg || global;
        for (var i = 0; i < this._values.length; i++) {
            callbackFn.call(thisArg, this._values[i], this._values[i], this);
        }
    }
    Set.prototype['values'] = Set.prototype['keys'] = function() {
        return makeIterator(this._values, function(value) { return decodeVal(value); });
    }
    Set.prototype['entries'] = function() {
        return makeIterator(this._values, function(value) { return [decodeVal(value), decodeVal(value)]; });
    }
    Set.prototype[Symbol.iterator] = function(){
        return this.values();
    }
    Set.prototype['forEach'] = function(callbackFn, thisArg) {
        thisArg = thisArg || global;
        var iterator = this.entries();
        forOf(iterator, (item) => {
            callbackFn.call(thisArg, item[1], item[0], this);
        })
    }
    Set.length = 0;
    global.Set = Set;
})(this)
复制代码


写段测试代码:


let set = new Set(new Set([1, 2, 3]));
console.log(set.size); // 3
console.log([...set.keys()]); // [1, 2, 3]
console.log([...set.values()]); // [1, 2, 3]
console.log([...set.entries()]); // [1, 2, 3]
复制代码


QUnit


由上我们也可以发现,每当我们进行一版的修改时,只是写了新的测试代码,但是代码改写后,对于之前的测试代码是否还能生效呢?是否不小心改了什么导致以前的测试代码没有通过呢?


为了解决这个问题,针对模拟实现 Set 这样一个简单的场景,我们可以引入 QUnit 用于编写测试用例,我们新建一个 HTML 文件:


<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width">
    <title>Set 的模拟实现</title>
    <link rel="stylesheet" href="qunit-2.4.0.css">
</head>
<body>
    <div id="qunit"></div>
    <div id="qunit-fixture"></div>
    <script src="qunit-2.4.0.js"></script>
    <script src="polyfill-set.js"></script>
    <script src="test.js"></script>
</body>
</html>
复制代码


编写测试用例,因为语法比较简单,我们就直接看编写的一些例子:


QUnit.test("unique value", function(assert) {
    const set = new Set([1, 2, 3, 4, 4]);
    assert.deepEqual([...set], [1, 2, 3, 4], "Passed!");
});
QUnit.test("unique value", function(assert) {
    const set = new Set(new Set([1, 2, 3, 4, 4]));
    assert.deepEqual([...set], [1, 2, 3, 4], "Passed!");
});
QUnit.test("NaN", function(assert) {
    const items = new Set([NaN, NaN]);
    assert.ok(items.size == 1, "Passed!");
});
QUnit.test("Object", function(assert) {
    const items = new Set([{}, {}]);
    assert.ok(items.size == 2, "Passed!");
});
QUnit.test("set.keys", function(assert) {
    let set = new Set(['red', 'green', 'blue']);
    assert.deepEqual([...set.keys()], ["red", "green", "blue"], "Passed!");
});
QUnit.test("set.forEach", function(assert) {
    let temp = [];
    let set = new Set([1, 2, 3]);
    set.forEach((value, key) => temp.push(value * 2) )
    assert.deepEqual(temp, [2, 4, 6], "Passed!");
});
复制代码


用浏览器预览 HTML 页面,效果如下图:


8.png


完整的 polyfill 及 Qunit 源码在 github.com/mqyqingfeng…


ES6 系列


ES6 系列目录地址:github.com/mqyqingfeng…


ES6 系列预计写二十篇左右,旨在加深 ES6 部分知识点的理解,重点讲解块级作用域、标签模板、箭头函数、Symbol、Set、Map 以及 Promise 的模拟实现、模块加载方案、异步处理等内容。


如果有错误或者不严谨的地方,请务必给予指正,十分感谢。如果喜欢或者有所启发,欢迎 star,对作者也是一种鼓励。



目录
相关文章
|
23天前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
25 6
【数据结构】map&set详解
|
1天前
|
存储 安全
【数据结构】Set的使用与注意事项
【数据结构】Set的使用与注意事项
12 2
|
14天前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
15天前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
2月前
|
存储 JavaScript 前端开发
ES6新特性(四): Set 和 Map
ES6新特性(四): Set 和 Map
|
3月前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
43 1
|
3月前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
52 0
|
3月前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
31 0
|
5月前
|
存储 JavaScript
ES6+新特性-Symbol与Set/Map数据结构
ES6 引入了三种新的数据结构:Symbol、Set和Map。Symbol是唯一且不可变的值,常用于定义对象的独特属性;Set存储不重复值,适合数组去重;Map则是键值对集合,键可为任意类型,提供了更灵活的存储方式。这些新数据结构提供了更高效的操作手段,分别解决了属性命名冲突、数据去重和复杂键值对存储的问题。示例展示了如何使用Symbol、Set和Map进行基本操作。
|
4月前
|
缓存 NoSQL 关系型数据库
Redis第二课,1.set key value(设置对应的key和value)2.get key(得到value值)Redis全局命令(支持很多的数据结构)3.keys(用来查询当前
Redis第二课,1.set key value(设置对应的key和value)2.get key(得到value值)Redis全局命令(支持很多的数据结构)3.keys(用来查询当前