Meniru set dalam JavaScript?

Saya bekerja di JavaScript. Saya ingin menyimpan daftar nilai string unik , tidak berurutan, dengan properti berikut:

1. cara cepat untuk bertanya 'apakah A ada dalam daftar'?
2. cara cepat untuk melakukan 'hapus A dari daftar jika ada dalam daftar'
3. cara cepat untuk melakukan 'tambahkan A ke daftar jika belum ada'.

Yang benar-benar saya inginkan adalah satu set. Adakah saran untuk cara terbaik meniru set di JavaScript?

Pertanyaan ini merekomendasikan menggunakan Obyek , dengan kunci menyimpan properti, dan semua nilai diatur ke true: apakah itu cara yang masuk akal?

Jika Anda memprogram dalam lingkungan yang mendukung ES6 (seperti node.js, peramban khusus dengan kemampuan ES6 yang Anda butuhkan atau mengubah kode ES6 untuk lingkungan Anda), maka Anda dapat menggunakan Setobjek yang dibangun ke dalam ES6 . Ini memiliki kemampuan yang sangat bagus dan dapat digunakan sebagaimana mestinya di lingkungan Anda.

Untuk banyak hal sederhana di lingkungan ES5, menggunakan Object berfungsi dengan sangat baik. Jika objobjek Anda dan Amerupakan variabel yang memiliki nilai yang ingin Anda operasikan di set, maka Anda bisa melakukan ini:

Kode inisialisasi:

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

Pertanyaan 1: Ada Adalam daftar:

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

Pertanyaan 2: Hapus 'A' dari daftar jika ada:

delete obj[A];

Pertanyaan 3: Tambahkan 'A' ke daftar jika belum ada

obj[A] = true;

Untuk kelengkapan, tes untuk apakah Aada dalam daftar sedikit lebih aman dengan ini:

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

karena potensi konflik antara metode bawaan dan / atau properti pada Objek dasar seperti constructorproperti.

Bilah sisi pada ES6: Versi ECMAScript 6 saat ini atau yang disebut ES 2015 memiliki objek Set bawaan . Ini diterapkan sekarang di beberapa browser. Karena ketersediaan browser berubah dari waktu ke waktu, Anda dapat melihat baris Setdi dalam tabel kompatibilitas ES6 ini untuk melihat status ketersediaan browser saat ini.

Salah satu keuntungan dari objek Set bawaan adalah bahwa ia tidak memaksa semua kunci ke string seperti Object sehingga Anda dapat memiliki 5 dan "5" sebagai kunci yang terpisah. Dan, Anda bahkan dapat menggunakan Objek secara langsung di set tanpa konversi string. Berikut adalah artikel yang menjelaskan beberapa kemampuan dan dokumentasi MDN tentang objek Set.

Saya sekarang telah menulis polyfill untuk objek set ES6 sehingga Anda bisa mulai menggunakannya sekarang dan secara otomatis akan tunduk pada objek set bawaan jika browser mendukungnya. Ini memiliki keuntungan bahwa Anda sedang menulis kode yang kompatibel ES6 yang akan bekerja sepanjang jalan kembali ke IE7. Tapi, ada beberapa kelemahannya. Set antarmuka ES6 mengambil keuntungan dari ES6 iterators sehingga Anda dapat melakukan hal-hal seperti for (item of mySet)dan itu akan secara otomatis beralih melalui set untuk Anda. Namun, fitur bahasa jenis ini tidak dapat diimplementasikan melalui polyfill. Anda masih dapat mengulangi set ES6 tanpa menggunakan fitur bahasa ES6 baru, tetapi terus terang tanpa fitur bahasa baru, itu tidak senyaman antarmuka set lain yang saya sertakan di bawah ini.

Anda dapat memutuskan mana yang paling cocok untuk Anda setelah melihat keduanya. Kumpulan polyfill ES6 ada di sini: https://github.com/jfriend00/ES6-Set .

FYI, dalam pengujian saya sendiri, saya perhatikan bahwa implementasi Firefox v29 Set tidak sepenuhnya mutakhir pada draft spesifikasi saat ini. Misalnya, Anda tidak dapat membuat .add()panggilan metode seperti yang dijelaskan oleh spec dan dukungan polyfill saya. Ini mungkin masalah spesifikasi yang bergerak karena belum selesai.

Objek Set Pra-Bangun: Jika Anda ingin objek yang sudah dibangun yang memiliki metode untuk beroperasi pada set yang dapat Anda gunakan di browser apa pun, Anda dapat menggunakan serangkaian objek pra-bangun yang berbeda yang menerapkan berbagai jenis set. Ada miniSet yang merupakan kode kecil yang mengimplementasikan dasar-dasar objek yang ditetapkan. Ini juga memiliki objek set kaya lebih banyak fitur dan beberapa derivasi termasuk Kamus (mari kita menyimpan / mengambil nilai untuk setiap kunci) dan ObjectSet (mari kita menyimpan satu set objek - objek JS atau objek DOM di mana Anda menyediakan fungsi yang menghasilkan kunci unik untuk masing-masing atau ObjectSet akan menghasilkan kunci untuk Anda).

