Imiter les ensembles en JavaScript ?

Question

Je travaille en JavaScript. J'aimerais stocker une liste de unique des valeurs de chaîne non ordonnées, avec les propriétés suivantes :

1. un moyen rapide de demander "A est-il dans la liste" ?
2. un moyen rapide de faire "supprimer A de la liste s'il existe dans la liste".
3. un moyen rapide de faire "ajouter A à la liste s'il n'est pas déjà présent".

Ce que je veux vraiment, c'est un ensemble. Avez-vous des suggestions sur la meilleure façon d'imiter un ensemble en JavaScript ?

Ce site La question recommande d'utiliser un objet avec les clés qui stockent les propriétés et les valeurs qui sont toutes définies comme vraies : est-ce une façon raisonnable de procéder ?

Answer 1

Si vous programmez dans un environnement compatible ES6 (tel que node.js, un navigateur spécifique avec les capacités ES6 dont vous avez besoin ou la transposition de code ES6 pour votre environnement), vous pouvez alors utiliser l'option Set intégré à l'ES6 . Il a de très belles capacités et peut être utilisé tel quel dans votre environnement.

---

Pour de nombreuses choses simples dans un environnement ES5, l'utilisation d'un objet fonctionne très bien. Si obj est votre objet et A est une variable qui a la valeur sur laquelle vous voulez opérer dans l'ensemble, alors vous pouvez faire ceci :

Code d'initialisation :

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

Question 1 : Est A dans la liste :

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

Question 2 : Supprimez le "A" de la liste s'il y est :

delete obj[A];

Question 3 : Ajouter "A" à la liste s'il n'y figurait pas déjà.

obj[A] = true;

---

Pour être complet, le test pour savoir si A est dans la liste est un peu plus sûr avec ça :

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

en raison d'un conflit potentiel entre des méthodes et/ou des propriétés intégrées à l'objet de base, comme l'objet constructor propriété.

---

Encadré sur ES6 : La version de travail actuelle de ECMAScript 6 ou quelque chose appelé ES 2015 a un objet Set intégré . Il est maintenant implémenté dans certains navigateurs. Étant donné que la disponibilité des navigateurs change avec le temps, vous pouvez regarder la ligne de Set en ce tableau de compatibilité ES6 pour connaître l'état actuel de la disponibilité du navigateur.

L'un des avantages de l'objet Set intégré est qu'il ne contraint pas toutes les clés à une chaîne comme le fait l'objet, de sorte que vous pouvez avoir à la fois 5 et "5" comme clés distinctes. Vous pouvez donc avoir 5 et "5" comme clés distinctes. Et vous pouvez même utiliser les Objects directement dans l'ensemble sans conversion de chaîne. Voici un exemple un article qui décrit certaines des capacités et La documentation de MDN sur l'objet Set.

J'ai maintenant écrit un polyfill pour l'objet set ES6. Vous pouvez donc commencer à l'utiliser dès maintenant et il se reportera automatiquement à l'objet set intégré si le navigateur le prend en charge. Cela présente l'avantage d'écrire un code compatible ES6 qui fonctionnera jusqu'à IE7. Mais il y a quelques inconvénients. L'interface set ES6 tire parti des itérateurs ES6, ce qui vous permet de faire des choses telles que for (item of mySet) et il parcourra automatiquement l'ensemble pour vous. Mais ce type de fonctionnalité du langage ne peut pas être implémenté via un polyfill. Vous pouvez toujours itérer un ensemble ES6 sans utiliser les nouvelles fonctionnalités du langage ES6, mais franchement, sans les nouvelles fonctionnalités du langage, ce n'est pas aussi pratique que l'autre interface d'ensemble que j'inclus ci-dessous.

Vous pouvez décider lequel vous convient le mieux après avoir examiné les deux. Le polyfill set ES6 est ici : https://github.com/jfriend00/ES6-Set .

Pour information, lors de mes propres tests, j'ai remarqué que l'implémentation de Firefox v29 Set n'est pas totalement à jour par rapport à la version actuelle de la spécification. Par exemple, vous ne pouvez pas enchaîner .add() comme le décrit la spécification et comme le prend en charge mon polyfill. Il s'agit probablement d'une spécification en mouvement, car elle n'est pas encore finalisée.

---

Objets de l'ensemble pré-construit : Si vous voulez un objet déjà construit qui possède des méthodes pour opérer sur un ensemble et que vous pouvez utiliser dans n'importe quel navigateur, vous pouvez utiliser une série de différents objets préconstruits qui implémentent différents types d'ensembles. Il y a un miniSet qui est un petit code qui implémente les bases d'un objet set. Il existe également un objet set plus riche en fonctionnalités et plusieurs dérivés, notamment un Dictionary (qui vous permet de stocker/récupérer une valeur pour chaque clé) et un ObjectSet (qui vous permet de conserver un ensemble d'objets, qu'il s'agisse d'objets JS ou d'objets DOM, pour lesquels vous fournissez la fonction qui génère une clé unique pour chacun d'entre eux ou l'ObjectSet génère la clé pour vous).

Voici une copie du code pour le miniSet (le code le plus à jour est le suivant ici sur 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;

Answer 2

Vous pouvez créer un objet sans propriétés comme

var set = Object.create(null)

qui peut agir comme un ensemble et élimine la nécessité d'utiliser 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

Answer 3

À partir d'ECMAScript 6, la structure de données Set est une structure de données intégrée. fonctionnalité . On peut trouver la compatibilité avec les versions de node.js aquí .

Answer 4

J'ai commencé une implémentation de Sets qui fonctionne actuellement assez bien avec les nombres et les chaînes de caractères. Mon objectif principal était l'opération de différence, j'ai donc essayé de la rendre aussi efficace que possible. Les commentaires et les revues de code sont les bienvenus !

https://github.com/mcrisc/SetJS

Answer 5

Je viens de remarquer que la bibliothèque d3.js implémente des ensembles, des cartes et d'autres structures de données. Je ne peux pas discuter de leur efficacité, mais à en juger par le fait que c'est une bibliothèque populaire, elle doit répondre à vos besoins.

La documentation est aquí

Pour des raisons de commodité, je copie le lien (les 3 premières fonctions sont celles qui nous intéressent).

---

• d3.set([array])

Construit un nouvel ensemble. Si array est spécifié, ajoute le tableau de valeurs de chaînes de caractères au jeu retourné.

• set.has(valeur)

Renvoie un message vrai si et seulement si cet ensemble a une entrée pour la chaîne de valeur spécifiée.

• set.add(value)

Ajoute la chaîne de valeur spécifiée à cet ensemble.

• set.remove(valeur)

Si l'ensemble contient la chaîne de valeur spécifiée, il la supprime et renvoie true. Sinon, cette méthode ne fait rien et renvoie false.

• set.values()

Renvoie un tableau des valeurs de chaînes de caractères dans cet ensemble. L'ordre des valeurs retournées est arbitraire. Peut être utilisé comme un moyen pratique de calculer les valeurs uniques d'un ensemble de chaînes de caractères. Par exemple :

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

• set.forEach(fonction)

Appelle la fonction spécifiée pour chaque valeur de cet ensemble, en passant la valeur comme argument. Le contexte de la fonction est cet ensemble. Retourne une valeur indéfinie. L'ordre d'itération est arbitraire.

• set.empty()

Renvoie vrai si et seulement si cet ensemble a des valeurs nulles.

• set.size()

Renvoie le nombre de valeurs dans cet ensemble.