¿Imitando conjuntos en JavaScript?

Estoy trabajando en JavaScript Me gustaría almacenar una lista de valores de cadena únicos y desordenados, con las siguientes propiedades:

1. ¿Una forma rápida de preguntar 'está A en la lista'?
2. una forma rápida de hacer 'eliminar A de la lista si existe en la lista'
3. una forma rápida de hacer 'agregar A a la lista si aún no está presente'.

Lo que realmente quiero es un set. ¿Alguna sugerencia sobre la mejor manera de imitar un conjunto en JavaScript?

Esta pregunta recomienda el uso de un objeto , con las propiedades de almacenamiento de claves y todos los valores establecidos en verdadero: ¿es esa una manera sensata?

Si está programando en un entorno compatible con ES6 (como node.js, un navegador específico con las capacidades de ES6 que necesita o transpilando el código de ES6 para su entorno), puede usar el Setobjeto integrado en ES6 . Tiene capacidades muy agradables y se puede usar como está en su entorno.

Para muchas cosas simples en un entorno ES5, usar un objeto funciona muy bien. Si objes su objeto y Aes una variable que tiene el valor con el que desea operar en el conjunto, puede hacer lo siguiente:

Código de inicialización:

// create empty object
var obj = {};

// or create an object with some items already in it
var obj = {"1":true, "2":true, "3":true, "9":true};

Pregunta 1: está Aen la lista:

if (A in obj) {
    // put code here
}

Pregunta 2: Eliminar 'A' de la lista si está allí:

delete obj[A];

Pregunta 3: Agregue 'A' a la lista si aún no estaba allí

obj[A] = true;

Para completar, la prueba de si Aestá en la lista es un poco más segura con esto:

if (Object.prototype.hasOwnProperty.call(obj, A))
    // put code here
}

debido a un posible conflicto entre los métodos integrados y / o las propiedades en el Objeto base, como la constructorpropiedad.

Barra lateral en ES6: la versión de trabajo actual de ECMAScript 6 o algo llamado ES 2015 tiene un objeto Set incorporado . Se implementa ahora en algunos navegadores. Dado que la disponibilidad del navegador cambia con el tiempo, puede consultar la línea Seten esta tabla de compatibilidad de ES6 para ver el estado actual de la disponibilidad del navegador.

Una ventaja del objeto Set incorporado es que no obliga a todas las teclas a una cadena como lo hace el Objeto, por lo que puede tener tanto 5 como "5" como teclas separadas. E incluso puede usar objetos directamente en el conjunto sin una conversión de cadena. Aquí hay un artículo que describe algunas de las capacidades y la documentación de MDN sobre el objeto Set.

Ahora he escrito un polyfill para el objeto de conjunto ES6 para que pueda comenzar a usarlo ahora y se transferirá automáticamente al objeto de conjunto incorporado si el navegador lo admite. Esto tiene la ventaja de que está escribiendo un código compatible con ES6 que funcionará desde IE7. Pero, hay algunas desventajas. La interfaz del conjunto ES6 aprovecha los iteradores ES6 para que pueda hacer cosas como for (item of mySet)y automáticamente iterará a través del conjunto por usted. Pero, este tipo de función de lenguaje no se puede implementar a través de polyfill. Todavía puede iterar un conjunto ES6 sin usar las nuevas funciones de idiomas ES6, pero, francamente, sin las nuevas funciones de idioma, no es tan conveniente como la otra interfaz de conjunto que incluyo a continuación.

Puedes decidir cuál funciona mejor para ti después de mirar a ambos. El polyfill del conjunto ES6 está aquí: https://github.com/jfriend00/ES6-Set .

Para su información, en mis propias pruebas, me di cuenta de que la implementación de Firefox v29 Set no está completamente actualizada en el borrador actual de la especificación. Por ejemplo, no puede encadenar .add()llamadas de método como lo describe la especificación y mi polyfill admite. Probablemente se trate de una especificación en movimiento, ya que aún no está finalizada.

Objetos de conjunto preconstruido: si desea un objeto ya construido que tenga métodos para operar en un conjunto que pueda usar en cualquier navegador, puede usar una serie de diferentes objetos preconstruidos que implementan diferentes tipos de conjuntos. Hay un miniSet que es un código pequeño que implementa los conceptos básicos de un objeto establecido. También tiene un objeto de conjunto más rico en funciones y varias derivaciones que incluyen un Diccionario (le permite almacenar / recuperar un valor para cada clave) y un ObjectSet (le permite mantener un conjunto de objetos, ya sea objetos JS u objetos DOM donde puede suministrar el función que genera una clave única para cada uno o el ObjectSet generará la clave para usted).

