22

高速ルックアップ（連想配列の場合のようにキーによる）と順序付きループの両方に使用できるデータ構造またはパターンがJavascriptにありますか？

現在、オブジェクトリテラルを使用してデータを保存していますが、プロパティ名をループするときにChromeが順序を維持しないことに気づきました。

Javascriptでこれを解決する一般的な方法はありますか？

ヒントをありがとう。

4

3 に答える 3

33

自分でデータ構造を作成します。構造体の内部にある配列に順序を格納します。キーによってマップされたオブジェクトを通常のオブジェクトに格納します。OrderedMapマップ、配列、および 4 つの基本的なメソッドを持つ、それを呼び出しましょう。

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

トラバーサルが注文され、いずれかのアプローチを使用できます。順序付けられたトラバーサルが必要な場合は、オブジェクト (値のみ) で配列を作成し、それを返します。配列であるため、キー付きアクセスはサポートされません。もう 1 つのオプションは、配列内の各オブジェクトに適用する必要があるコールバック関数を提供するようにクライアントに依頼することです。

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

このようなクラスのドキュメントとソースについては、Closure Library からのGoogle のLinkedMapの実装を参照してください。

于 2010-08-23T17:57:22.233 に答える
3

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,banana,apple,cherry" を生成します。

他のブラウザでは、「damsonplum,9,banana,1,apple,cherry,342」を生成します。

したがって、キーが数字でない限り、Chrome でも安全だと思います。また、キーが数値の場合は、先頭に文字列を追加するだけです。

于 2010-08-23T18:07:26.483 に答える
2

前述 のように、キーが数値の場合、順序を維持するために文字列を前に追加できます。

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

例

于 2014-08-10T03:38:33.970 に答える