Set of objects in javascript

Question

I'd like to have a set of objects in Javascript. That is, a data structure that contains only unique objects.

Normally using properties is recommended, e.g. myset["key"] = true. However, I need the keys to be objects. I've read that Javascript casts property names to strings, so I guess I can't use myset[myobject] = true.

I could use an array, but I need something better than O(n) performance for adding, finding and removing items.

It needs to be able to tell objects apart by reference only, so given:

var a = {};
var b = {};

then both a and b should be able to be added, because they're separate objects.

Basically, I'm after something like C++'s std::set, that can store Javascript objects. Any ideas?

Answer 1

ES6 provides a native Set:

let s = new Set();
let a = {};
let b = {};

s.add(a);

console.log(s.has(a));  // true
console.log(s.has(b));  // false

Answer 2

Here's a mad suggestion ... key it on the result of JSON.stringify(object)

Answer 3

It's not possible for all objects, but if your object has a .toString() method implemented, it is:

var x = {toString: function(){ return 'foo'; }};
var y = {toString: function(){ return 'bar'; }};
var obj = {};
obj[x] = 'X';
obj[y] = 'Y';
console.log(obj);
// { foo: 'X', bar: 'Y' }

If you want to make this easier, make it a class:

function myObj(name){
   this.name = name;
}
myObj.prototype.toString = function(){ return this.name; }

var obj = {};
obj[new myObj('foo')] = 'X';
obj[new myObj('bar')] = 'Y';

Answer 4

I'm answering my own question, but I came up with an alternative solution I thought was interesting and thought it would be useful to share it.

cwolves' answer gave me an idea. Providing an object's toString() method uniquely identifies the instance, properties of an object can be used to store a set of objects. Essentially, to store object x, you can use items[x.toString()] = x;. Note that the value is the object itself, so then the set of objects can be extracted by looking at all item's properties and dumping all the values in to an array.

Here's the class, which I call ObjectSet, in full. It requires objects are uniquely identified by their toString() method, which is OK for my purposes. add, remove and contains should all run in better than O(n) time - whatever javascript's property access efficiency is, which hopefully is either O(1) or O(n log n).

// Set of objects.  Requires a .toString() overload to distinguish objects.
var ObjectSet = function ()
{
    this.items = {};
    this.item_count = 0;
};

ObjectSet.prototype.contains = function (x)
{
    return this.items.hasOwnProperty(x.toString());
};

ObjectSet.prototype.add = function (x)
{
    if (!this.contains(x))
    {
        this.items[x.toString()] = x;
        this.item_count++;
    }

    return this;
};

ObjectSet.prototype.remove = function (x)
{
    if (this.contains(x))
    {
        delete this.items[x.toString()];
        this.item_count--;
    }

    return this;
};

ObjectSet.prototype.clear = function ()
{
    this.items = {};
    this.item_count = 0;

    return this;
};

ObjectSet.prototype.isEmpty = function ()
{
    return this.item_count === 0;
};

ObjectSet.prototype.count = function ()
{
    return this.item_count;
};

ObjectSet.prototype.values = function ()
{
    var i, ret = [];

    for (i in this.items)
    {
        if (this.items.hasOwnProperty(i))
            ret.push(this.items[i]);
    }

    return ret;
};

Answer 5

ECMAScript6 Set should behave like that:

• Standard: http://www.ecma-international.org/ecma-262/6.0/#sec-set-o-p-v-throw
• Unofficial ES6 cheat sheet: https://github.com/lukehoban/es6features#map--set--weakmap--weakset

Working example on Firefox 32 (but not implemented in Chromium 37):

if (Set) {
  var s = new Set()
  var a = {}
  var b = {}
  var c = {}
  s.add(a)
  s.add(b)
  s.add(b)
  assert(s.size === 2)
  assert(s.has(a))
  assert(s.has(b))
  assert(!s.has(c))
}

This is not surprising since {} != {}: equality compares object addresses by default.

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

Answer 6

For what you're trying to do (sets of objects), there is no native Javascript implementation. You would have to implement this on your own. One way to do this would be to implement a hashing function for your objects. The backing data-type of the set would be an associative array, where the key of the array is the value you get from calling the object's hash function, and the value of the array is the object itself.

Of course, this doesn't address the issue that you highlighted, so you will need to take equality into account as well (implement an equals function perhaps)?

Instead of making the hash function a property of the object itself, you can have a standalone hash function that takes in an object as input and generates a hash value (presumably by iterating over its properties).

Using this method you should be able to get O(1) for insertion, searching, and removing (not counting the order of the hash function, which shouldn't be any worse than O(n), especially if you are iterating over its properties to create your hashed value).

Answer 7

I used Map, solved my case

const objectsMap = new Map();
const placesName = [
  { place: "here", name: "stuff" },
  { place: "there", name: "morestuff" },
  { place: "there", name: "morestuff" },
];
placesName.forEach((object) => {
  objectsMap.set(object.place, object);
});
console.log(objectsMap);

Answer 8

It seems that the inner call of function works when prefixed with this. Exemple:

var put;
this.put = put = function(x) {
    if (!this.contains(x))
        list.push(x);

    return this;
}

Answer 9

Just typed this up, it's only briefly tested:

var Set = function Set()
{
    var list = [];

    var contains;
    this.contains = contains = function(x) {
        return list.indexOf(x) >= 0;
    }

    var put;
    this.put = put = function(x) {
        if (!contains(x))
            list.push(x);

        return this;
    }

    var remove;
    this.remove = remove = function(x)
    {
        var idx = list.indexOf(x);
        if (idx >= 0)
            list.splice(idx,1);

        return this;
    }

    var all;
    this.all = all = function()
    {
        return list.concat();
    }

    return this;
}

Answer 10

Please use this code as a reference.

const fruits = [
  {name: 'apple', price: 100},
  {name: 'apple', price: 100},
  {name: 'orange', price: 200},
  {name: 'grapes', price: 300}
];

const hasFruitDuplicated = () => {
  const duplicatedDeleteFruits = fruits.filter((fruit, index) =>
    fruits.findIndex(item => item.name === fruit.name && item.price === fruit.price) === index
  );
  return duplicatedDeleteFruits;
};

Answer 11

Javascript Set's don't do deep object comparison.

Using lodash, this is a unique array with deep object comparison:

const objects = [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }, { 'x': 1, 'y': 2 }];
 
_.uniqWith(objects, _.isEqual);