Aquí hay una copia del código para el miniSet (el código más actualizado es aquí en github ).

"use strict";
//-------------------------------------------
// Simple implementation of a Set in javascript
//
// Supports any element type that can uniquely be identified
//    with its string conversion (e.g. toString() operator).
// This includes strings, numbers, dates, etc...
// It does not include objects or arrays though
//    one could implement a toString() operator
//    on an object that would uniquely identify
//    the object.
// 
// Uses a javascript object to hold the Set
//
// This is a subset of the Set object designed to be smaller and faster, but
// not as extensible.  This implementation should not be mixed with the Set object
// as in don't pass a miniSet to a Set constructor or vice versa.  Both can exist and be
// used separately in the same project, though if you want the features of the other
// sets, then you should probably just include them and not include miniSet as it's
// really designed for someone who just wants the smallest amount of code to get
// a Set interface.
//
// s.add(key)                      // adds a key to the Set (if it doesn't already exist)
// s.add(key1, key2, key3)         // adds multiple keys
// s.add([key1, key2, key3])       // adds multiple keys
// s.add(otherSet)                 // adds another Set to this Set
// s.add(arrayLikeObject)          // adds anything that a subclass returns true on _isPseudoArray()
// s.remove(key)                   // removes a key from the Set
// s.remove(["a", "b"]);           // removes all keys in the passed in array
// s.remove("a", "b", ["first", "second"]);   // removes all keys specified
// s.has(key)                      // returns true/false if key exists in the Set
// s.isEmpty()                     // returns true/false for whether Set is empty
// s.keys()                        // returns an array of keys in the Set
// s.clear()                       // clears all data from the Set
// s.each(fn)                      // iterate over all items in the Set (return this for method chaining)
//
// All methods return the object for use in chaining except when the point
// of the method is to return a specific value (such as .keys() or .isEmpty())
//-------------------------------------------


// polyfill for Array.isArray
if(!Array.isArray) {
    Array.isArray = function (vArg) {
        return Object.prototype.toString.call(vArg) === "[object Array]";
    };
}

function MiniSet(initialData) {
    // Usage:
    // new MiniSet()
    // new MiniSet(1,2,3,4,5)
    // new MiniSet(["1", "2", "3", "4", "5"])
    // new MiniSet(otherSet)
    // new MiniSet(otherSet1, otherSet2, ...)
    this.data = {};
    this.add.apply(this, arguments);
}

MiniSet.prototype = {
    // usage:
    // add(key)
    // add([key1, key2, key3])
    // add(otherSet)
    // add(key1, [key2, key3, key4], otherSet)
    // add supports the EXACT same arguments as the constructor
    add: function() {
        var key;
        for (var i = 0; i < arguments.length; i++) {
            key = arguments[i];
            if (Array.isArray(key)) {
                for (var j = 0; j < key.length; j++) {
                    this.data[key[j]] = key[j];
                }
            } else if (key instanceof MiniSet) {
                var self = this;
                key.each(function(val, key) {
                    self.data[key] = val;
                });
            } else {
                // just a key, so add it
                this.data[key] = key;
            }
        }
        return this;
    },
    // private: to remove a single item
    // does not have all the argument flexibility that remove does
    _removeItem: function(key) {
        delete this.data[key];
    },
    // usage:
    // remove(key)
    // remove(key1, key2, key3)
    // remove([key1, key2, key3])
    remove: function(key) {
        // can be one or more args
        // each arg can be a string key or an array of string keys
        var item;
        for (var j = 0; j < arguments.length; j++) {
            item = arguments[j];
            if (Array.isArray(item)) {
                // must be an array of keys
                for (var i = 0; i < item.length; i++) {
                    this._removeItem(item[i]);
                }
            } else {
                this._removeItem(item);
            }
        }
        return this;
    },
    // returns true/false on whether the key exists
    has: function(key) {
        return Object.prototype.hasOwnProperty.call(this.data, key);
    },
    // tells you if the Set is empty or not
    isEmpty: function() {
        for (var key in this.data) {
            if (this.has(key)) {
                return false;
            }
        }
        return true;
    },
    // returns an array of all keys in the Set
    // returns the original key (not the string converted form)
    keys: function() {
        var results = [];
        this.each(function(data) {
            results.push(data);
        });
        return results;
    },
    // clears the Set
    clear: function() {
        this.data = {}; 
        return this;
    },
    // iterate over all elements in the Set until callback returns false
    // myCallback(key) is the callback form
    // If the callback returns false, then the iteration is stopped
    // returns the Set to allow method chaining
    each: function(fn) {
        this.eachReturn(fn);
        return this;
    },
    // iterate all elements until callback returns false
    // myCallback(key) is the callback form
    // returns false if iteration was stopped
    // returns true if iteration completed
    eachReturn: function(fn) {
        for (var key in this.data) {
            if (this.has(key)) {
                if (fn.call(this, this.data[key], key) === false) {
                    return false;
                }
            }
        }
        return true;
    }
};

