1

boost::multi_index ライブラリ内のイテレータの射影の複雑さについて何か知っている人はいますか? ドキュメントはここboost::multi_index project of iteratorsにありますが、操作の複雑さについては述べていません。

基本的な考え方は、インデックス内のオブジェクトへの反復子を取得し、これを 2 番目のインデックスに射影して、2 番目のインデックス内の同じオブジェクトへの反復子を取得できるというものです。これが O(1) 操作の場合、効率的に 2 つのインデックスを維持できます。1 つは高速で検索可能で、もう 1 つは低速です。私が理解しているように、反復子の射影により、インデックス内でより高速に検索されるオブジェクトを見つけて、それを検索速度の遅いインデックスに射影することができます。

イテレータの射影のための単純な O(1) ルックアップなのか、それとも 2 番目のインデックスで検索操作を効果的に開始するだけなのか、したがって射影先の特定のインデックスに依存して遅くなるのかを知りたいと思っています。 O(1) よりも。

助けてくれてありがとう！

4

1 に答える 1

2

documentationで指定されているように、一定の時間であり、実際、次のように高速です。

  template<int N,typename IteratorType>
  typename nth_index_iterator<N>::type project(IteratorType it)
  {
    typedef typename nth_index<N>::type index_type;
    ...
    return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
  }

これは、任意のインデックス イテレータが保持する内部ノード ポインタの再ラップにすぎません。

于 2013-12-10T13:23:30.687 に答える