Naśladować zestawy w JavaScript?

Pracuję w JavaScript. Chciałbym przechowywać listę unikalnych , nieuporządkowanych wartości ciągów, o następujących właściwościach:

1. szybki sposób na pytanie „czy A jest na liście”?
2. szybki sposób na „usunięcie A z listy, jeśli istnieje na liście”
3. szybki sposób na dodanie „A do listy, jeśli jeszcze jej nie ma”.

To, czego naprawdę chcę, to zestaw. Wszelkie sugestie dotyczące najlepszego sposobu naśladowania zestawu w JavaScript?

To pytanie zaleca użycie obiektu z właściwościami przechowywania kluczy, a wszystkie wartości ustawione na true: czy to rozsądny sposób?

Jeśli programujesz w środowisku obsługującym ES6 (takim jak node.js, konkretna przeglądarka z możliwościami ES6, których potrzebujesz lub transponuj kod ES6 dla swojego środowiska), możesz użyć Setobiektu wbudowanego w ES6 . Ma bardzo ładne możliwości i może być używany tak, jak jest w twoim otoczeniu.

W przypadku wielu prostych rzeczy w środowisku ES5 korzystanie z obiektu działa bardzo dobrze. Jeśli objjest to twój obiekt i Ajest zmienną, która ma wartość, na której chcesz operować w zestawie, możesz to zrobić:

Kod inicjalizacji:

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

Pytanie 1: Jest Ana liście:

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

Pytanie 2: Usuń „A” z listy, jeśli tam jest:

delete obj[A];

Pytanie 3: Dodaj „A” do listy, jeśli jeszcze jej nie było

obj[A] = true;

Aby uzyskać kompletność, sprawdź, czy A to, jest na liście, jest nieco bezpieczniejszy dzięki temu:

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

z powodu potencjalnego konfliktu między wbudowanymi metodami i / lub właściwościami w obiekcie podstawowym, takim jak constructor właściwość.

Pasek boczny na ES6: bieżąca działająca wersja ECMAScript 6 lub coś o nazwie ES 2015 ma wbudowany obiekt Set . Jest teraz zaimplementowany w niektórych przeglądarkach. Ponieważ dostępność przeglądarki zmienia się z czasem, możesz poszukać w wierszuSet w tabeli zgodności ES6, aby zobaczyć bieżący stan dostępności przeglądarki.

Jedną z zalet wbudowanego obiektu Set jest to, że nie zmusza wszystkich kluczy do łańcucha tak jak Obiekt, więc możesz mieć zarówno 5, jak i „5” jako osobne klucze. I możesz nawet używać Obiektów bezpośrednio w zestawie bez konwersji łańcucha. Oto artykuł opisujący niektóre możliwości i dokumentację MDN na obiekcie Set.

Napisałem polifill dla obiektu zestawu ES6, abyś mógł zacząć z niego korzystać teraz i automatycznie przełączy się na wbudowany obiekt zestawu, jeśli przeglądarka go obsługuje. Ma to tę zaletę, że piszesz kod zgodny z ES6, który będzie działał aż do IE7. Ale są też pewne wady. Interfejs zestawu ES6 wykorzystuje iteratory ES6, dzięki czemu możesz robić takie rzeczyfor (item of mySet) a on będzie automatycznie iterował przez zestaw dla Ciebie. Ale tego rodzaju funkcji językowych nie można zaimplementować za pomocą funkcji polifill. Nadal możesz iterować zestaw ES6 bez korzystania z nowych funkcji języków ES6, ale szczerze mówiąc bez nowych funkcji języka, nie jest to tak wygodne, jak inny interfejs zestawu, który przedstawiam poniżej.

Możesz zdecydować, który z nich będzie dla Ciebie najlepszy po zapoznaniu się z obydwoma. Zestaw wypełnień ES6 znajduje się tutaj: https://github.com/jfriend00/ES6-Set .

Do twojej wiadomości, w moich własnych testach zauważyłem, że implementacja zestawu Firefox v29 nie jest w pełni aktualna w bieżącym szkicu specyfikacji. Na przykład nie można łączyć .add()wywołań metod, takich jak opisy specyfikacji i obsługa wielu wypełniaczy. Jest to prawdopodobnie kwestia specyfikacji w ruchu, ponieważ nie została jeszcze sfinalizowana.

