Sets in JavaScript nachahmen?

Ich arbeite in JavaScript. Ich möchte eine Liste eindeutiger , ungeordneter Zeichenfolgenwerte mit den folgenden Eigenschaften speichern :

1. ein schneller Weg zu fragen, ob A in der Liste ist?
2. Ein schneller Weg, um 'A aus der Liste zu löschen, wenn es in der Liste vorhanden ist'.
3. Ein schneller Weg, um 'A zur Liste hinzuzufügen, falls es noch nicht vorhanden ist'.

Was ich wirklich will, ist ein Set. Irgendwelche Vorschläge, wie man einen Satz in JavaScript am besten nachahmt?

In dieser Frage wird empfohlen, ein Objekt zu verwenden , bei dem die Schlüssel Eigenschaften speichern und alle Werte auf true gesetzt sind: Ist das ein sinnvoller Weg?

Wenn Sie in einer ES6-fähigen Umgebung programmieren (z. B. node.js, einem bestimmten Browser mit den von Ihnen benötigten ES6-Funktionen oder dem Transpilieren von ES6-Code für Ihre Umgebung), können Sie Setdas in ES6 integrierte Objekt verwenden . Es hat sehr schöne Fähigkeiten und kann so verwendet werden, wie es direkt in Ihrer Umgebung ist.

Für viele einfache Dinge in einer ES5-Umgebung funktioniert die Verwendung eines Objekts sehr gut. Wenn objes sich um Ihr Objekt handelt und Aes sich um eine Variable handelt, die den Wert hat, mit dem Sie im Set arbeiten möchten, können Sie Folgendes tun:

Initialisierungscode:

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

Frage 1: Ist Ain der Liste:

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

Frage 2: Löschen Sie 'A' aus der Liste, wenn es dort ist:

delete obj[A];

Frage 3: Fügen Sie 'A' zur Liste hinzu, falls es noch nicht vorhanden war

obj[A] = true;

Der Vollständigkeit halber Aist der Test, ob er in der Liste enthalten ist, damit etwas sicherer:

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

aufgrund eines möglichen Konflikts zwischen integrierten Methoden und / oder Eigenschaften auf dem Basisobjekt wie der constructorEigenschaft.

Seitenleiste auf ES6: Die aktuelle Arbeitsversion von ECMAScript 6 oder etwas, das als ES 2015 bezeichnet wird, verfügt über ein integriertes Set-Objekt . Es ist jetzt in einigen Browsern implementiert. Da sich die Browserverfügbarkeit im Laufe der Zeit ändert, können Sie in der Zeile Setin dieser ES6-Kompatibilitätstabelle nach dem aktuellen Status für die Browserverfügbarkeit suchen .

Ein Vorteil des integrierten Set-Objekts besteht darin, dass nicht alle Schlüssel zu einer Zeichenfolge gezwungen werden, wie dies beim Objekt der Fall ist, sodass Sie sowohl 5 als auch "5" als separate Schlüssel verwenden können. Sie können Objekte sogar direkt im Set ohne Zeichenfolgenkonvertierung verwenden. In diesem Artikel werden einige der Funktionen und die MDN-Dokumentation zum Set-Objekt beschrieben.

Ich habe jetzt eine Polyfüllung für das ES6-Set-Objekt geschrieben, damit Sie diese jetzt verwenden können. Sie wird automatisch auf das integrierte Set-Objekt verschoben, wenn der Browser dies unterstützt. Dies hat den Vorteil, dass Sie ES6-kompatiblen Code schreiben, der bis zum IE7 zurückreicht. Es gibt jedoch einige Nachteile. Die ES6-Set-Schnittstelle nutzt die ES6-Iteratoren, sodass Sie beispielsweise Folgendes tun können, for (item of mySet)und durchläuft das Set automatisch für Sie. Diese Art von Sprachfunktion kann jedoch nicht über Polyfill implementiert werden. Sie können ein ES6-Set immer noch iterieren, ohne die neuen ES6-Sprachfunktionen zu verwenden. Ohne die neuen Sprachfunktionen ist es jedoch nicht so praktisch wie die andere Set-Oberfläche, die ich unten einfüge.

Sie können entscheiden, welches für Sie am besten geeignet ist, nachdem Sie sich beide angesehen haben. Die ES6-Set-Polyfüllung finden Sie hier: https://github.com/jfriend00/ES6-Set .

Zu Ihrer Information, bei meinen eigenen Tests habe ich festgestellt, dass die Implementierung von Firefox v29 Set im aktuellen Entwurf der Spezifikation nicht vollständig auf dem neuesten Stand ist. Zum Beispiel können Sie keine .add()Methodenaufrufe verketten, wie in der Spezifikation beschrieben und meine Polyfill unterstützt. Dies ist wahrscheinlich eine Frage einer Spezifikation in Bewegung, da sie noch nicht abgeschlossen ist.

Vorgefertigte Set-Objekte: Wenn Sie ein bereits erstelltes Objekt mit Methoden zum Bearbeiten eines Sets möchten, das Sie in jedem Browser verwenden können, können Sie eine Reihe verschiedener vorgefertigter Objekte verwenden, die verschiedene Arten von Sets implementieren. Es gibt ein miniSet, einen kleinen Code, der die Grundlagen eines festgelegten Objekts implementiert. Es verfügt außerdem über ein funktionsreicheres Set-Objekt und mehrere Ableitungen, darunter ein Dictionary (speichern / rufen Sie einen Wert für jeden Schlüssel ab) und ein ObjectSet (behalten Sie eine Reihe von Objekten bei - entweder JS-Objekte oder DOM-Objekte, in denen Sie entweder das angeben Funktion, die für jeden einen eindeutigen Schlüssel generiert, oder das ObjectSet generiert den Schlüssel für Sie).

