Pracuję w JavaScript. Chciałbym zapisać listę wartości unikalne, nieuporządkowane wartości łańcuchowe, z następującymi właściwościami:

  1. Szybki sposób zapytania "jest na liście"?
  2. szybki sposób na "Usuń a z listy, jeśli istnieje na liście"
  3. Szybki sposób na "dodaj A do listy, jeśli nie jest już obecny".

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

To Pytanie zaleca korzystanie z obiektu, przy użyciu właściwości przechowywania klawiszy i wartości Wszystkie ustawione To prawda: czy to rozsądny sposób?

220
Richard 31 październik 2011, 22:56

7 odpowiedzi

Najlepsza odpowiedź

Jeśli programujesz w środowisku zdolnym ES6 (np. Node.js, specyficzna przeglądarka z możliwościami ES6, potrzebujesz lub transportujesz kod ES6 dla środowiska), możesz użyć Set obiekt wbudowany w ES6. Ma bardzo ładne możliwości i może być używany tak samo w swoim środowisku.


Dla wielu prostych rzeczy w środowisku ES5, używając obiektu bardzo dobrze działa. Jeśli obj jest Twoim obiektem i {X1}} jest zmienną, która ma wartość, na której chcesz obsługiwać 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: to A na 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 nie było już tam

obj[A] = true;

Aby uzyskać kompletność, test dla tego, czy A jest na liście, jest trochę bezpieczniejszy:

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

Ze względu na potencjalny konflikt między wbudowanymi metodami i / lub właściwościami na obiekcie bazowym, takim jak właściwość constructor.


pasek boczny na ES6: Aktualna wersja robocza ECMASCRIPT 6 lub w rzeczywistości ES 2015 ma wbudowany obiekt wbudowany . Jest teraz wdrażany w niektórych przeglądarkach. Ponieważ dostępność przeglądarki zmienia się w czasie, możesz spojrzeć na linię dla Set w Ta tabela zgodności ES6 Aby zobaczyć aktualny stan dostępności przeglądarki.

Jedną z zalet wbudowanego ustawionego obiektu jest to, że nie uwzględnia wszystkich kluczy do ciągłości, tak jak obiekt, dzięki czemu można mieć zarówno 5, jak i "5" jako oddzielne klucze. A można nawet używać obiektów bezpośrednio w zestawie bez konwersji ciągów. Oto Artykuł opisuje niektóre z możliwości oraz Dokumentacja MDN na obiekcie ustawionym.

Teraz napisałem posiłek do obiektu Ustaw ES6, dzięki czemu można zacząć używać tego teraz i automatycznie odroczy do wbudowanego obiektu, jeśli przeglądarka go obsługuje. Ma to tę zaletę, którą piszesz kompatybilny kod ES6, który będzie działać przez cały czas do IE7. Ale są jakieś obniżki. Zestaw ES6 Interfejs wykorzystuje Iteratory ES6, dzięki czemu możesz robić rzeczy takie jak for (item of mySet) i będzie automatycznie iteruje przez zestaw do Ciebie. Ale ten rodzaj funkcji języka nie może być wdrażany za pośrednictwem posiłku. Nadal możesz iterować zestaw ES6 bez korzystania z nowych funkcji języków ES6, ale szczerze mówiąc bez nowych funkcji językowych, nie jest tak wygodne, jak drugi zestaw interfejsu zawieram poniżej.

Możesz zdecydować, który działa najlepiej dla Ciebie po obarciu. Zestaw ES6 Polyfill jest tutaj: https://github.com/jfriend00/es6-set.

FYI, w moich własnych testach zauważyłem, że implementacja Firefox V29 nie jest w pełni aktualna w bieżącym projekcie specyfikacji. Na przykład nie można łańcuchowy .add() metodę połączeń, takich jak specyfikacja, a moje wsporniki polifillowe. Jest to prawdopodobnie kwestia specyfikacji w ruchu, ponieważ nie jest jeszcze sfinalizowany.


