模仿JavaScript中的集?

我正在使用JavaScript。 我想存储一个唯一的 ,无序的字符串值的列表,具有以下属性:

  1. 一个快速的方式来问'是列表中的A'?
  2. 一个快速的方法来做'从列表中删除A,如果它存在于列表中'
  3. 一个快速的方法来做'添加到列表,如果它不存在'。

我真正想要的是一套。 任何建议在JavaScript模仿一套最好的方法?

这个问题建议使用一个对象 ,存储属性的键和所有的值设置为true:这是一个明智的方法?

如果您在具有ES6功能的环境(如node.js,具有所需的ES6功能的特定浏览器,或者为您的环境转换ES6代码的特定浏览器)进行编程,则可以使用ES6中内置的Set对象 。 它具有非常好的功能,可以在您的环境中正确使用。


对于ES5环境中的很多简单的事情来说,使用对象工作得非常好。 如果obj是你的对象,而A是一个变量,它具有你想在集合中操作的值,那么你可以这样做:

初始化代码:

 // create empty object var obj = {}; // or create an object with some items already in it var obj = {"1":true, "2":true, "3":true, "9":true}; 

问题1:列表中是否是A

 if (A in obj) { // put code here } 

问题2:如果在列表中,从列表中删除“A”:

 delete obj[A]; 

问题3:如果列表中没有“A”,则添加“A”

 obj[A] = true; 

为了完整性,测试A是否在列表中是有点安全的:

 if (Object.prototype.hasOwnProperty.call(obj, A)) // put code here } 

因为内建方法和/或基础对象(如constructor属性)上的属性之间可能存在冲突。


ES6上的补充工具栏: ECMAScript 6或ES 2015的当前工作版本有一个内置的Set对象 。 它现在在一些浏览器中实现。 由于浏览器可用性随时间而改变,因此您可以查看此ES6兼容性表中的“ Set ”行,以查看浏览器可用性的当前状态。

内置的Set对象的一个​​优点是它并不像Object那样强制所有的字符串,所以你可以同时使用5和“5”作为单独的键。 而且,甚至可以直接在集合中使用对象,而无需字符串转换。 这里有一篇介绍Set对象的一些功能和MDN文档 的文章 。

现在我已经为ES6设置对象编写了一个polyfill,因此您现在可以开始使用它,如果浏览器支持,它将自动推迟到内置的set对象。 这有一个好处,就是你正在写ES6兼容的代码,可以一直工作到IE7。 但是,有一些缺点。 ES6的设置界面利用了ES6的迭代器,所以你可以做一些事情for (item of mySet) ,它会自动迭代你的设置。 但是,这种类型的语言功能不能通过polyfill实现。 您仍然可以在不使用新的ES6语言功能的情况下迭代ES6集合,但坦率地说,没有新的语言功能,它不如下面包含的其他集合接口那么方便。

看完两者后,你可以决定哪一个最适合你。 ES6设置填充在这里: https : //github.com/jfriend00/ES6-Set 。

仅供参考,在我自己的测试中,我注意到Firefox v29集的实现并不完全符合当前草案的最新版本。 例如,您不能链接.add()方法调用,如spec描述和我的polyfill支持。 这可能是一个议案的问题,因为它还没有最终确定。


预构建集对象:如果您希望已经构建的对象具有可在任何浏览器中使用的集合的操作方法,则可以使用一系列不同的预构建对象来实现不同类型的集合。 有一个miniSet,它是实现一个set对象的基础的小代码。 它还有一个功能更丰富的设置对象和几个派生,包括一个字典(让我们为每个键存储/检索一个值)和一个ObjectSet(让我们保留一组对象 – 要么提供的JS对象或DOM对象函数为每个函数生成一个唯一的键,或者ObjectSet将为您生成键)。

这里是miniSet代码的副本(最新的代码在github上 )。

 "use strict"; //------------------------------------------- // Simple implementation of a Set in javascript // // Supports any element type that can uniquely be identified // with its string conversion (eg toString() operator). // This includes strings, numbers, dates, etc... // It does not include objects or arrays though // one could implement a toString() operator // on an object that would uniquely identify // the object. // // Uses a javascript object to hold the Set // // This is a subset of the Set object designed to be smaller and faster, but // not as extensible. This implementation should not be mixed with the Set object // as in don't pass a miniSet to a Set constructor or vice versa. Both can exist and be // used separately in the same project, though if you want the features of the other // sets, then you should probably just include them and not include miniSet as it's // really designed for someone who just wants the smallest amount of code to get // a Set interface. // // s.add(key) // adds a key to the Set (if it doesn't already exist) // s.add(key1, key2, key3) // adds multiple keys // s.add([key1, key2, key3]) // adds multiple keys // s.add(otherSet) // adds another Set to this Set // s.add(arrayLikeObject) // adds anything that a subclass returns true on _isPseudoArray() // s.remove(key) // removes a key from the Set // s.remove(["a", "b"]); // removes all keys in the passed in array // s.remove("a", "b", ["first", "second"]); // removes all keys specified // s.has(key) // returns true/false if key exists in the Set // s.isEmpty() // returns true/false for whether Set is empty // s.keys() // returns an array of keys in the Set // s.clear() // clears all data from the Set // s.each(fn) // iterate over all items in the Set (return this for method chaining) // // All methods return the object for use in chaining except when the point // of the method is to return a specific value (such as .keys() or .isEmpty()) //------------------------------------------- // polyfill for Array.isArray if(!Array.isArray) { Array.isArray = function (vArg) { return Object.prototype.toString.call(vArg) === "[object Array]"; }; } function MiniSet(initialData) { // Usage: // new MiniSet() // new MiniSet(1,2,3,4,5) // new MiniSet(["1", "2", "3", "4", "5"]) // new MiniSet(otherSet) // new MiniSet(otherSet1, otherSet2, ...) this.data = {}; this.add.apply(this, arguments); } MiniSet.prototype = { // usage: // add(key) // add([key1, key2, key3]) // add(otherSet) // add(key1, [key2, key3, key4], otherSet) // add supports the EXACT same arguments as the constructor add: function() { var key; for (var i = 0; i < arguments.length; i++) { key = arguments[i]; if (Array.isArray(key)) { for (var j = 0; j < key.length; j++) { this.data[key[j]] = key[j]; } } else if (key instanceof MiniSet) { var self = this; key.each(function(val, key) { self.data[key] = val; }); } else { // just a key, so add it this.data[key] = key; } } return this; }, // private: to remove a single item // does not have all the argument flexibility that remove does _removeItem: function(key) { delete this.data[key]; }, // usage: // remove(key) // remove(key1, key2, key3) // remove([key1, key2, key3]) remove: function(key) { // can be one or more args // each arg can be a string key or an array of string keys var item; for (var j = 0; j < arguments.length; j++) { item = arguments[j]; if (Array.isArray(item)) { // must be an array of keys for (var i = 0; i < item.length; i++) { this._removeItem(item[i]); } } else { this._removeItem(item); } } return this; }, // returns true/false on whether the key exists has: function(key) { return Object.prototype.hasOwnProperty.call(this.data, key); }, // tells you if the Set is empty or not isEmpty: function() { for (var key in this.data) { if (this.has(key)) { return false; } } return true; }, // returns an array of all keys in the Set // returns the original key (not the string converted form) keys: function() { var results = []; this.each(function(data) { results.push(data); }); return results; }, // clears the Set clear: function() { this.data = {}; return this; }, // iterate over all elements in the Set until callback returns false // myCallback(key) is the callback form // If the callback returns false, then the iteration is stopped // returns the Set to allow method chaining each: function(fn) { this.eachReturn(fn); return this; }, // iterate all elements until callback returns false // myCallback(key) is the callback form // returns false if iteration was stopped // returns true if iteration completed eachReturn: function(fn) { for (var key in this.data) { if (this.has(key)) { if (fn.call(this, this.data[key], key) === false) { return false; } } } return true; } }; MiniSet.prototype.constructor = MiniSet; 

你可以创建一个没有属性的对象

 var set = Object.create(null) 

它可以作为一个集合,并消除了使用hasOwnProperty的需要。


 var set = Object.create(null); // create an object with no properties if (A in set) { // 1. is A in the list // some code } delete set[a]; // 2. delete A from the list if it exists in the list set[A] = true; // 3. add A to the list if it is not already present 

从ECMAScript 6开始,Set数据结构是一个内置的特性 。 与node.js版本的兼容性可以在这里找到。

在ES6版本的Javascript中,您已经内置了类型( 与您的浏览器兼容 )。

 var numbers = new Set([1, 2, 4]); // Set {1, 2, 4} 

添加元素到集合中,只需使用在O(1)运行的.add() ,并添加要设置的元素(如果不存在),或者如果已经存在,则不执行任何操作。 你可以添加任何类型的元素(数组,字符串,数字)

 numbers.add(4); // Set {1, 2, 4} numbers.add(6); // Set {1, 2, 4, 6} 

检查集合中元素的数量 ,可以简单地使用.size 。 也运行在O(1)

 numbers.size; // 4 

要从设置中删除元素,请使用.delete() 。 如果值存在(并被删除),则返回true;如果值不存在,则返回false。 也运行在O(1)

 numbers.delete(2); // true numbers.delete(2); // false 

检查元素是否存在于set中,使用.has() ,如果元素在set中则返回true,否则返回false。 也运行在O(1)

 numbers.has(3); // false numbers.has(1); // true 

除了你想要的方法之外,还有几个额外的方法:

  • numbers.clear(); 只会删除集合中的所有元素
  • numbers.forEach(callback); 按照插入顺序迭代集合的值
  • numbers.entries(); 创建所有值的迭代器
  • numbers.keys(); 返回与numbers.values()相同的集合的键

还有一个Weakset允许只添加对象类型的值。

我已经开始使用数字和字符串的集合的实现。 我主要关注的是差异化操作,所以我尽可能提高效率。 叉和代码评论,欢迎!

https://github.com/mcrisc/SetJS

我只是注意到d3.js库已经实现了集合,地图和其他数据结构。 我不能争论他们的效率,但是由于这是一个受欢迎的图书馆,它一定是你所需要的。

文档在这里

为了方便,我从链接复制(前3个功能是感兴趣的)


  • d3.set([数组])

构造一个新的集合。 如果指定了数组,则将给定的字符串值数组添加到返回的集合中。

  • set.has(值)

当且仅当此集合具有指定值字符串的条目时才返回true。

  • set.add(值)

将指定的值字符串添加到此集合。

  • set.remove(值)

如果该集合包含指定的值字符串,则将其删除并返回true。 否则,这个方法什么也不做,并返回false。

  • set.values()

返回此集合中字符串值的数组。 返回值的顺序是任意的。 可以用作计算一组字符串的唯一值的便捷方式。 例如:

d3.set([“foo”,“bar”,“foo”,“baz”])。 //“foo”,“bar”,“baz”

  • set.forEach(功能)

为此集合中的每个值调用指定的函数,将该值作为参数传递。 这个函数的上下文是这个集合。 返回undefined。 迭代顺序是任意的。

  • set.empty()

当且仅当此集合具有零值时返回true。

  • set.size()

返回此集合中的值的数量。

是的,这是一个明智的方式 – 这是一个对象(好,这个用例) – 一堆键/值直接访问。

在添加它之前,您需要检查它是否已经存在,或者只需要指示存在,“添加”它实际上不会改变任何内容,只是将其重新设置在对象上。