2

久しぶりの読者初ポスター！私はboost::multi_indexコンテナのものをいじっていて、うまくいけばブーストまたはC++コンテナの専門家が知っているかもしれないかなり深い質問があります(C++コンテナに関する私の知識はかなり基本的です)。参考までに、複合キーに関するブーストのドキュメントは次の場所にあります: boost::multi_index 複合キー。

複合キーを使用する場合、ドキュメントには、「複合キーは辞書式の順序でソートされます。つまり、ソートは最初のキーで実行され、最初のキーが等しい場合は 2 番目のキーで実行される、など」と記載されています。これは、特定の 2 部構成の複合キーのルックアップに O(n=1) 時間がかかるように構造が格納されていることを意味しますか、つまり、各項目への直接のポインターがあるようにコンテナーがソートされているか、ブーストを行いますか?コンテナは、複合キーの最初の部分に一致するリストを取得し、キーの 2 番目の部分に一致する項目の検索を実行する必要があるため、処理が遅くなりますか?

たとえば、2 つの異なるインデックスを使用して 2 つのコンテナーを手動で維持し、特定の 2 部構成のクエリに一致するアイテムを見つけたい場合、クエリの最初の部分に一致するすべてのアイテムの最初のコンテナーをフィルター処理してから、クエリの 2 番目の部分に一致するアイテムの結果。したがって、この手動の方法では、実質的に 2 つの検索が必要になります。ブーストは効果的にこれを行いますか、それとも複合キーを使用して何らかの形で効率を向上させますか?

うまくいけば、私はここで自分自身を説明しましたが、質問をしてください。私の言いたいことを正確に明確にするために最善を尽くします!

4

1 に答える 1

4

あなたが説明したように、複合キーを含むルックアップは2段階のプロセスを経ません。composite_key-induced 順序付けは通常の順序付けです。唯一の特別な点は、1 つではなく 2 つ以上の要素キーに依存することです。

たぶん、例が明らかになるでしょう。のこの使用法を考えてみましょうcomposite_key:

struct element
{
  int x,y,z;
};

typedef multi_index_container<
  element,
  indexed_by<
    ordered_unique<
      composite_key<
        element,
        member<element,int,&element::x>,
        member<element,int,&element::y>,
        member<element,int,&element::z>
      >
    >
  >
> multi_t;

結果として得られるコンテナは、ある意味でこれと同等です:

struct element_cmp
{
  bool operator()(const element& v1, const element& v2)const
  {
    if(v1.x<v2.x)return true;
    if(v2.x<v1.x)return false;
    if(v1.y<v2.y)return true;
    if(v2.y<v1.y)return false;
    return v1.z<v2.z;
  }
};

typedef std::set<element,element_cmp> set_t;

composite_keyは、 のコードと同等のコードを自動的に生成しelement_cmp::operator()、さらに最初の n 個のキーだけを検索できますが、基本的なデータ構造は を使用した場合とは異なりstd::setます。

于 2013-12-01T19:49:30.647 に答える