21

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;

Employee[]実際にオブジェクトを格納する1 つの配列employeeと 2 つのマップがあるとします。 

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

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

4

3 に答える 3

33

基礎となる構造についての簡単な説明をここに示します。以下に引用します。

実装は、お気に入りのstd::set実装と同じように、ポインターで相互リンクされたノードに基づいています。これについて少し詳しく説明します。Astd::setは通常、ノードが次のように見えるrbツリーとして実装されます。

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

さて、multi_index_containerのノードは基本的に「マルチノード」であり、ペイロードだけでなくインデックスと同じ数のヘッダーがあります。たとえば、multi_index_container2つのいわゆる順序付きインデックスを持つは、次のような内部ノードを使用します。

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

（現実はもっと複雑です。これらのノードはいくつかのメタプログラミングなどによって生成されますが、あなたはその考えを理解します）[...]

于 2010-11-17T19:32:12.830 に答える
4

概念的には、はい。

Boost.MultiIndex について私が理解していることから (私はそれを使用しましたが、実装は見ていません)、2 つのインデックスを使用した例では、ポインター/参照/インデックスをs の共通セットに格納ordered_uniqueする 2 つの並べ替えられた連想コンテナー ( など) が実際に作成されます。 .std::mapemployee

いずれにせよ、everyemployeeはマルチインデックス コンテナーに 1 回だけ格納されますが、 と を組み合わせるとmap<string,employee>、map<int,employee>すべての従業員が 2 回格納されます。

複数インデックスのコンテナー内に (動的) 配列が実際に存在する可能性は非常に高いですが、これが正しいという保証はありません。

std::vector[ランダム アクセス インデックス] は、要素がメモリの 1 つのブロックに互いに隣接して格納される s のプロパティである、メモリの連続性を提供しません。

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

于 2010-11-17T16:09:35.540 に答える
2

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

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

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

  • より少ない割り当て: より高速な割り当て/解放
  • より良いキャッシュの局所性

誰かがマチについて知っていれば、決定的な答えをいただければ幸いです。

于 2010-11-17T16:39:24.540 に答える