Hier ist eine Kopie des Codes für das miniSet (der aktuellste Code ist hier auf 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;

Sie können ein Objekt ohne Eigenschaften wie erstellen

var set = Object.create(null)

Dies kann als Set fungieren und macht die Verwendung überflüssig 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

Ab ECMAScript 6 ist die Set-Datenstruktur eine integrierte Funktion . Die Kompatibilität mit den Versionen von node.js finden Sie hier .

In der ES6-Version von Javascript haben Sie den Typ für set integriert ( überprüfen Sie die Kompatibilität mit Ihrem Browser ).

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

Um hinzuzufügen , ein Element der Menge , verwenden Sie einfach .add(), das ausgeführt wird O(1)und entweder das zu setzende Element hinzufügt (falls es nicht vorhanden ist) oder nichts tut, wenn es bereits vorhanden ist. Sie können dort Elemente eines beliebigen Typs hinzufügen (Arrays, Strings, Zahlen).

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

So überprüfen Sie die Anzahl der Elemente im Set , können Sie einfach verwenden .size. Läuft auch inO(1)

numbers.size; // 4

So entfernen Sie das Element aus dem Set verwenden Sie .delete(). Es gibt true zurück, wenn der Wert vorhanden war (und entfernt wurde), und false, wenn der Wert nicht vorhanden war. Läuft auch in O(1).

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

Um zu überprüfen, ob das Element in einer Menge vorhanden ist, verwenden Sie .has(), was true zurückgibt, wenn sich das Element in der Menge befindet, andernfalls false. Läuft auch in O(1).

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

Zusätzlich zu den von Ihnen gewünschten Methoden gibt es nur wenige zusätzliche:

• numbers.clear(); würde einfach alle Elemente aus dem Set entfernen
• numbers.forEach(callback); Durchlaufen der Werte des Satzes in Einfügereihenfolge
• numbers.entries(); Erstellen Sie einen Iterator aller Werte
• numbers.keys(); Gibt die Schlüssel des Sets zurück, die mit identisch sind numbers.values()

Es gibt auch ein Weakset, mit dem nur Objekttypwerte hinzugefügt werden können.

Ich habe eine Implementierung von Sets gestartet, die derzeit ziemlich gut mit Zahlen und Zeichenfolgen funktioniert. Mein Hauptaugenmerk lag auf der Differenzoperation, deshalb habe ich versucht, sie so effizient wie möglich zu gestalten. Gabeln und Code-Bewertungen sind willkommen!

https://github.com/mcrisc/SetJS

Mir ist gerade aufgefallen, dass in der Bibliothek d3.js Mengen, Karten und andere Datenstrukturen implementiert sind. Ich kann nicht über ihre Effizienz streiten, aber nach der Tatsache zu urteilen, dass es sich um eine beliebte Bibliothek handelt, muss es das sein, was Sie brauchen.

Die Dokumentation finden Sie hier

Der Einfachheit halber kopiere ich vom Link (die ersten 3 Funktionen sind von Interesse)

• d3.set ([Array])

Erstellt einen neuen Satz. Wenn ein Array angegeben ist, wird das angegebene Array von Zeichenfolgenwerten zum zurückgegebenen Satz hinzugefügt.

• set.has (Wert)

Gibt nur dann true zurück, wenn diese Menge einen Eintrag für die angegebene Wertzeichenfolge enthält.

• set.add (Wert)

Fügt diesem Satz die angegebene Wertzeichenfolge hinzu.

• set.remove (Wert)

Wenn die Menge die angegebene Wertzeichenfolge enthält, wird sie entfernt und true zurückgegeben. Andernfalls führt diese Methode nichts aus und gibt false zurück.

• set.values ​​()

Gibt ein Array der Zeichenfolgenwerte in dieser Gruppe zurück. Die Reihenfolge der zurückgegebenen Werte ist beliebig. Kann als bequeme Methode zur Berechnung der eindeutigen Werte für eine Reihe von Zeichenfolgen verwendet werden. Beispielsweise:

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

• set.forEach (Funktion)

Ruft die angegebene Funktion für jeden Wert in dieser Menge auf und übergibt den Wert als Argument. Der this-Kontext der Funktion ist diese Menge. Gibt undefiniert zurück. Die Iterationsreihenfolge ist beliebig.

• set.empty ()

Gibt nur dann true zurück, wenn diese Menge Nullwerte hat.

• set.size ()

Gibt die Anzahl der Werte in diesem Satz zurück.

Ja, das ist ein vernünftiger Weg - das ist alles, was ein Objekt ist (nun, für diesen Anwendungsfall) - eine Reihe von Schlüsseln / Werten mit direktem Zugriff.

Sie müssen überprüfen, ob es bereits vorhanden ist, bevor Sie es hinzufügen, oder wenn Sie nur die Anwesenheit anzeigen müssen, ändert das erneute "Hinzufügen" nichts, sondern setzt es einfach erneut auf das Objekt.