Структура данных Javascript для быстрого поиска и упорядоченного цикла?

Ответ 1

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

Ответ 2

Единственный экземпляр, в котором 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 вы в безопасности. И если ваши ключи являются числовыми, возможно, просто добавьте их со строкой.

Ответ 3

Как было отмечено, если ваши ключи являются числовыми вы можете добавить их с помощью строки для сохранения порядка.

var qy = {
  _141: '256k AAC',
   _22: '720p H.264 192k AAC',
   _84: '720p 3D 192k AAC',
  _140: '128k AAC'
};

Пример