¿Estructura de datos de Javascript para una búsqueda rápida y un bucle ordenado?

Question

¿existe una estructura de datos o un patrón en Javascript que se pueda usar tanto para la búsqueda rápida (por clave, como con las matrices asociativas) como para el bucle ordenado?

Bien, ahora estoy usando literales de objeto para almacenar mis datos, pero acabo de descubrir que Chrome no mantiene el orden cuando se repiten los nombres de las propiedades.

¿Hay una manera común de resolver esto en Javascript?

Gracias por cualquier pista.

Answer 1

Cree usted mismo una estructura de datos. Almacene el pedido en una matriz que es interna a la estructura. Almacene los objetos asignados por una clave en un objeto regular. Llamémoslo OrderedMap que tendrá un mapa, una matriz y cuatro métodos básicos.

OrderedMap 
    map 
    _array 

    set(key, value) 
    get(key) 
    remove(key) 
    forEach(fn) 

function OrderedMap() { 
    this.map = {}; 
    this._array = []; 
} 

Cuando inserte un elemento, agréguelo al arreglo en la posición deseada así como también al objeto. La inserción por índice o al final está en 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; 
    } 
}; 

Al eliminar un objeto, quítelo de la matriz y del objeto. Si se elimina mediante una clave o un valor, la complejidad es O (n) ya que tendrá que atravesar la matriz interna que mantiene el orden. Al eliminar por índice, la complejidad es O (1) ya que tiene acceso directo al valor tanto en la matriz como en el objeto.

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]; 
}; 

Las búsquedas estarán en O (1). Recupere el valor por clave de la matriz asociativa (objeto).

OrderedMap.prototype.get = function(key) { 
    return this.map[key]; 
}; 

Traversal se ordenará y puede utilizar cualquiera de los enfoques. Cuando se requiere un recorrido ordenado, cree una matriz con los objetos (solo valores) y devuélvala. Al ser una matriz, no admitiría el acceso por clave. La otra opción es pedirle al cliente que proporcione una función de devolución de llamada que se debe aplicar a cada objeto en la matriz.

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); 
    } 
}; 

Véase aplicación de Google de un LinkedMap de la Biblioteca de cierre para la documentación y la fuente para dicha clase.

Answer 2

La única instancia en la que Chrome no mantiene el orden de las claves en un objeto literal parece ser si las teclas son numéricas.

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()); 
    } 

En Chrome, lo anterior produce: "1,9,342, damsonplum, banana, apple, cherry".

En otros navegadores, produce "damsonplum, 9, banana, 1, apple, cherry, 342".

Así que a menos que sus llaves sean numéricas, creo que incluso en Chrome, está a salvo. Y si tus llaves son numéricas, tal vez solo anteponga una cuerda.

Answer 3

Como has been noted, si sus claves son numéricas puede anteponerlas a una cadena para conservar el orden.

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

Example