ECMAScript前端学数据结构之集合

面前的讲话

  本文将详细介绍集合,这是一致栽不允许值更的次第数据结构

 

数据结构

  集合是由于同组无序且唯一(即无可知重新)的起构成的。这个数据结构使用了和简单集合相同之数学概念,但采用在处理器是的数据结构中。

  在深刻学集合的计算机是落实之前,我们事先看她的数学概念。在数学中,集合是均等组不同的对象(的会师)。比如说,一个由于高于或等于于0的平头组成的自然数集合:N={0,1,2,3,4,5,6,…}。集合中的对象列表用“{}”(大括哀号)包围。

  还有一个定义让空集。空集就是免含有其他因素的会师。比如24同29内的素数集合。由于24跟29次从未素数(除了1暨自家,没有其它正因为累的很叫1的自然数),这个集就是空集。空集用“{}”表示

  也足以将集想象变为一个既没有再次元素,也远非各个概念的数组。在数学中,集合也发生并集、交集、差集等基本操作。下面将介绍这些操作

 

创立集合

  下面要兑现之近乎就是坐ECMAScript6挨Set类的兑现呢底蕴之。

  以下是Set类的架子:

function Set() { 
  var items = {};
}

  有一个可怜重大之底细,我们以对象要非是屡组来代表集合(items)。但为可以就此数组实现。
同时,JavaScript的靶子不允许一个键指向星星只不等的性能,也保了集合里的素还是唯一的

  接下去,需要声明一些凑合可用的不二法门(我们见面尝试模拟与ECMAScript
6贯彻同的Set类)

add(value):向集合添加一个新的项。
remove(value):从集合移除一个值。
has(value):如果值在集合中,返回true,否则返回false。
clear():移除集合中的所有项。
size():返回集合所包含元素的数量。与数组的length属性类似。
values():返回一个包含集合中所有值的数组。

【has】

  首先使落实之是has(value)方法。这是因它们见面被add、remove等其它办法调用。

  既然我们运用对象来储存集合的值,就得用JavaScript的in操作符来说明给定的值是否是items对象的属性

  下面看看她的实现:

this.has = function(value){ 
  return value in items;
};

  但以此措施还有更好的兑现方式,所有JavaScript对象还发生hasOwnProperty方法。这个法子返回一个表明对象是不是具有一定属性之布尔值。代码如下:

this.has = function(value){
  return items.hasOwnProperty(value);
};

【add】

  接下要促成add方法:

this.add = function(value){ 
  if (!this.has(value)){
    items[value] = value; //{1} 
    return true;
  }
  return false;
};

  对于给定的value,可以检查她是不是留存于聚集中。如果无在,就管value添加到集结中(行{1}),返回true,表示补加了之价。如果凑中都产生是价,就回false,表示没长它。

  [注意]长一个价值的时光,把它同时作为键和价值保存,因为这样便于查找这价

【remove】

  在remove方法被,我们会证明给定的value是否留存叫聚集中。如果有,就由集合中易除value(行{2}),返回true,表示值为移除;否则回false。

  下面来贯彻remove方法:

this.remove = function(value){ 
  if (this.has(value)){
    delete items[value]; //{2}
    return true;
  }
  return false;
};

  既然用对象来存储集合的items对象,就得省略地动delete操作符从items对象吃移除属性(行{2})

  使用Set类的以身作则代码如下:

var set = new Set(); 
set.add(1);
set.add(2);

  于执行以上代码之后,在控制台(console.log)输出items
变量,Chrome就会见输出如下内容:

 Object {1: 1, 2: 2}

  可以见见,这是一个出一定量独特性之对象。属性名就是长到集结的值,同时其也是属于性值

【clear】

  如果想移除集合中的具备值,可以据此clear方法:

  要重置items对象,需要做的只是把一个空对象还赋值给它(行{3})。我们呢可迭代集合,用remove方法依次移除所有的价,但既然有更简便的道,那样做就是太难为了

this.clear = function(){ 
  items = {}; // {3}
};

【size】

  size方法(返回集合中产生微件)方法来三栽实现方式。
