Подражая множествам в JavaScript? - PullRequest
215 голосов
/ 31 октября 2011

Я работаю в JavaScript.Я хотел бы сохранить список уникальных неупорядоченных строковых значений со следующими свойствами:

  1. быстрый способ узнать, «есть ли в списке»?
  2. быстрый способ сделать «удалить А из списка, если он существует в списке»
  3. быстрый способ сделать «добавить А в список, если его еще нет».

Что я действительно хочу, так это набор.Любые предложения для лучшего способа имитировать набор в JavaScript?

В этом вопросе рекомендуется использовать Object , с ключами, хранящими свойства, и значениями все установлены в true: это разумно?способ

Ответы [ 7 ]

258 голосов
/ 31 октября 2011

Если вы программируете в среде с поддержкой ES6 (например, node.js, конкретный браузер с необходимыми вам возможностями ES6 или перенос кода ES6 для вашей среды), то вы можете использовать объект Setвстроенный в ES6 .Он обладает очень хорошими возможностями и может быть использован как есть в вашей среде.


Для многих простых вещей в среде ES5 использование объекта работает очень хорошо.Если obj является вашим объектом, а A является переменной, значение которой вы хотите оперировать в наборе, то вы можете сделать следующее:

Код инициализации:

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

Вопрос 1: Есть A в списке:

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

Вопрос 2: Удалить букву «А» из списка, если она есть:

delete obj[A];

Вопрос 3: Добавить 'A' в список, если его там еще не было

obj[A] = true;

Для полноты, проверить, является ли A в списке немного безопаснее:

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

из-за потенциального конфликта между встроенными методами и / или свойствами базового объекта, такими как свойство constructor.


Боковая панель на ES6: Текущая рабочая версия ECMAScript 6 или что-то, называемое ES 2015, имеет встроенный объект Set .Это реализовано сейчас в некоторых браузерах.Поскольку доступность браузера со временем меняется, вы можете посмотреть строку Set в этой таблицы совместимости ES6 , чтобы увидеть текущее состояние доступности браузера.

Одно из преимуществ встроенногов Set объект состоит в том, что он не приводит все ключи к строке, как это делает Object, поэтому вы можете использовать как 5, так и «5» в качестве отдельных ключей.И вы даже можете использовать объекты непосредственно в наборе без преобразования строки.Вот статья , в которой описаны некоторые возможности и документация MDN об объекте Set.

Теперь я написал polyfill для объекта set ES6, чтобы вы могли начатьиспользуя это сейчас, и он автоматически будет зависеть от встроенного объекта set, если браузер его поддерживает.Преимущество этого в том, что вы пишете ES6-совместимый код, который будет работать вплоть до IE7.Но есть некоторые недостатки.Интерфейс набора ES6 использует преимущества итераторов ES6, поэтому вы можете выполнять такие действия, как for (item of mySet), и он будет автоматически выполнять итерацию по всему набору для вас.Но этот тип языковой функции не может быть реализован через polyfill.Вы по-прежнему можете выполнять итерацию набора ES6 без использования новых языковых функций ES6, но, честно говоря, без новых языковых функций он не так удобен, как другой интерфейс набора, который я включил ниже.

Вы можете решить, какой из них работаетлучше всего для вас, посмотрев на оба.Полифилл набора ES6 находится здесь: https://github.com/jfriend00/ES6-Set.

К вашему сведению, в моем собственном тестировании я заметил, что реализация Firefox v29 Set не полностью соответствует текущей версии спецификации.Например, вы не можете связывать вызовы .add() методов, как описано в спецификации, и моя поддержка polyfill.Вероятно, это вопрос спецификации в движении, так как она еще не завершена.


Предварительно построенные объекты Set: Если вы хотите, чтобы уже построенный объект имел методы для работыВ наборе, который вы можете использовать в любом браузере, вы можете использовать серию различных предварительно созданных объектов, которые реализуют различные типы наборов.Существует мини-набор, представляющий собой небольшой код, который реализует основы заданного объекта.Он также имеет более функциональный набор объектов и несколько дериваций, включая Словарь (давайте сохраним / получим значение для каждого ключа) и ObjectSet (позволим вам сохранить набор объектов - либо объекты JS, либо объекты DOM, для которых вы либо предоставляетефункция, которая генерирует уникальный ключ для каждого или ObjectSet сгенерирует ключ для вас).

