Imitando conjuntos em JavaScript?

Estou trabalhando em JavaScript. Gostaria de armazenar uma lista de valores de sequência exclusivos e não ordenados, com as seguintes propriedades:

1. uma maneira rápida de perguntar 'está A na lista'?
2. uma maneira rápida de fazer 'excluir A da lista, se existir na lista'
3. uma maneira rápida de fazer 'adicionar A à lista, se ainda não estiver presente'.

O que eu realmente quero é um conjunto. Alguma sugestão para a melhor maneira de imitar um conjunto em JavaScript?

Esta pergunta recomenda o uso de um Object , com as chaves armazenando propriedades e os valores definidos como true: isso é uma maneira sensata?

Se você estiver programando em um ambiente compatível com ES6 (como node.js, um navegador específico com os recursos necessários para ES6 ou transpilando código ES6 para o seu ambiente), poderá usar o Setobjeto incorporado ao ES6 . Possui recursos muito agradáveis ​​e pode ser usado como é certo em seu ambiente.

Para muitas coisas simples em um ambiente ES5, o uso de um Object funciona muito bem. Se objé seu objeto e Aé uma variável que possui o valor que você deseja operar no conjunto, você pode fazer o seguinte:

Código de inicialização:

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

Pergunta 1: Está Ana lista:

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

Pergunta 2: exclua 'A' da lista, se houver:

delete obj[A];

Pergunta 3: adicione 'A' à lista se ainda não estiver lá

obj[A] = true;

Para completar, o teste para saber se Aestá na lista é um pouco mais seguro com isso:

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

devido a um possível conflito entre métodos e / ou propriedades integradas no objeto base, como a constructorpropriedade

Barra lateral no ES6: a versão atual do ECMAScript 6 ou algo chamado ES 2015 possui um objeto Set interno . Está implementado agora em alguns navegadores. Desde disponibilidade navegador muda ao longo do tempo, você pode olhar para a linha para Setem esta tabela compatibilidade ES6 para ver o status atual disponibilidade browser.

Uma vantagem do objeto Set embutido é que ele não coage todas as chaves a uma string como o Object, para que você possa ter 5 e "5" como chaves separadas. E você pode até usar objetos diretamente no conjunto sem uma conversão de string. Aqui está um artigo que descreve alguns dos recursos e a documentação do MDN no objeto Set.

Agora, eu escrevi um polyfill para o objeto definido do ES6 para que você possa começar a usá-lo agora e ele será automaticamente adiado para o objeto definido interno, se o navegador suportar. Isso tem a vantagem de você escrever um código compatível com ES6 que funcionará desde o IE7. Mas existem algumas desvantagens. A interface do conjunto ES6 tira proveito dos iteradores do ES6 para que você possa fazer coisas como for (item of mySet)ele irá automaticamente iterar o conjunto para você. Mas, esse tipo de recurso de idioma não pode ser implementado via polyfill. Você ainda pode iterar um conjunto ES6 sem usar os novos recursos de idiomas do ES6, mas, francamente, sem os novos recursos de idioma, não é tão conveniente quanto a outra interface de conjunto que incluo abaixo.

Você pode decidir qual funciona melhor para você depois de analisar os dois. O polyfill do conjunto ES6 está aqui: https://github.com/jfriend00/ES6-Set .

Para sua informação, em meus próprios testes, notei que a implementação do Firefox v29 Set não está totalmente atualizada com o rascunho atual da especificação. Por exemplo, você não pode encadear .add()chamadas de método como a especificação descreve e meu polyfill é compatível. Provavelmente é uma questão de especificação em movimento, pois ainda não está finalizada.

Objetos de conjunto pré- criado : se você deseja um objeto já criado que possui métodos para operar em um conjunto que pode ser usado em qualquer navegador, pode usar uma série de objetos pré-criados diferentes que implementam diferentes tipos de conjuntos. Existe um miniSet que é um código pequeno que implementa o básico de um objeto definido. Ele também possui um objeto de conjunto mais rico em recursos e várias derivações, incluindo um Dicionário (vamos armazenar / recuperar um valor para cada chave) e um ObjectSet (vamos manter um conjunto de objetos - objetos JS ou objetos DOM, onde você fornece o função que gera uma chave exclusiva para cada um ou o ObjectSet irá gerar a chave para você).