Obiekty zestawu gotowego: Jeśli chcesz już zbudować obiekt, który ma metody działania na zestawie, którego można używać w dowolnej przeglądarce, możesz użyć szeregu różnych gotowych obiektów, które implementują różne typy zestawów. Istnieje miniSet, który jest małym kodem, który implementuje podstawy obiektu ustawionego. Ma także bardziej bogaty w funkcje obiekt zestawu i kilka pochodnych, w tym Słownik (pozwala przechowywać / odzyskiwać wartość dla każdego klucza) i ObjectSet (pozwala zachować zestaw obiektów - albo obiekty JS, albo obiekty DOM, w których albo funkcja, która generuje unikalny klucz dla każdego lub ObjectSet wygeneruje klucz dla Ciebie).

Oto kopia kodu miniSet (najbardziej aktualny kod znajduje się tutaj na 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;

Możesz utworzyć Obiekt bez właściwości takich jak

var set = Object.create(null)

który może działać jako zestaw i eliminuje potrzebę użycia 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

Począwszy od ECMAScript 6, struktura danych Set jest funkcją wbudowaną . Zgodność z wersjami node.js można znaleźć tutaj .

W wersji ES6 Javascript masz wbudowany typ dla zestawu ( sprawdź kompatybilność z przeglądarką ).

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

Aby dodać element do zestawu, którego po prostu używasz .add(), który uruchamia się O(1)i albo dodaje element do zestawu (jeśli nie istnieje), albo nic nie robi, jeśli już tam jest. Możesz dodać element dowolnego typu (tablice, ciągi, liczby)

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

Aby sprawdzić liczbę elementów w zestawie, możesz po prostu użyć .size. Działa również wO(1)

numbers.size; // 4

Aby usunąć element z zestawu użyj .delete(). Zwraca true, jeśli wartość tam była (i została usunięta), i false, jeśli wartość nie istniała. Działa również w O(1).

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

Aby sprawdzić, czy element istnieje w zestawie .has(), zwraca true, jeśli element jest w zestawie, a false w przeciwnym razie. Działa również w O(1).

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

Oprócz metod, które chciałeś, istnieje kilka dodatkowych:

• numbers.clear(); po prostu usunie wszystkie elementy z zestawu
• numbers.forEach(callback); iterowanie po wartościach zestawu w kolejności wstawiania
• numbers.entries(); utwórz iterator wszystkich wartości
• numbers.keys(); zwraca klucze zestawu, który jest taki sam jak numbers.values()

Istnieje również zestaw słabych punktów, który pozwala dodawać tylko wartości typu obiektowego.

Rozpocząłem wdrażanie zestawów, które obecnie działają całkiem dobrze z liczbami i łańcuchami. Moim głównym celem była operacja różnicowa, więc starałem się, aby była jak najbardziej wydajna. Widoki i recenzje kodów są mile widziane!

https://github.com/mcrisc/SetJS

Właśnie zauważyłem, że biblioteka d3.js ma implementację zestawów, map i innych struktur danych. Nie mogę kłócić się o ich skuteczność, ale sądząc po tym, że jest to popularna biblioteka, musi być tym, czego potrzebujesz.

Dokumentacja jest tutaj

Dla wygody kopiuję z linku (pierwsze 3 funkcje są interesujące)

• d3.set ([tablica])

Tworzy nowy zestaw. Jeśli określono tablicę, dodaje podaną tablicę wartości ciągów do zwróconego zestawu.

• set.has (wartość)

Zwraca wartość true tylko wtedy, gdy ten zestaw zawiera wpis dla określonego ciągu wartości.

• set.add (wartość)

Dodaje określony ciąg wartości do tego zestawu.

• set.remove (wartość)

Jeśli zestaw zawiera określony ciąg wartości, usuwa go i zwraca wartość true. W przeciwnym razie ta metoda nic nie robi i zwraca false.

• set.values ​​()

Zwraca tablicę wartości ciągów w tym zestawie. Kolejność zwracanych wartości jest dowolna. Może być używany jako wygodny sposób obliczania unikalnych wartości dla zestawu ciągów. Na przykład:

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

• set.forEach (funkcja)

Wywołuje określoną funkcję dla każdej wartości w tym zestawie, przekazując wartość jako argument. Ten kontekst funkcji jest tym zestawem. Zwraca niezdefiniowany. Kolejność iteracji jest dowolna.

• set.empty ()

Zwraca wartość true tylko wtedy, gdy ten zestaw ma wartości zerowe.

• set.size ()

Zwraca liczbę wartości w tym zestawie.

Tak, to rozsądny sposób - to wszystko, czym jest obiekt (cóż, w tym przypadku użycia) - kilka kluczy / wartości z bezpośrednim dostępem.

Przed dodaniem musisz sprawdzić, czy już tam jest, lub jeśli musisz tylko wskazać obecność, „dodanie” go ponownie niczego nie zmienia, po prostu ustawia go ponownie na obiekcie.