模仿 JavaScript 中的集合？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7958292/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Mimicking sets in JavaScript?
提问by Richard
I'm working in JavaScript. I'd like to store a list of unique, unordered string values, with the following properties:
我在 JavaScript 中工作。我想存储一个唯一的、无序的字符串值列表，具有以下属性：
- a fast way to ask 'is A in the list'?
- a fast way to do 'delete A from the list if it exists in the list'
- a fast way to do 'add A to the list if it is not already present'.
- 一种快速询问“列表中是否有 A”的方法？
- 一种快速执行“如果列表中存在 A 从列表中删除它”的方法
- 一种快速的方法来执行“如果 A 尚不存在，则将其添加到列表中”。
What I really want is a set. Any suggestions for the best way to mimic a set in JavaScript?
我真正想要的是一套。在 JavaScript 中模仿集合的最佳方式有什么建议吗？
This question recommends using an Object, with the keys storing properties, and the values all set to true: is that a sensible way?
这个问题建议使用 Object，键存储属性，值都设置为 true：这是一种明智的方式吗？
回答by jfriend00
If you are programming in an ES6-capable environment (such as node.js, a specific browser with the ES6 capabilities you need or transpiling ES6 code for your environment), then you can use the Setobject built into ES6. It has very nice capabilities and can be used as is right in your environment.
如果您在支持 ES6 的环境中编程（例如 node.js，具有您需要的 ES6 功能的特定浏览器或为您的环境转译 ES6 代码），那么您可以使用SetES6 中内置的对象。它具有非常好的功能，可以在您的环境中正常使用。
For many simple things in an ES5 environment, using an Object works very well. If objis your object and Ais a variable that has the value you want to operate on in the set, then you can do these:
对于 ES5 环境中的许多简单事情，使用 Object 效果很好。如果obj是您的对象并且A是一个变量，该变量具有您要在集合中操作的值，那么您可以执行以下操作：
Initialization code:
初始化代码：
// 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};
Question 1:Is Ain the list:
问题1：是否A在列表中：
if (A in obj) {
// put code here
}
Question 2:Delete 'A' from the list if it's there:
问题 2：从列表中删除“A”，如果它在那里：
delete obj[A];
Question 3:Add 'A' to the list if it wasn't already there
问题 3：如果列表中没有“A”，请将其添加到列表中
obj[A] = true;
For completeness, the test for whether Ais in the list is a little safer with this:
为了完整起见，测试是否A在列表中更安全一些：
if (Object.prototype.hasOwnProperty.call(obj, A))
// put code here
}
because of potential conflict between built-in methods and/or properties on the base Object like the constructorproperty.
由于内置方法和/或基本对象（如属性）上的属性之间存在潜在冲突constructor。
Sidebar on ES6:The current working version of ECMAScript 6or somethings called ES 2015 has a built-in Set object. It is implemented now in some browsers. Since browser availability changes over time, you can look at the line for Setin this ES6 compatibility tableto see the current status for browser availability.
ES6 上的侧边栏：ECMAScript 6的当前工作版本或称为 ES 2015 的东西有一个内置的 Set 对象。它现在在某些浏览器中实现。由于浏览器的可用性随时间变化的，你可以看看线Set在此ES6兼容性表，查看浏览器可用性的当前状态。
One advantage of the the built-in Set object is that it doesn't coerce all keys to a string like the Object does so you can have both 5 and "5" as separate keys. And, you can even use Objects directly in the set without a string conversion. Here's an articlethat describes some of the capabilities and MDN's documentationon the Set object.
内置 Set 对象的一个优点是它不会像 Object 那样将所有键强制转换为字符串，因此您可以将 5 和“5”作为单独的键。而且，您甚至可以直接在集合中使用对象，而无需进行字符串转换。这是一篇描述Set 对象的一些功能和MDN 文档的文章。
I have now written a polyfill for the ES6 set object so you could start using that now and it will automatically defer to the built-in set object if the browser supports it. This has the advantage that you're writing ES6 compatible code that will work all the way back to IE7. But, there are some downsides. The ES6 set interface takes advantage of the ES6 iterators so you can do things like for (item of mySet)and it will automatically iterate through the set for you. But, this type of language feature cannot be implemented via polyfill. You can still iterate an ES6 set without using the new ES6 languages features, but frankly without the new language features, it isn't as convenient as the other set interface I include below.
我现在已经为 ES6 set 对象编写了一个 polyfill，所以你现在可以开始使用它，如果浏览器支持它，它会自动遵循内置的 set 对象。这样做的好处是您正在编写 ES6 兼容的代码，这些代码将一直工作到 IE7。但是，也有一些缺点。ES6 set 接口利用了 ES6 迭代器，因此您可以执行类似操作for (item of mySet)，它会自动为您遍历 set。但是，这种语言特性不能通过 polyfill 实现。您仍然可以在不使用新的 ES6 语言特性的情况下迭代 ES6 集，但坦率地说，如果没有新的语言特性，它不如我在下面包含的其他集接口方便。
You can decide which one works best for you after looking at both. The ES6 set polyfill is here: https://github.com/jfriend00/ES6-Set.
您可以在查看两者后决定哪一个最适合您。ES6 set polyfill 在这里：https: //github.com/jfriend00/ES6-Set。
FYI, in my own testing, I've noticed that the Firefox v29 Set implementation is not fully up-to-date on the current draft of the spec. For example, you can't chain .add()method calls like the spec describes and my polyfill supports. This is probably a matter of a specification in motion as it is not yet finalized.
仅供参考，在我自己的测试中，我注意到 Firefox v29 Set 实现在规范的当前草案中并不完全是最新的。例如，您不能.add()像规范描述和我的 polyfill 支持那样链接方法调用。这可能是一个正在制定的规范问题，因为它尚未最终确定。
Pre-Built Set objects:If you want an already built object that has methods for operating on a set that you can use in any browser, you can use a series of different pre-built objects that implement different types of sets. There is a miniSet which is small code that implements the basics of a set object. It also has a more feature rich set object and several derivations including a Dictionary (let's you store/retrieve a value for each key) and an ObjectSet (let's you keep a set of objects - either JS objects or DOM objects where you either supply the function that generates a unique key for each one or the ObjectSet will generate the key for you).
Pre-Built Set 对象：如果您想要一个已经构建的对象，该对象具有可以在任何浏览器中使用的操作集合的方法，您可以使用一系列不同的预构建对象来实现不同类型的集合。有一个 miniSet，它是实现集合对象基础的小代码。它还有一个功能更丰富的集合对象和几个派生，包括一个字典（让你存储/检索每个键的值）和一个 ObjectSet（让你保留一组对象——JS 对象或 DOM 对象，你可以在其中提供为每个人生成唯一密钥的函数或 ObjectSet 将为您生成密钥）。
Here's a copy of the code for the miniSet (most up-to-date code is here on github).
这是 miniSet 的代码副本（最新代码在 github 上）。
"use strict";
//-------------------------------------------
// Simple implementation of a Set in javascript
//
// Supports any element type that can uniquely be identified
// with its string conversion (e.g. 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;
回答by Thorben Croisé
You can create an Object with no properties like
您可以创建一个没有属性的对象，例如
var set = Object.create(null)
which can act as a set and eliminates the need to use hasOwnProperty.
它可以作为一个集合，无需使用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
回答by hymloth
回答by Salvador Dali
In ES6 version of Javascript you have built in type for set(check compatibility with your browser).
在 JavaScript 的 ES6 版本中，您已经为set内置了类型（检查与浏览器的兼容性）。
var numbers = new Set([1, 2, 4]); // Set {1, 2, 4}
To add an elementto the set you simply use .add(), which runs in O(1)and either adds the element to set (if it does not exist) or does nothing if it is already there. You can add element of any type there (arrays, strings, numbers)
要将元素添加到集合中，您只需使用.add()，它运行O(1)并添加要设置的元素（如果它不存在），或者如果它已经存在，则不执行任何操作。您可以在那里添加任何类型的元素（数组、字符串、数字）
numbers.add(4); // Set {1, 2, 4}
numbers.add(6); // Set {1, 2, 4, 6}
To check the number of elementsin the set, you can simply use .size. Also runs in O(1)
要检查集合中元素的数量，您可以简单地使用.size. 也跑进去O(1)
numbers.size; // 4
To remove the element from the setuse .delete(). It returns true if the value was there (and was removed), and false if the value did not exist. Also runs in O(1).
要从集合中删除元素，请使用.delete(). 如果该值存在（并被删除），则返回 true，如果该值不存在，则返回 false。也运行在O(1).
numbers.delete(2); // true
numbers.delete(2); // false
To check whether the element existin a set use .has(), which returns true if the element is in the set and false otherwise. Also runs in O(1).
要检查元素是否存在一组使用.has()，如果元素是集合，否则为false返回true。也运行在O(1).
numbers.has(3); // false
numbers.has(1); // true
In addition to methods you wanted, there are few additional one:
除了您想要的方法之外，还有一些其他方法：
numbers.clear();would just remove all elements from the setnumbers.forEach(callback);iterating through the values of the set in insertion ordernumbers.entries();create an iterator of all the valuesnumbers.keys();returns the keys of the set which is the same asnumbers.values()
numbers.clear();只会从集合中删除所有元素numbers.forEach(callback);按插入顺序迭代集合的值numbers.entries();创建所有值的迭代器numbers.keys();返回与集合相同的键numbers.values()
There is also a Weakset which allows to add only object-type values.
还有一个 Weakset 只允许添加对象类型的值。
回答by mcrisc
I have started an implementation of Sets that currently works pretty well with numbers and strings. My main focus was the difference operation, so I tried to make it as efficient as I could. Forks and code reviews are welcome!
我已经开始了一个 Sets 的实现，它目前在数字和字符串上工作得很好。我的主要关注点是差异化操作，所以我试图让它尽可能高效。欢迎分叉和代码！
回答by kon psych
I just noticed that d3.js library has implementation of sets, maps and other data structures. I can't argue about their efficiency but judging by the fact that it is a popular library it must be what you need.
我刚刚注意到 d3.js 库有集合、映射和其他数据结构的实现。我不能争论它们的效率，但从它是一个流行的库的事实来看，它一定是你需要的。
The documentation is here
文档在这里
For convenience I copy from the link (the first 3 functions are those of interest)
为方便起见，我从链接复制（前 3 个函数是感兴趣的函数）
- d3.set([array])
- d3.set([数组])
Constructs a new set. If array is specified, adds the given array of string values to the returned set.
构造一个新的集合。如果指定了数组，则将给定的字符串值数组添加到返回的集合中。
- set.has(value)
- set.has(值)
Returns true if and only if this set has an entry for the specified value string.
当且仅当此集合具有指定值字符串的条目时，才返回 true。
- set.add(value)
- 设置。添加（值）
Adds the specified value string to this set.
将指定的值字符串添加到此集合。
- set.remove(value)
- set.remove(值)
If the set contains the specified value string, removes it and returns true. Otherwise, this method does nothing and returns false.
如果集合包含指定的值字符串，则将其删除并返回 true。否则，此方法不执行任何操作并返回 false。
- set.values()
- 设置值（）
Returns an array of the string values in this set. The order of the returned values is arbitrary. Can be used as a convenient way of computing the unique values for a set of strings. For example:
返回此集合中字符串值的数组。返回值的顺序是任意的。可用作计算一组字符串的唯一值的便捷方法。例如：
d3.set(["foo", "bar", "foo", "baz"]).values(); // "foo", "bar", "baz"
d3.set(["foo", "bar", "foo", "baz"]).values(); // "foo", "bar", "baz"
- set.forEach(function)
- set.forEach(函数)
Calls the specified function for each value in this set, passing the value as an argument. The this context of the function is this set. Returns undefined. The iteration order is arbitrary.
为该集合中的每个值调用指定的函数，将该值作为参数传递。函数的 this 上下文就是这个集合。返回未定义。迭代顺序是任意的。
- set.empty()
- set.empty()
Returns true if and only if this set has zero values.
当且仅当此集合具有零值时才返回 true。
- set.size()
- 设置大小（）
Returns the number of values in this set.
返回该集合中值的数量。
回答by Dave Newton
Yes, that's a sensible way--that's all an object is (well, for this use-case)--a bunch of keys/values with direct access.
是的，这是一种明智的方式——这就是一个对象（好吧，对于这个用例）——一堆可以直接访问的键/值。
You'd need to check to see if it's already there before adding it, or if you just need to indicate presence, "adding" it again doesn't actually change anything, it just sets it on the object again.
您需要在添加它之前检查它是否已经存在，或者如果您只需要表明存在，再次“添加”它实际上并没有改变任何东西，它只是再次将它设置在对象上。