Вот копия кода для miniSet (наиболее актуальный код здесь на 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;
71 голосов
/ 19 сентября 2013

Вы можете создать объект без свойств, таких как

var set = Object.create(null)

, который может действовать как набор и исключает необходимость использования 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
22 голосов
/ 31 декабря 2012

Начиная с ECMAScript 6, структура данных Set является встроенной функцией .Совместимость с версиями node.js можно найти здесь .

14 голосов
/ 21 декабря 2014

В версии ES6 Javascript вы встроили тип для set ( проверьте совместимость с вашим браузером ).

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

К добавить элемент к набору, который вы просто используете .add(), который работает в O(1) и либо добавляет элемент для установки (если он не существует), либо ничего не делает, если он уже существует там. Вы можете добавить туда элемент любого типа (массивы, строки, числа)

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

Чтобы проверить количество элементов в наборе, вы можете просто использовать .size. Также работает в O(1)

numbers.size; // 4

Для удалить элемент из набора использовать .delete(). Возвращает true, если значение было (и было удалено), и false, если значение не существовало. Также работает в O(1).

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

To чтобы проверить, существует ли элемент в наборе, используйте .has(), который возвращает true, если элемент находится в наборе, и false в противном случае. Также работает в O(1).

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

В дополнение к желаемым методам, есть несколько дополнительных:

  • numbers.clear(); просто удалит все элементы из набора
  • numbers.forEach(callback); итерация значений набора в порядке вставки
  • numbers.entries(); создать итератор всех значений
  • numbers.keys(); возвращает ключи набора, который совпадает с numbers.values()

Существует также Weakset, который позволяет добавлять только значения типа объекта.

9 голосов
/ 14 декабря 2011

Я начал реализацию наборов, которая в настоящее время довольно хорошо работает с числами и строками. Основное внимание было уделено разностной операции, поэтому я старался сделать ее максимально эффективной. Форки и обзоры кодов приветствуются!

https://github.com/mcrisc/SetJS

8 голосов
/ 18 апреля 2014

Я только что заметил, что в библиотеке d3.js есть реализация наборов, карт и других структур данных.Я не могу спорить об их эффективности, но, судя по тому, что это популярная библиотека, она должна быть именно тем, что вам нужно.

Документация здесь

Для удобстваЯ копирую по ссылке (первые 3 функции представляют интерес)


  • d3.set ([массив])

Создает новый набор.Если указан массив, добавляет указанный массив строковых значений к возвращенному набору.

  • set.has (значение)

Возвращает true, если и только если этот набор имеетзапись для указанной строки значения.

  • set.add (значение)

Добавляет указанную строку значения в этот набор.

  • set.remove (значение)

Если набор содержит указанную строку значений, удаляет ее и возвращает true.В противном случае этот метод ничего не делает и возвращает false.

  • set.values ​​()

Возвращает массив строковых значений в этом наборе.Порядок возвращаемых значений произвольный.Может использоваться как удобный способ вычисления уникальных значений для набора строк.Например:

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

  • set.forEach (function)

Вызывает указанную функцию для каждого значения в этом наборе, передаваязначение в качестве аргумента.Этот контекст функции является этим набором.Возвращает неопределенное.Порядок итерации произвольный.

  • set.empty ()

Возвращает true, если и только если этот набор имеет нулевые значения.

  • set.size ()

Возвращает количество значений в этом наборе.

4 голосов
/ 31 октября 2011

Да, это разумный способ - это все, чем является объект (ну, в данном случае) - набор ключей / значений с прямым доступом.

Вам нужно проверитьперед тем, как добавить его, посмотрите, есть ли он, или если вам просто нужно указать присутствие, «добавление» еще раз на самом деле ничего не меняет, просто снова устанавливает его на объекте.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...