Есть ли в JavaScript реализация заданной структуры данных? - PullRequest
Новая
       17

Есть ли в JavaScript реализация заданной структуры данных?

33 голосов
/ 26 марта 2010

Я ищу достойную реализацию заданной структуры данных в JavaScript. Он должен поддерживать элементы, которые являются простыми объектами JavaScript.

Пока я нашел только Структуры библиотеки закрытия. Установите , но мне не нравится тот факт, что она изменяет мои данные.

Ответы [ 6 ]

22 голосов

ECMAScript 6 имеет его

Спецификация: http://www.ecma -international.org / ecma-262 / 6.0 / # sec-set-constructor

Использование: https://github.com/lukehoban/es6features#map--set--weakmap--weakset

Пример: 

var s = new Set()
s.add("hello").add("goodbye").add("hello")
s.size === 2
s.has("hello") === true

Модуль, реализующий его для браузеров без поддержки: https://github.com/medikoo/es6-set

11 голосов
/ 26 марта 2010

Вы можете создать простую оболочку вокруг ключей хеш-таблицы, предоставленной моей jshashtable . У меня есть где-то, что я буду выкапывать позже.

UPDATE

Я завершил и протестировал реализацию HashSet и загрузил ее в проект jshashtable на GitHub. Вы можете загрузить его или просмотреть исходный код . 

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2
2 голосов
/ 23 сентября 2015

Использование стандартная структура данных ECMAScript 2015 (ES6) действительно прост в использовании: 

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

mySet.has(1); // true
mySet.has(3); // false, 3 has not been added to the set
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has("Some Text".toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 4

mySet.delete(5); // removes 5 from the set
mySet.has(5);    // false, 5 has been removed

mySet.size; // 3, we just removed one value

Обновление для тех, кто использует AngularJs

Имейте в виду, что наборы не работают с ng-repeat. Так что лучше использовать массив и просто применить уникальный фильтр

2 голосов
/ 26 марта 2010

Я не думаю, что есть способ работать с хеш-кодом объекта, кроме как сохранить его в самом объекте. Строго говоря, можно создать набор классов без хеширования, используя простой линейный поиск, но это вряд ли будет эффективным.

1 голос
/ 20 января 2016

В версии 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, который позволяет добавлять только значения типа объекта.

1 голос
/ 08 мая 2013

Мне нравится Simple-JS-Set (вероятно, потому что я написал это). Он поддерживает любые объекты JavaScript. Он имеет следующий API:

  • Set(hashFunction): (Конструктор) Создать новый набор с заданным hashFunction (по умолчанию JSON.stringify)
  • add(item): добавить предмет в набор
  • remove(item): удалить предмет из набора
  • contains(item): вернуть, содержится ли элемент в наборе
  • size(): вернуть количество уникальных предметов в наборе
  • each(function(item), thisObj): выполнить функцию с каждым элементом в наборе в контексте thisObj
...