第一种方式是应用一个length变量,每当使用add或remove方法时操其;第二种方式,使用JavaScript内打的Object类的一个内建函数(ECMAScript
5之上版本):

  JavaScript的Object类有一个keys方法,它回到一个包含加对象拥有属性的数组。在这种情景下,可以使这数组的length属性(行{4})来回到items对象的性质个数。以下代码只能于当代浏览器被运行

this.size = function(){
  return Object.keys(items).length; //{4}
};

  第三种办法是手动提取items对象的各个一个属性,记录属性之个数并回到这个数字。这个点子可以于其它浏览器上运行,和前的代码是等价格的:

  全历items对象的富有属性(行{5}),检查其是不是是目标自我之习性(避免再计数——
行{6})。如果是,就与日俱增count变量的价(行{7}),最后以点子了时返回这个数字

  [注意]未可知大概地用for-in语词遍历items对象的习性,递增count变量的值。
还需要利用has方法(以验证items对象拥有该属性),因为对象的原型包含了附加的习性(属性既来持续自JavaScript的Object类的,也来属于对象自我,未用于数据结构的)

this.sizeLegacy = function(){ 
  var count = 0;
  for(var prop in items) { //{5}
    if(items.hasOwnProperty(prop)) //{6}
    ++count; //{7}
  }
  return count;
};

【values】

  values方法也动了平的逻辑,提取items对象的备属性,以数组的款型返回:

this.values = function(){
 let values = [];
 for (let i=0, keys=Object.keys(items); i<keys.length; i++) {
  values.push(items[keys[i]]);
 }
 return values;
};

  以上代码只能于现世浏览器被运行

  如果想吃代码在另浏览器中还能够实行,可以就此同之前代码等的下边就段代码:

this.valuesLegacy = function(){
 let values = [];
 for(let key in items) { //{7}
  if(items.hasOwnProperty(key)) { //{8}
    values.push(items[key]);
  }
 }
 return values;
};

  所以,首先遍历items对象的备属性(行{7}),把其增长一个数组中(行{8}),并返回这个数组。该办法类似于sizeLegacy方法,但我们抬高一个再三组,而未是测算属性个数

【使用Set类】

  数据结构已经形成了,下面来尝试着执行有下令,测试我们的Set类:

var set = new Set(); 
set.add(1);
console.log(set.values()); //输出["1"]
console.log(set.has(1)); //输出true
console.log(set.size()); //输出1
set.add(2);
console.log(set.values()); //输出["1", "2"]
console.log(set.has(2)); //true 
console.log(set.size()); //2
set.remove(1); 
console.log(set.values()); //输出["2"]
set.remove(2); 
console.log(set.values()); //输出[]

  现在咱们来了一个暨ECMAScript6遇充分相近的Set类实现

 

会师操作

  对聚集好开展如下操作

  1、并集结:对于给定的星星点点单集,返回一个含两独聚众中所有因素的新集

  2、交集:对于给定的片个集,返回一个暗含两只集聚中共有素的新集

  3、差集:对于给定的星星点点只聚众,返回一个蕴含有存在为第一个集合且不在吃次只聚众的元素的新集

  4、子集:验证一个加以集合是否是其它一样聚众的子集

【并集】

  并集的数学概念是集合A和B的并集,表示也A∪B,定义如下:

A∪B = { x | x ∈ A∨x ∈ B }

  意思是x(元素)存在于A中,或x存在于B中。下图展示了并集操作:

  现在来落实Set类的union方法:

  首先用创造一个初的成团,代表个别单聚众的并集(行{1})。接下来,获取第一个集(当前底Set类实例)所有的价值(values),遍历并尽抬高到代表并集的集中(行{2})。然后对第二独聚众做一样的行(行{3})。最后回到结果

this.union = function(otherSet){
 let unionSet = new Set(); //{1}
 let values = this.values(); //{2}
 for (let i=0; i<values.length; i++){
  unionSet.add(values[i]);
 }
 values = otherSet.values(); //{3}
 for (let i=0; i<values.length; i++){
   unionSet.add(values[i]);
 }
 return unionSet;
};

  测试一下地方的代码:

