Структура данных Javascript для быстрого поиска и упорядоченного цикла?
есть ли структура данных или шаблон в Javascript, который можно использовать как для быстрого поиска (по ключу, как с ассоциативными массивами), так и для упорядоченного цикла?
]Правильно, теперь я использую объектные литералы для хранения своих данных, но я только что обнаружил, что Chrome не поддерживает порядок при циклическом повторении имен свойств.
Есть ли распространенный способ решить эту проблему в Javascript?
Спасибо за любые подсказки.
2 ответа
Создайте структуру данных сами. Сохраните порядок во внутреннем массиве структуры. Храните объекты, сопоставленные ключом, в обычном объекте. Назовем его OrderedMap , в котором будет карта, массив и четыре основных метода.
OrderedMap
map
_array
set(key, value)
get(key)
remove(key)
forEach(fn)
function OrderedMap() {
this.map = {};
this._array = [];
}
При вставке элемента добавьте его в массив в желаемой позиции, а также в объект. Вставка по индексу или в конце находится в O (1).
OrderedMap.prototype.set = function(key, value) {
// key already exists, replace value
if(key in this.map) {
this.map[key] = value;
}
// insert new key and value
else {
this._array.push(key);
this.map[key] = value;
}
};
При удалении объекта удалите его из массива и объекта. При удалении по ключу или значению сложность составляет O (n), поскольку вам нужно будет пройти по внутреннему массиву, который поддерживает порядок. При удалении по индексу сложность составляет O (1), поскольку у вас есть прямой доступ к значению как в массиве, так и в объекте.
OrderedMap.prototype.remove = function(key) {
var index = this._array.indexOf(key);
if(index == -1) {
throw new Error('key does not exist');
}
this._array.splice(index, 1);
delete this.map[key];
};
Поиск будет в O (1). Получить значение по ключу из ассоциативного массива (объекта).
OrderedMap.prototype.get = function(key) {
return this.map[key];
};
Обход будет упорядочен и может использовать любой из подходов. Если требуется упорядоченный обход, создайте массив с объектами (только значениями) и верните его. Будучи массивом, он не поддерживает доступ по ключу. Другой вариант - попросить клиента предоставить функцию обратного вызова, которая должна применяться к каждому объекту в массиве.
OrderedMap.prototype.forEach = function(f) {
var key, value;
for(var i = 0; i < this._array.length; i++) {
key = this._array[i];
value = this.map[key];
f(key, value);
}
};
См. Реализацию Google LinkedMap из библиотеки Closure для документации и исходного кода для такого класса.
Единственный случай, когда Chrome не сохраняет порядок ключей в объектном литерале, - это если ключи являются числовыми.
var properties = ["damsonplum", "9", "banana", "1", "apple", "cherry", "342"];
var objLiteral = {
damsonplum: new Date(),
"9": "nine",
banana: [1,2,3],
"1": "one",
apple: /.*/,
cherry: {a: 3, b: true},
"342": "three hundred forty-two"
}
function load() {
var literalKeyOrder = [];
for (var key in objLiteral) {
literalKeyOrder.push(key);
}
var incremental = {};
for (var i = 0, prop; prop = properties[i]; i++) {
incremental[prop] = objLiteral[prop];
}
var incrementalKeyOrder = [];
for (var key in incremental) {
incrementalKeyOrder.push(key);
}
alert("Expected order: " + properties.join() +
"\nKey order (literal): " + literalKeyOrder.join() +
"\nKey order (incremental): " + incrementalKeyOrder.join());
}
В Chrome вышеприведенный пример дает: "1,9,342,малиновая слива,банан,яблоко,вишня".
В других браузерах получается "damsonplum,9,banana,1,apple,cherry,342".
Так что если ваши клавиши не являются цифровыми, я думаю, что даже в Chrome вы в безопасности. А если ваши ключи числовые, возможно, просто добавьте к ним строку.