マップ内の挿入オーダーを効率的に保存するにはどうすればよいですか?

マップ内の挿入順序の保持

データ構造の領域では、マップはキーと値のペアを格納するコンテナーです。マップの一般的な要件は、これらのペアが挿入された順序を維持し、マップを反復処理するときに追加された順序で要素にアクセスできるようにすることです。ただし、標準マップのデフォルトの実装では、この挿入順序の保持は保証されません。

このニーズに対処するために、いくつかの代替手段が検討できます。 1 つのオプションは、挿入順序の維持を可能にするペアのベクトルを利用することです。ただし、10,000,000 を超えるキーと値のペアを反復するなど、多数の操作が含まれるシナリオでは、パフォーマンス上の懸念により、ベクターは最適な選択ではない可能性があります。

あるいは、キーの数が限られているシステムの場合は、 - 値のペア (約 50 ペアの質問のシナリオなど)、マップをベクトルに変換し、適切な順序で標準の並べ替えライブラリ (std::sort) を使用します。ファンクターなどのコンパレータは、実行可能なアプローチになる可能性があります。

マップ内の挿入順序を保持するためのもう 1 つのオプションは、Boost Multi-Index Library を利用することです。このライブラリは、組み合わせてマルチインデックス コンテナーを作成できるさまざまなインデックス タイプを提供します。たとえば、質問のシナリオでは、マルチ インデックス マップを 2 つのインデックスで使用できます。1 つはランダム アクセス (挿入順序の保持) 用で、もう 1 つはハッシュされた一意のインデックスで効率的な文字列検索用です。次のコード スニペットは、このシナリオでマルチインデックス マップを実装する方法を示しています。

struct value_t {
  string s;
  int i;
};

struct string_tag {};

typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique<tag<string_tag>, member<value_t, string, &value_t::s>>
    >
> values_t;

以上がマップ内の挿入オーダーを効率的に保存するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。