Set of objects in javascript - Stack Overflow

admin管理员组

文章数量:1134232

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?

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?

• javascript
• object
• data-structures
• set

Share Improve this question Follow asked Apr 14, 2011 at 0:21 AshleysBrainAshleysBrain 22.6k1616 gold badges9191 silver badges125125 bronze badges 1

• possible duplicate of JavaScript implementation of a set data structure – Ciro Santilli OurBigBook.com Commented Jun 15, 2014 at 15:45

Add a comment  | 

13 Answers 13

Sorted by: Reset to default 46

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

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

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

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

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

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

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

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

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.

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

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

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

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

本文标签： Set of objects in javascriptStack Overflow