CODEWITHSUNDEEP
javascriptobjectdata-structuresset
AshleysBrain
AshleysBrain

Reputation: 22591

Set of objects in javascript

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?

Upvotes: 83

Views: 148498

Answers (13)

felipeaf
felipeaf

Reputation: 404

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

Upvotes: 1

ghostinpeace
ghostinpeace

Reputation: 73

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.

Upvotes: 1

Rui Marques
Rui Marques

Reputation: 8904

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

Upvotes: 2

Sun Higuchi
Sun Higuchi

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

Upvotes: -2

ENcy
ENcy

Reputation: 414

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

Upvotes: 17

Ry-
Ry-

Reputation: 224857

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

Upvotes: 46

Ciro Santilli OurBigBook.com
Ciro Santilli OurBigBook.com

Reputation: 382572

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

Upvotes: 4

Aurelien
Aurelien

Reputation: 281

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

Upvotes: 0

Jim Blackler
Jim Blackler

Reputation: 23169

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

Upvotes: 26

AshleysBrain
AshleysBrain

Reputation: 22591

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

Upvotes: 11

Sophistifunk
Sophistifunk

Reputation: 5032

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

Upvotes: 0

user578895
user578895

Reputation:

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

Upvotes: 9

Vivin Paliath
Vivin Paliath

Reputation: 95508

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

Upvotes: 4

Related Questions