boost multi_index の実装方法

Question

Boost.MultiIndex がどのように実装されているかを理解するのが少し難しいです。次のものがあるとしましょう:

typedef multi_index_container<
    employee,
    indexed_by<    
        ordered_unique<member<employee, std::string, &employee::name> >,
        ordered_unique<member<employee, int, &employee::age> >
    > 
> employee_set;

配列が 1 つあると想像しますが、 Employee[], 、実際には employee オブジェクトと 2 つのマップ

map<std::string, employee*>
map<int, employee*>

名前と年齢をキーにします。各マップには、 employee* 配列に格納されているオブジェクトを指す値。これでいい？

Answer 1

は根本的な構造上の簡単な説明は、<こちら与えています/

：>、以下に引用

実装は、同じように、お気に入りstd::set実装言う、ポインタと連動したノードに基づいています。私はこの上で少し詳しく説明します：std::setは通常のノードが

のように見えるRB-ツリーとして実装されています

struct node
{
  // header
  color      c;
  pointer    parent,left,right;
  // payload
  value_type value;
};

さて、multi_index_containerのノードは基本的に多くの指標としてヘッダならびにペイロードとして有する「マルチノード」です。例えば、2いわゆる順序付けインデックス付きmulti_index_containerは内部ノードを使用するようになります

struct node
{
  // header index #0
  color      c0;
  pointer    parent0,left0,right0;
  // header index #1
  color      c1;
  pointer    parent1,left1,right2;
  // payload
  value_type value;
};

（現実はもっと複雑であり、これらのノードは、いくつかのメタプログラミングなどを介して生成されていますが、アイデアを得る）[...]

Answer 2

概念的にはそうです。

Boost.MultiIndex について私が理解していることから（使用したことはありますが、実装は見ていません）、2 つの例 ordered_unique インデックスは実際に 2 つのソートされた連想コンテナーを作成します (例: std::map) ポインタ/参照/インデックスを共通のセットに保存します。 employees.

いずれにせよ、あらゆる employee はマルチインデックスコンテナに一度だけ保存されますが、 map<string,employee> そして map<int,employee> すべての従業員を 2 回保存することになります。

複数のインデックスを持つコンテナー内に実際に (動的) 配列が存在する可能性は十分にありますが、 保証なし これが真実であること:

ランダムアクセスインデックス]メモリの連続性を提供しないでください、 std::vectorsは、メモリの単一ブロックに要素が互いに隣接して保存されます。

また、 Boost.Bimap は Boost.MultiIndex に基づいています 前者では、その「バックボーン」構造のさまざまな表現が可能になります。

Answer 3

実際にはそうではないと思います。

にあるものに基づいて、 detail/node_type.hpp. 。のような気がします std::map ノードには値とインデックスの両方が含まれます。ただし、この場合、さまざまなインデックスが互いに異なるため、ノードのインターリーブは実際には、フォローしているインデックスに応じて異なります。

ただし、これについてはよくわかりません。Boost ヘッダーは間違いなく解析が困難ですが、メモリの観点から考えると、次のことは理にかなっています。

• 割り当てが少なくなります:より高速な割り当て/割り当て解除
• キャッシュの局所性が向上

ただし、ゴアについて知っている人がいたら、明確な回答をいただければ幸いです。