CODEWITHSUNDEEP
javascriptdata-structuresset
Tim Molendijk
Tim Molendijk

Reputation: 1046

Does JavaScript have an implementation of a set data structure?

I'm looking for a decent implementation of a set data structure in JavaScript. It should be able to support elements that are plain JavaScript objects.

So far I only found Closure Library's structs.Set, but I don't like the fact that it modifies my data.

Upvotes: 36

Views: 33189

Answers (6)

Tim Down
Tim Down

Reputation: 324567

You could build a simple wrapper around the keys of a hash table provided by my jshashtable. I have one knocking around somewhere that I will dig out later.

UPDATE

I have completed and tested an implementation of HashSet and uploaded it to the jshashtable project on GitHub. You can download it or view the source.

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2

Upvotes: 13

Salvador Dali
Salvador Dali

Reputation: 222531

In ES6 version of Javascript you have built in type for set (check compatibility with your browser).

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

To add an element to 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)

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

To check the number of elements in the set, you can simply use .size. Also runs in O(1)

numbers.size; // 4

To remove the element from the set use .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).

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

To check whether the element exist in a set use .has(), which returns true if the element is in the set and false otherwise. Also runs in 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 set
  • numbers.forEach(callback); iterating through the values of the set in insertion order
  • numbers.entries(); create an iterator of all the values
  • numbers.keys(); returns the keys of the set which is the same as numbers.values()

There is also a Weakset which allows to add only object-type values.

Upvotes: 3

CommonSenseCode
CommonSenseCode

Reputation: 25369

Use the ECMAScript 2015 (ES6) standard Set Data structure really easy to use:

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

mySet.has(1); // true
mySet.has(3); // false, 3 has not been added to the set
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has("Some Text".toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 4

mySet.delete(5); // removes 5 from the set
mySet.has(5);    // false, 5 has been removed

mySet.size; // 3, we just removed one value

Update for those using AngularJs

Be aware that sets don't work with ng-repeat. So it is better you use an array and just apply a unique filter

Upvotes: 2

Ciro Santilli OurBigBook.com
Ciro Santilli OurBigBook.com

Reputation: 382802

ECMAScript 6 has it

Spec: http://www.ecma-international.org/ecma-262/6.0/#sec-set-constructor

Usage: https://github.com/lukehoban/es6features#map--set--weakmap--weakset

Example:

var s = new Set()
s.add("hello").add("goodbye").add("hello")
s.size === 2
s.has("hello") === true

A module that implements it for browsers without support: https://github.com/medikoo/es6-set

Upvotes: 25

Lukas
Lukas

Reputation: 9845

I like Simple-JS-Set (probably because I wrote it). It supports any sort of JavaScript object. It has the following API:

  • Set(hashFunction): (Constructor) Instantiate a new set with the given hashFunction (defaults to JSON.stringify)
  • add(item): Add an item to the set
  • remove(item): Remove an item from the set
  • contains(item): Return whether or not the item is contained in the set
  • size(): Return the number of unique items in the set
  • each(function(item), thisObj): Execute a function with each item in the set in context of thisObj

Upvotes: 1

user187291
user187291

Reputation: 53940

I don't think there's a way to work with object's hash code other than store it in the object itself. Strictly speaking, it's possible to create a set class without hashing, using simple linear search, but this would hardly be efficient.

Upvotes: 2

Related Questions