4

私はboost::multi_index_containerその要素が次のような構造体であるを持っています：

struct Elem {
    A a;
    B b;
    C c;
};

（データベースの意味での）メインキーはcomposite_keyのとaですb。さまざまなタイプのクエリを実行するための他のキーが存在します。

ここで、のすべての異なる値のセットを取得する必要がありますc。これらの値は決して一意ではありませんが、すべてのエントリを反復処理する（順序付けられている場合でも）、またはの異なる値の数がエントリの総数（たとえば、10）よりも<<であると予想されることを考えると、使用するstd::uniqueのはかなり無駄に思えますc1000まで）。

この結果をより効率的に取得する簡単な方法がありませんか？

4

2 に答える 2

1

Boost.MultiIndexのドキュメントを調べましたが、やりたいことを実行する方法が見つからないようです。それが実行可能かどうかを知りたいです。

おそらく、あなたができる最善のことは、std::map<C, size_t>あなたと一緒に（またはハッシュマップ）multi_index_containerを維持し、両方を「同期」させておくことです。

マップは、C値をその発生回数（頻度）に関連付けます。これは基本的にC値のヒストグラムです。にを追加するたびに、ヒストグラムの対応する頻度をインクリメントしますElem。からmulti_index_containerを削除すると、ヒストグラムの対応する頻度が減少します。頻度がゼロに達したら、そのエントリをヒストグラムから削除します。Elemmulti_index_counter

個別のC値のセットを取得するに<key,value>は、ヒストグラムのペアを反復処理し、key各ペアの部分を確認するだけです。を使用した場合std::map、個別のC値はソートされて出力されます。

個別のC値のセットを一度だけ（またはめったに）調べない場合は、上記のアプローチはやり過ぎかもしれません。より簡単なアプローチは、すべてのC値をに挿入してstd::set<C>から、セットを反復処理して個別のC値を取得することです。

個別のCのセットは、Cの総数よりもはるかに少ないとおっしゃいました。したがって、このアプローチは、Cをaにコピーし、ベクトルをソートしてから実行するstd::set<C>よりもはるかに少ないスペースを浪費する必要があります。std::vectorstd::unique

セットへのコピーとベクトルへのコピー、ソート、実行の時間計算量を比較してみましょうunique。NをC値の総数、Mを個別のC値の数とします。私の考えでは、セットアプローチはO（N * log（M））の時間計算量を持つ必要があります。Mは小さく、Nが高くてもあまり成長しないため、複雑さは事実上O（N）になります。一方、並べ替えと一意の手法では、時間計算量がO（N * log（N））である必要があります。

于 2011-02-17T03:22:38.563 に答える