boost multi_index の実装方法
-
25-09-2019 - |
質問
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*
配列に格納されているオブジェクトを指す値。これでいい?
解決
は根本的な構造上の簡単な説明は、<こちら与えています/
:>、以下に引用実装は、同じように、お気に入りstd::set
実装言う、ポインタと連動したノードに基づいています。私はこの上で少し詳しく説明します:std::set
は通常のノードが
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;
};
(現実はもっと複雑であり、これらのノードは、いくつかのメタプログラミングなどを介して生成されていますが、アイデアを得る)[...]
他のヒント
概念的にはそうです。
Boost.MultiIndex について私が理解していることから(使用したことはありますが、実装は見ていません)、2 つの例 ordered_unique
インデックスは実際に 2 つのソートされた連想コンテナーを作成します (例: std::map
) ポインタ/参照/インデックスを共通のセットに保存します。 employee
s.
いずれにせよ、あらゆる employee
はマルチインデックスコンテナに一度だけ保存されますが、 map<string,employee>
そして map<int,employee>
すべての従業員を 2 回保存することになります。
複数のインデックスを持つコンテナー内に実際に (動的) 配列が存在する可能性は十分にありますが、 保証なし これが真実であること:
ランダムアクセスインデックス]メモリの連続性を提供しないでください、
std::vector
sは、メモリの単一ブロックに要素が互いに隣接して保存されます。
また、 Boost.Bimap は Boost.MultiIndex に基づいています 前者では、その「バックボーン」構造のさまざまな表現が可能になります。
実際にはそうではないと思います。
にあるものに基づいて、 detail/node_type.hpp
. 。のような気がします std::map
ノードには値とインデックスの両方が含まれます。ただし、この場合、さまざまなインデックスが互いに異なるため、ノードのインターリーブは実際には、フォローしているインデックスに応じて異なります。
ただし、これについてはよくわかりません。Boost ヘッダーは間違いなく解析が困難ですが、メモリの観点から考えると、次のことは理にかなっています。
- 割り当てが少なくなります:より高速な割り当て/割り当て解除
- キャッシュの局所性が向上
ただし、ゴアについて知っている人がいたら、明確な回答をいただければ幸いです。