Wstępnie zbudowane obiekty: Jeśli chcesz już zbudować obiekt, który ma metody pracy na zestawie, którego można użyć w dowolnej przeglądarce, możesz użyć szeregu różnych przedbudowanych obiektów, które wdrażają różne Rodzaje zestawów. Jest miniset, który jest małym kodem, który implementuje podstawy zestawu obiektu. Posiada również więcej obiektów bogatych w funkcję obiekt i kilka pochodnych, w tym słownik (przechowujesz / pobieraj wartość dla każdego klawisza) i obiektów (Let's trzymać zestaw obiektów - albo JS obiektów lub obiektów DOM, gdzie albo dostarczasz Funkcja generuje unikalny klucz dla każdego lub obiekt wygeneruje klucz dla Ciebie).

Oto kopia kodu minisetu (większość aktualnych kodu to 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;
262
HoldOffHunger 11 sierpień 2020, 14:49

Możesz utworzyć obiekt bez właściwości

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
72
Thorben Croisé 4 kwiecień 2014, 15:01

Od ECMASCRESS 6, ustawiona struktura danych jest wbudowana Funkcja. Kompatybilność z wersjami węzła

23
hymloth 11 czerwiec 2016, 10:52

W wersji ES6 w wersji JavaScript wbudowany typ dla zestaw (< href = "http://kangax.github.io/compat-table/es6/"> Sprawdź zgodność z przeglądarką ).

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

Do Dodaj element do zestawu, który po prostu używasz .add(), który działa w O(1) i albo dodaje element do ustawienia (jeśli nie istnieje), czy nic nie ma jest już tam. Możesz dodać element dowolnego typu (tablice, ciągi, numery)

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

Do Sprawdź liczbę elementów w zestawie, możesz po prostu użyć .size. Działa również w O(1)

numbers.size; // 4

Do Wyjmij element z zestawu Użyj .delete(). Zwraca TRUE, jeśli wartość była tam (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

Do Sprawdź, czy istnieje element w zestawie użyj .has(), co zwraca się, jeśli element znajduje się w zestawie i false inaczej. Działa również w O(1).

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

Oprócz potrzebnych metod, istnieje kilka dodatkowych:

  • numbers.clear(); Wystarczy usunąć wszystkie elementy z zestawu
  • numbers.forEach(callback); Iterating przez wartości 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ż słaby, który pozwala dodać tylko wartości typu obiektu.

14
Salvador Dali 21 grudzień 2014, 11:32

Rozpocząłem wdrożenie zestawów, które obecnie działa całkiem dobrze z liczbami i łańcuchami. Moim głównym skupieniem była działanie różnicy, więc starałem się uczynić go tak skutecznym jak mogłem. Widelce i recenzje kodu są mile widziane!

https://github.com/mcrisc/setjs.

10
mcrisc 10 styczeń 2014, 16:15

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 oceniając faktem, ż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 ([Array])

Konstruuje nowy zestaw. Jeśli określono tablicę, dodaje podaną tablicę wartości łańcuchowych do zestawu zwracanego.

  • set.Has (wartość)

Zwraca true, jeśli i tylko wtedy, gdy ten zestaw ma 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 true. W przeciwnym razie ta metoda nic nie robi i zwraca fałszywe.

  • set.values ()

Zwraca tablicę wartości ciągów w tym zestawie. Kolejność zwróconych wartości jest arbitralna. 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"]). wartości (); // "foo", "bar", "baz"

  • Set.Forach (funkcja)

Wywołuje określoną funkcję dla każdej wartości w tym zestawie, przekazując wartość jako argument. Ten kontekst funkcji jest ten zestaw. Zwraca niezdefiniowane. Zamówienie iteracji jest arbitralne.

  • set.empty ()

Zwraca true, jeśli i tylko wtedy, gdy ten zestaw ma wartości zero.

  • set.size ()

Zwraca liczbę wartości w tym zestawie.

9
kon psych 24 kwiecień 2014, 00:15

Tak, to jest rozsądny sposób - to wszystko jest obiektem (cóż, dla tego użytku) - kilka kluczy / wartości z bezpośrednim dostępem.

Musisz sprawdzić, czy jest już tam przed dodaniem go, lub jeśli wystarczy wskazać obecność, "dodawanie" ponownie nie zmienia nic, po prostu ustawia go ponownie na obiekcie.

4
Dave Newton 31 październik 2011, 18:58