70

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?

1

13 Answers 13

40

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

4
  • 26
    new Set([{one: "one"}, {one: "one"}]).size is 2. Shouldn't it be 1?
    – ndtreviv
    Dec 11, 2018 at 12:35
  • 27
    @ndtreviv: No, they’re not the same object. {one: "one"} !== {one: "one"}
    – Ry-
    Dec 11, 2018 at 15:30
  • 9
    You're right. I ended up using lodash's _.uniqWith and _.isEqual to get unique Objects.
    – ndtreviv
    Dec 11, 2018 at 20:34
  • Thank you @ndtreviv! I used uniqueObjects = _.uniqWith(objects, _.isEqual)
    – joerick
    Jan 3, 2020 at 12:24
24

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

3
  • 10
    This is what I keep thinking of, but I really really don't want to do things this way :/
    – Charlie L
    Jul 22, 2017 at 18:05
  • 2
    TypeError: cyclic object value
    – Pacerier
    Jun 14, 2020 at 17:56
  • 3
    Will give false negative results when order of properties in object is different. Dec 7, 2022 at 21:57
11

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;
};
0
9

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';
8
  • 1
    All objects have a toString method inherited from Object.prototype. Assigning the object to a property name will call its toString method anyway, so no need to do so explicitly. You can't guarantee that an object's toString will be unique for all objects, so Sophistifunk's approach is better (i.e. store objects in an array and provide a wrapper with methods to add, retrieve and remove members).
    – RobG
    Apr 14, 2011 at 1:43
  • 1
    @RobG - You're missing the point. The toString() methods I added were so that you could return a unique hash of the current object. In this case, I'm just returning 'foo' and 'bar', but you could easily hash anything else that identifies the object (hence the prototype example). As for your first statement, no... Assigning toString() as a property will call that function, NOT the one it inherits from Object.prototype
    – user578895
    Apr 14, 2011 at 1:46
  • 2
    For all I care, var guid=0; myObj.prototype.toString = function(){ return (this.guid || (this.guid=guid++)); } would work.
    – user578895
    Apr 14, 2011 at 1:50
  • @cwolves - all stored objects will need to have unique names, so better to automate it and keep it private.
    – RobG
    Apr 14, 2011 at 2:10
  • @RobG - if all the objects are the same type, doing it like this is better (see my last guid comment if you wish) as it's O(1) lookups unlike Array.indexOf
    – user578895
    Apr 14, 2011 at 2:14
8

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);
1
  • 1
    Perfect solution.. Thanks
    – Yehya
    Sep 20, 2022 at 13:16
4

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).

4

ECMAScript6 Set should behave like that:

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

2

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);
1

Given an array of the following type:

Array<{ foo: T1, bar: T2 }>

You can build a corresponding dictionary of type:

{ [foo: T1]: Set<T2> }

The look-up for { foo: fooValue, bar: barValue } can be performed as follows:

if (fooValue in dictionary && dictionary[fooValue].has(barValue))

This way we can build what would be an ObjectSet<T1, T2> . If you now have three elements, you can build the following dictionary:

{ [foo: T1]: ObjectSet<T2, T3> }

and extend your ObjectSet to any number of properties by induction.

That is assuming your types can be used as index signatures.

0

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;
}
2
  • 1
    Thanks, but I believe indexOf runs in O(n) time. In the question, I stated I needed better efficiency than that. Apr 14, 2011 at 16:06
  • Sorry, I missed that part of the post :-/ It's pretty much a custom hash function then. Apr 18, 2011 at 0:07
0

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;
}
0

well, there is no native ecmascript class like std::set, where you pass an comparator function. You can implement this data structure, of course, as in any other programming language. But for most use cases i suggest something easier:

  • If your objects have some kind of key or id field, and you want O(1) operations for operations like find/add/update/delete, you should use a map using this id field.
  • If you don't have a key, just want avoid duplications in a collection, you can use map or even set, using JSON.stringify(o, Object.keys(o).sort()) as an id. If you have nested objects or arrays, you should short its items either (i didn't wrote that part).

I wrote a class that can match both:

class ObjectSet {
    constructor(iterable) {
        this.map = new Map()
        if(!iterable) {
            return;
        }
        for(o of iterable) {
            this.map.set(this._getId(o), o);
        }
    }

    _getId(o) {
        return o.id ? o.id :
            JSON.stringify(o, Object.keys(o).sort());
    }

    get(id) {
        return this.map.get(id);
    }

    has(o) {
        return this.map.has(this._getId(o));
    }

    //add or update. Call "add" if you want to match ES6 Set interface
    set(o) {
        this.map.set(this._getId(o), o);
    }

    delete(o) {
        this.map.delete(this._getId(o));
    }

    values() {
        return this.map.values();
    }

    [Symbol.iterator] () {
        return this.values();
    }

    get size() {
        return this.map.size;
    }
}

//first use case example, fast find and update:
let objSet = new ObjectSet();

//add
objSet.set({
    id: 1,
    name: "John",
    age: 30
});
const eric = {
    id: 2,
    name: "Eric",
    age: 27
}
//add
objSet.set(eric)
console.log(objSet.size); //2

//update object of id 2
objSet.set({
    id: 2,
    name: "Eric",
    age: 28
})
console.log(objSet.size); // still 2


for(o of objSet) {
    console.log(o);
}
/*
prints:

{ id: 1, name: 'John Abbot', age: 30 }
{ id: 2, name: 'Eric', age: 28 }
*/

objSet.delete({id: 1});//deletes john
objSet.delete(eric);
console.log(objSet.size);//0


//second use case, lets remove duplicated objects using this class
let points = [
    {
        x: 10,
        y: 40
    },
    {
        x: 10,
        y: 40
    },
    {
        x: 10,
        y: 35
    }
]


//lets remove duplicated objects using ObjectSet:
objSet = new ObjectSet(points);
console.log(o.size);//2
for(o of objSet) {
    console.log(o);
}

//same with set method
objSet.set({
    x: 10,
    y: 35
});
console.log(objSet.size);//still 2
-1

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;
};

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.