существует ли структура данных или шаблон в Javascript, который может использоваться как для быстрого поиска (по ключу, так и для ассоциативных массивов) и для упорядоченного цикла?
Правильно, теперь я использую литералы объектов для хранения своих данных, но я просто отключил, что Chrome не поддерживает порядок при переходе по именам свойств.
Есть ли общий способ решить эту проблему в Javascript?
Спасибо за любые подсказки.
Создайте структуру данных самостоятельно. Сохраните порядок в массиве, который является внутренним для структуры. Храните объекты, сопоставленные ключом в обычном объекте. Позвольте называть его 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, банан, яблоко, вишня".
В других браузерах он производит "damsonplum, 9, banana, 1, apple, cherry, 342".
Поэтому, если ваши ключи не являются числовыми, я думаю, что даже в Chrome вы в безопасности. И если ваши ключи являются числовыми, возможно, просто добавьте их со строкой.
Как было отмечено, если ваши ключи являются числовыми вы можете добавить их с помощью строки для сохранения порядка.
var qy = {
_141: '256k AAC',
_22: '720p H.264 192k AAC',
_84: '720p 3D 192k AAC',
_140: '128k AAC'
};