var setA = new Set(); 
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

var unionAB = setA.union(setB);
console.log(unionAB.values());

  输出为[“1”, “2”, “3”, “4”, “5”,
“6”]。注意元素3而在为AB饱受,它当结果的 集合中只现出同差

【交集】

  交集的数学概念是集合A和B的交集,表示为A∩B,定义如下:

A∩B = { x | x ∈ A∧x ∈ B }

  意思是x(元素)存在叫A中,且x存在让B中。下图展示了交集操作:

  现在来兑现Set类的intersection方法:

  intersection方法需要找到时Set实例中,所有有让为定Set实例中之元素。首先创建一个初的Set实例,这样即使能够用她回到共有的元素(行{1})。接下来,遍历当前Set实例所有的价(行{2}),验证其是不是为在于otherSet实例(行{3})。可以用前实现之has方法来验证元素是否存在于Set实例中。然后,如果这个价为在叫外一个Set实例中,就将该加加到创建的intersectionSet变量中(行{4}),最后回来其。

this.intersection = function(otherSet){
 let intersectionSet = new Set(); //{1}
 let values = this.values();
 for (let i=0; i<values.length; i++){ //{2}
  if (otherSet.has(values[i])){ //{3}
    intersectionSet.add(values[i]); //{4}
  }
 }
 return intersectionSet;
}

  测试一下面的代码:

var setA = new Set(); 
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set(); 
setB.add(2);
setB.add(3);
setB.add(4);

var intersectionAB = setA.intersection(setB); 
console.log(intersectionAB.values());

  输出为[“2”, “3”],因为2及3以有于简单单集聚中

【差集】

  差集的数学概念,集合AB的差集,表示为AB,定义如下:

  意思是x(元素)存在于A中,且x不有吃B受。下图展示了集聚AB的差集操作:

  现在来兑现Set类的difference方法:

  intersection方法会得到所有以有让片独聚众中之价值。而difference方法会得到有在吃集合A但不存在于B的价值。因此就有限个措施以促成上唯一的分就是推行{3}。只落不在于otherSet实例中的价,而未是也有让中的价值。行{1}、{2}和{4}是完全相同的

this.intersection = function(otherSet){
 let intersectionSet = new Set(); //{1}
 let values = this.values();
 for (let i=0; i<values.length; i++){ //{2}
  if (!otherSet.has(values[i])){ //{3}
    intersectionSet.add(values[i]); //{4}
  }
 }
 return intersectionSet;
}

  测试一下端的代码:

var setA = new Set(); 
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set(); 
setB.add(2);
setB.add(3);
setB.add(4);

var differenceAB = setA.difference(setB); 
console.log(differenceAB.values());

  输出为[“1”],因为1是绝无仅有一个仅在于setA的元素

【子集】

  子集的数学概念是集合A是B的子集(或集合B包含了A),表示也A⊆B,定义如下:

∀x { x ∈ A → x ∈ B }

  意思是集合A中之各一个x(元素),也得是为B中。下图显示了集合A是集合B的子集:

  现在来兑现Set类的subset方法:

  首先需要证实的是时下Set实例的轻重缓急。如果手上实例中之因素比otherSet实例更多,它就是非是一个子集(行{1})。子集的素个数需要小于或等于要比较的成团。

  接下去要遍历集合中之有着因素(行{2}),验证这些因素也是于otherSet中(行{3})。如果发生其他因素不在于otherSet中,就意味着它们不是一个子集,返回false(行{4})。如果具有因素还是于otherSet中,行{4}就未会见吃执行,那么即便回来true(行{5})。

this.subset = function(otherSet){
 if (this.size() > otherSet.size()){ //{1}
  return false;
 } else {
  let values = this.values();
  for (let i=0; i<values.length; i++){ //{2}
    if (!otherSet.has(values[i])){ //{3}
      return false; //{4}
    }
  }
  return true; //{5}
 }
};

  检验一下上面的代码效果怎么样:

var setA = new Set(); 
setA.add(1);
setA.add(2);