MiniSet.prototype.constructor = MiniSet;

Puede crear un objeto sin propiedades como

var set = Object.create(null)

que puede actuar como un conjunto y elimina la necesidad de usar hasOwnProperty.

var set = Object.create(null); // create an object with no properties

if (A in set) { // 1. is A in the list
  // some code
}
delete set[a]; // 2. delete A from the list if it exists in the list 
set[A] = true; // 3. add A to the list if it is not already present

A partir de ECMAScript 6, la estructura de datos Set es una característica incorporada . La compatibilidad con las versiones de node.js se puede encontrar aquí .

En la versión ES6 de Javascript, ha incorporado el tipo de conjunto ( verifique la compatibilidad con su navegador ).

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

Para agregar un elemento al conjunto que simplemente usa .add(), que se ejecuta O(1)y agrega el elemento al conjunto (si no existe) o no hace nada si ya está allí. Puede agregar elementos de cualquier tipo allí (matrices, cadenas, números)

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

Para verificar el número de elementos en el conjunto, simplemente puede usar .size. También corre enO(1)

numbers.size; // 4

Para eliminar el elemento del conjunto, use .delete(). Devuelve verdadero si el valor estaba allí (y fue eliminado), y falso si el valor no existía. También corre en O(1).

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

Para verificar si el elemento existe en un conjunto de uso .has(), que devuelve verdadero si el elemento está en el conjunto y falso en caso contrario. También corre en O(1).

numbers.has(3); // false
numbers.has(1); // true

Además de los métodos que desea, hay algunos adicionales:

• numbers.clear(); simplemente eliminaría todos los elementos del conjunto
• numbers.forEach(callback); iterando a través de los valores del conjunto en orden de inserción
• numbers.entries(); crear un iterador de todos los valores
• numbers.keys(); devuelve las claves del conjunto que es lo mismo que numbers.values()

También hay un Weakset que permite agregar solo valores de tipo de objeto.

He comenzado una implementación de Sets que actualmente funciona bastante bien con números y cadenas. Mi enfoque principal era la operación de diferencia, así que traté de hacerlo lo más eficiente posible. Tenedores y revisiones de código son bienvenidos!

https://github.com/mcrisc/SetJS

Acabo de notar que la biblioteca d3.js tiene implementación de conjuntos, mapas y otras estructuras de datos. No puedo discutir sobre su eficiencia, pero a juzgar por el hecho de que es una biblioteca popular, debe ser lo que necesita.

La documentación está aquí

Por conveniencia, copio desde el enlace (las 3 primeras funciones son las de interés)

• d3.set ([matriz])

Construye un nuevo conjunto. Si se especifica la matriz, agrega la matriz dada de valores de cadena al conjunto devuelto.

• set.has (valor)

Devuelve verdadero si y solo si este conjunto tiene una entrada para la cadena de valor especificada.

• set.add (valor)

Agrega la cadena de valor especificada a este conjunto.

• set.remove (valor)

Si el conjunto contiene la cadena de valor especificada, la elimina y devuelve verdadero. De lo contrario, este método no hace nada y devuelve falso.

• set.values ​​()

Devuelve una matriz de los valores de cadena en este conjunto. El orden de los valores devueltos es arbitrario. Se puede utilizar como una forma conveniente de calcular los valores únicos para un conjunto de cadenas. Por ejemplo:

d3.set (["foo", "bar", "foo", "baz"]). values ​​(); // "foo", "bar", "baz"

• set.forEach (función)

Llama a la función especificada para cada valor en este conjunto, pasando el valor como argumento. El contexto de esta función es este conjunto. Devuelve indefinido. El orden de iteración es arbitrario.

• set.empty ()

Devuelve verdadero si y solo si este conjunto tiene valores cero.

• set.size ()

Devuelve el número de valores en este conjunto.

Sí, esa es una forma sensata, eso es todo lo que es un objeto (bueno, para este caso de uso), un conjunto de claves / valores con acceso directo.

Debería verificar si ya está allí antes de agregarlo, o si solo necesita indicar presencia, "agregar" nuevamente no cambia nada, simplemente lo coloca nuevamente en el objeto.