Berikut adalah salinan kode untuk miniSet (kode paling baru ada di 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;

Anda dapat membuat Obyek tanpa properti seperti

var set = Object.create(null)

yang dapat bertindak sebagai satu set dan menghilangkan kebutuhan untuk digunakan 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

Pada ECMAScript 6, struktur data Set adalah fitur bawaan . Kompatibilitas dengan versi node.js dapat ditemukan di sini .

Di Javascript versi ES6, Anda memiliki tipe bawaan untuk set ( periksa kompatibilitas dengan browser Anda ).

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

Untuk menambahkan elemen ke set yang Anda gunakan .add(), yang berjalan di O(1)dan menambahkan elemen ke set (jika tidak ada) atau tidak melakukan apa-apa jika sudah ada di sana. Anda dapat menambahkan elemen jenis apa pun di sana (array, string, angka)

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

Untuk memeriksa jumlah elemen dalam set, Anda cukup menggunakan .size. Juga berjalan diO(1)

numbers.size; // 4

Untuk menghapus elemen dari set penggunaan .delete(). Mengembalikan nilai true jika nilainya ada di sana (dan telah dihapus), dan false jika nilainya tidak ada. Juga berjalan di O(1).

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

Untuk memeriksa apakah elemen tersebut ada dalam set yang digunakan .has(), yang mengembalikan true jika elemen tersebut di set dan false sebaliknya. Juga berjalan di O(1).

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

Selain metode yang Anda inginkan, ada beberapa metode tambahan:

• numbers.clear(); hanya akan menghapus semua elemen dari set
• numbers.forEach(callback); iterasi melalui nilai-nilai set dalam urutan penyisipan
• numbers.entries(); buat iterator dari semua nilai
• numbers.keys(); mengembalikan kunci set yang sama dengan numbers.values()

Ada juga Weakset yang memungkinkan untuk menambahkan hanya nilai tipe objek.

Saya telah memulai implementasi Sets yang saat ini bekerja cukup baik dengan angka dan string. Fokus utama saya adalah operasi perbedaan, jadi saya mencoba membuatnya seefisien mungkin. Ulasan fork dan kode dipersilakan!

https://github.com/mcrisc/SetJS

Saya hanya memperhatikan bahwa perpustakaan d3.js memiliki implementasi set, peta dan struktur data lainnya. Saya tidak dapat berdebat tentang efisiensi mereka tetapi menilai dari fakta bahwa itu adalah perpustakaan yang populer, itu pasti yang Anda butuhkan.

Dokumentasinya ada di sini

Untuk kenyamanan saya salin dari tautan (3 fungsi pertama adalah yang menarik)

• d3.set ([array])

Membangun set baru. Jika array ditentukan, tambahkan array nilai string yang diberikan ke set yang dikembalikan.

• set.has (nilai)

Mengembalikan nilai true jika dan hanya jika set ini memiliki entri untuk string nilai yang ditentukan.

• set.add (nilai)

Menambahkan string nilai yang ditentukan ke set ini.

• set.remove (nilai)

Jika set berisi string nilai yang ditentukan, hapus dan mengembalikan true. Jika tidak, metode ini tidak melakukan apa pun dan mengembalikan false.

• set.values ​​()

Mengembalikan array nilai string di set ini. Urutan nilai yang dikembalikan adalah arbitrer. Dapat digunakan sebagai cara yang nyaman untuk menghitung nilai-nilai unik untuk serangkaian string. Sebagai contoh:

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

• set.forEach (fungsi)

Memanggil fungsi yang ditentukan untuk setiap nilai dalam set ini, meneruskan nilai sebagai argumen. Konteks fungsi ini adalah himpunan ini. Pengembalian tidak terdefinisi. Urutan iterasi bersifat arbitrer.

• set.empty ()

Mengembalikan nilai true jika dan hanya jika set ini memiliki nilai nol.

• set.size ()

Mengembalikan jumlah nilai dalam set ini.

Ya, itu cara yang masuk akal - itu saja objek (untuk kasus penggunaan ini) - banyak kunci / nilai dengan akses langsung.

Anda perlu memeriksa untuk melihat apakah sudah ada sebelum menambahkannya, atau jika Anda hanya perlu menunjukkan keberadaan, "menambahkan" lagi tidak benar-benar mengubah apa pun, itu hanya mengaturnya pada objek lagi.