Создайте структуру данных самостоятельно.Сохраните порядок в массиве, который является внутренним по отношению к структуре.Храните объекты, сопоставленные ключом, в обычном объекте.Давайте назовем его 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 из библиотеки закрытиядокументация и источник для такого класса.