Aqui está uma cópia do código para o miniSet (o código mais atualizado está aqui no 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;

Você pode criar um objeto sem propriedades como

var set = Object.create(null)

que pode atuar como um conjunto e elimina a necessidade de uso 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

No ECMAScript 6, a estrutura de dados do conjunto é um recurso interno . A compatibilidade com as versões do node.js. pode ser encontrada aqui .

Na versão ES6 do Javascript, você incorporou o tipo de conjunto ( verifique a compatibilidade com seu navegador ).

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

Para adicionar um elemento ao conjunto, você simplesmente usa .add(), que é executado O(1)e adiciona o elemento ao conjunto (se ele não existir) ou não faz nada se já estiver lá. Você pode adicionar elemento de qualquer tipo lá (matrizes, strings, números)

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

Para verificar o número de elementos no conjunto, você pode simplesmente usar .size. Também é executado emO(1)

numbers.size; // 4

Para remover o elemento do conjunto, use .delete(). Retorna true se o valor estava lá (e foi removido) e false se o valor não existir. Também é executado O(1).

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

Para verificar se o elemento existe em um conjunto .has(), use true, que retorna true se o elemento estiver no conjunto e false, caso contrário. Também é executado O(1).

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

Além dos métodos desejados, existem alguns adicionais:

• numbers.clear(); apenas removeria todos os elementos do conjunto
• numbers.forEach(callback); iterando pelos valores do conjunto na ordem de inserção
• numbers.entries(); crie um iterador de todos os valores
• numbers.keys(); retorna as teclas do conjunto, que é o mesmo que numbers.values()

Há também um conjunto de armas que permite adicionar apenas valores de tipo de objeto.

Eu iniciei uma implementação de Sets que atualmente funciona muito bem com números e strings. Meu foco principal era a operação de diferença, então tentei torná-la o mais eficiente possível. Garfos e revisões de código são bem-vindos!

https://github.com/mcrisc/SetJS

Acabei de notar que a biblioteca d3.js. possui implementação de conjuntos, mapas e outras estruturas de dados. Não posso discutir sobre a eficiência deles, mas, a julgar pelo fato de ser uma biblioteca popular, deve ser o que você precisa.

A documentação está aqui

Por conveniência, copio do link (as 3 primeiras funções são de interesse)

• d3.set ([matriz])

Constrói um novo conjunto. Se matriz for especificada, adiciona a matriz especificada de valores de sequência ao conjunto retornado.

• set.has (valor)

Retorna true se e somente se este conjunto tiver uma entrada para a cadeia de valor especificada.

• set.add (valor)

Adiciona a cadeia de valor especificada a este conjunto.

• set.remove (value)

Se o conjunto contiver a cadeia de valor especificada, a remove e retorna true. Caso contrário, esse método não fará nada e retorna falso.

• set.values ​​()

Retorna uma matriz dos valores da sequência neste conjunto. A ordem dos valores retornados é arbitrária. Pode ser usado como uma maneira conveniente de calcular os valores exclusivos para um conjunto de strings. Por exemplo:

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

• set.forEach (function)

Chama a função especificada para cada valor neste conjunto, passando o valor como argumento. O contexto da função é este conjunto. Retorna indefinido. A ordem da iteração é arbitrária.

• set.empty ()

Retorna true se e somente se este conjunto tiver valores zero.

• set.size ()

Retorna o número de valores neste conjunto.

Sim, é uma maneira sensata - é tudo o que um objeto é (bem, para este caso de uso) - um monte de chaves / valores com acesso direto.

Você precisaria verificar se ele já está lá antes de adicioná-lo, ou se você só precisa indicar presença, "adicioná-lo" novamente não muda nada, apenas o define novamente no objeto.