var setB = new Set(); 
setB.add(1);
setB.add(2);
setB.add(3);

var setC = new Set(); 
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.subset(setB)); 
console.log(setA.subset(setC));

  我们发三单集:setA是setB的子集(因此输出为true),然而setA不是setC的子集(setC
只含了setA中之2,而休分包1),因此输出为false

【完整代码】

  关于集合的完全代码如下

function Set() {

    let items = {};

    this.add = function(value){
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };

    this.delete = function(value){
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };

    this.has = function(value){
        return items.hasOwnProperty(value);
        //return value in items;
    };

    this.clear = function(){
        items = {};
    };

    /**
     * Modern browsers function
     * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
     * @returns {Number}
     */
    this.size = function(){
        return Object.keys(items).length;
    };

    /**
     * cross browser compatibility - legacy browsers
     * for modern browsers use size function
     * @returns {number}
     */
    this.sizeLegacy = function(){
        let count = 0;
        for(let key in items) {
            if(items.hasOwnProperty(key))
                ++count;
        }
        return count;
    };

    /**
     * Modern browsers function
     * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
     * @returns {Array}
     */
    this.values = function(){
        let values = [];
        for (let i=0, keys=Object.keys(items); i<keys.length; i++) {
            values.push(items[keys[i]]);
        }
        return values;
    };

    this.valuesLegacy = function(){
        let values = [];
        for(let key in items) {
            if(items.hasOwnProperty(key)) {
                values.push(items[key]);
            }
        }
        return values;
    };

    this.getItems = function(){
      return items;
    };

    this.union = function(otherSet){
        let unionSet = new Set(); //{1}

        let values = this.values(); //{2}
        for (let i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        values = otherSet.values(); //{3}
        for (let i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        return unionSet;
    };

    this.intersection = function(otherSet){
        let intersectionSet = new Set(); //{1}

        let values = this.values();
        for (let i=0; i<values.length; i++){ //{2}
            if (otherSet.has(values[i])){    //{3}
                intersectionSet.add(values[i]); //{4}
            }
        }

        return intersectionSet;
    };

    this.difference = function(otherSet){
        let differenceSet = new Set(); //{1}

        let values = this.values();
        for (let i=0; i<values.length; i++){ //{2}
            if (!otherSet.has(values[i])){    //{3}
                differenceSet.add(values[i]); //{4}
            }
        }

        return differenceSet;
    };

    this.subset = function(otherSet){

        if (this.size() > otherSet.size()){ //{1}
            return false;
        } else {
            let values = this.values();
            for (let i=0; i<values.length; i++){ //{2}
                if (!otherSet.has(values[i])){    //{3}
                    return false; //{4}
                }
            }
            return true;
        }
    };
}

【ES6】

  ES6本的代码如下

let Set2 = (function () {

    const items = new WeakMap();

    class Set2 {

        constructor () {
            items.set(this, {});
        }

        add(value){
            if (!this.has(value)){
                let items_ = items.get(this);
                items_[value] = value;
                return true;
            }
            return false;
        }

        delete(value){
            if (this.has(value)){
                let items_ = items.get(this);
                delete items_[value];
                return true;
            }
            return false;
        }

        has(value){
            let items_ = items.get(this);
            return items_.hasOwnProperty(value);
        }

        clear(){
            items.set(this, {});
        }

        size(){
            let items_ = items.get(this);
            return Object.keys(items_).length;
        }


        values(){
            let values = [];
            let items_ = items.get(this);
            for (let i=0, keys=Object.keys(items_); i<keys.length; i++) {
                values.push(items_[keys[i]]);
            }
            return values;
        }

        getItems(){
            return items.get(this);
        }

        union(otherSet){
            let unionSet = new Set();

            let values = this.values();
            for (let i=0; i<values.length; i++){
                unionSet.add(values[i]);
            }

            values = otherSet.values();
            for (let i=0; i<values.length; i++){
                unionSet.add(values[i]);
            }

            return unionSet;
        }

        intersection(otherSet){
            let intersectionSet = new Set();

            let values = this.values();
            for (let i=0; i<values.length; i++){
                if (otherSet.has(values[i])){
                    intersectionSet.add(values[i]);
                }
            }

            return intersectionSet;
        }

        difference(otherSet){
            let differenceSet = new Set();

            let values = this.values();
            for (let i=0; i<values.length; i++){
                if (!otherSet.has(values[i])){
                    differenceSet.add(values[i]);
                }
            }

            return differenceSet;
        };

        subset(otherSet){

            if (this.size() > otherSet.size()){
                return false;
            } else {
                let values = this.values();
                for (let i=0; i<values.length; i++){
                    if (!otherSet.has(values[i])){
                        return false;
                    }
                }
                return true;
            }
        };
    }
    return Set2;
})();

 

ES6

  ECMAScript 2015增产了Set类。我们得基于ES6的Set开发我们的Set类

  和咱们的Set不同,ES6的Set的values方法返回Iterator,而休是价值构成的数组。另一个有别于是,我们落实之size方法返回set中贮存的价值的个数,而ES6的Set则有一个size属性

let set = new Set();
set.add(1);
console.log(set.values()); // 输出@Iterator
console.log(set.has(1)); // 输出true
console.log(set.size); // 输出1 

  可以就此delete方法去set中之要素:

set.delete(1); 

  clear方法会重置set数据结构,这和我们兑现之功能雷同

【集合】

  我们的Set类实现了并集、交集、差集、子集等数学操作,然而ES6原生的Set并无这些意义

  我们可创造一个初的聚合,用来补偿加点儿个集中装有的元素(行{1})。迭代就点儿只集聚(行{2}、行{3}),把具备因素还增长到并集的汇聚中。代码如下:

let unionAb = new Set(); //{1}
for (let x of setA) unionAb.add(x); //{2}
for (let x of setB) unionAb.add(x); //{3} 

  模拟交集操作需要创造一个声援函数,来十分成包含setA和setB都有的元素的初集(行
{1})。代码如下:

let intersection = function(setA, setB) {
 let intersectionSet = new Set();
 for (let x of setA) {
   if (setB.has(x)) { //{1}
     intersectionSet.add(x);
   }
 }
 return intersectionSet;
};
let intersectionAB = intersection(setA, setB); 

  交集可以就此重新简单的语法实现,代码如下:

intersectionAb = new Set([x for (x of setA) if (setB.has(x))]); 

  这同intersection函数的效应完全同

  交集操作创建的聚众包含setA和setB都有些元素,差集操作创建的会师包含的则是setA有
而setB没有的要素。看下的代码:

let difference = function(setA, setB) {
 let differenceSet = new Set();
 for (let x of setA) {
     if (!setB.has(x)) { //{1}
         differenceSet.add(x);
     }
 }
 return differenceSet;
};
let differenceAB = difference(setA, setB); 

  intersection函数和difference函数只发实施{1}不同,因为不同集中只补充加setA有要setB
没有底要素

  差集也可用更简约的语法实现,代码如下:

differenceAB = new Set([x for (x of setA) if (!setB.has(x))]); 

【set代码】

  基于ES6的set开发之切近的完全代码如下

let set = new Set();

//--------- Union ----------
let unionAb = new Set();
for (let x of setA) unionAb.add(x);
for (let x of setB) unionAb.add(x);

//--------- Intersection ----------
let intersection = function(setA, setB){
    let intersectionSet = new Set();

    for (let x of setA){
        if (setB.has(x)){
            intersectionSet.add(x);
        }
    }

    return intersectionSet;
};
let intersectionAB = intersection(setA, setB);
//alternative - works on FF only
//intersectionAb = new Set([x for (x of setA) if (setB.has(x))]);

//--------- Difference ----------
let difference = function(setA, setB){
    let differenceSet = new Set();

    for (let x of setA){
        if (!setB.has(x)){
            differenceSet.add(x);
        }
    }

    return differenceSet;
};
let differenceAB = difference(setA, setB);
//alternative  - works on FF only
//differenceAB = new Set([x for (x of setA) if (!setB.has(x))]);