0

しばらくの間、データ構造の問題について熟考してきましたが、良い解決策が思い浮かびません。解決策が単純であるという気持ちを振り払うことはできませんが、それが見えていないだけなので、皆さんが助けてくれることを願っています!

問題は次のとおりです。メモリ内に大量のオブジェクトのコレクションがあります。それぞれに多数のデータ フィールドがあります。ID などの一部のデータ フィールドはオブジェクトごとに一意ですが、名前などの他のデータ フィールドは複数のオブジェクトに表示できます。

class Object {
    size_t id;
    std::string name;
    Histogram histogram;
    Type type;
    ...
};

これらのオブジェクトを整理して、(オブジェクトの数が比較的多く、つまり数百万の場合でも) 任意の数のオブジェクト メンバーを指定してコレクションをフィルター処理し、指定されていないすべてのメンバーをカウントできるようにする必要があります。ワイルドカードとして。たとえば、指定した を指定した場合、nameその名前メンバーがその名前と等しいすべてのオブジェクトを取得したいとします。ただし、クエリにヒストグラムを追加する場合は、nameとhistogramフィールドの両方で一致するオブジェクトのみを返すクエリが必要です。たとえば、関数が欲しい

std::set<Object*> retrieve(size_t, std::string, Histogram, Type)

それは両方できる

retrieve(42, WILDCARD, WILDCARD, WILDCARD)

としても

retrieve(42, WILDCARD, WILDCARD, Type_foo)

2 番目の呼び出しは、最初の呼び出しよりも少ないか同じ数のオブジェクトを返します。このようなクエリを可能にし、数百万のオブジェクト数に対して合理的な時間内に構築およびクエリを実行できるデータ構造はどれですか?

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

4

1 に答える 1

0

まず、Boost Multi-indexを使用して、 のさまざまなメンバーに対する効率的なルックアップを実装できますObject。これは、考慮する要素の数を制限するのに役立ちます。2 番目のステップとして、ラムダ式を使用してstd::find_if、最初の要素を取得するための述語を実装するかstd::copy_if、すべての要素をターゲット シーケンスにコピーするために使用できます。ブーストを使用する場合は、ブースト範囲をフィルタリングで使用できます。

于 2013-06-21T07:30:42.363 に答える