1

次のシナリオに最適なデータ構造を探しています。

インデックスiがあり、それぞれについて次の操作をサポートする必要があります1Foo ：オブジェクト（以下を参照）をすばやく検索します。各オブジェクトはdouble値に関連付けられています。

だから私はこれをしました：

struct Foo {
  int a, b, c;
};

typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;

しかし、次の操作に対しても非常に高速なサポートを提供する必要があるため、非効率的であることがわかります2 ：およびFooに特定の値を持つすべてのを削除します（関連するdouble値と一緒に）。ab

この操作2を実行するには、ベクトル内のマップを反復処理し、Foosの値aとb値を確認して、マップから1つずつ消去する必要があります。これは非常にコストがかかるようです。

だから私は今、代わりにこのデータ構造を検討しています：

struct Foo0 {
  int a, b;
};

typedef std::multimap<Foo0, std::map<int, double> > VecElem;
std::vector<VecElem> vec;

これにより、上記の操作1と2の両方が高速にサポートされます。それは合理的ですか？ネストされたコンテナ構造からのオーバーヘッドはたくさんありますか？

注：各マルチマップには通常、（タイプの）1つまたは2つのキーしかなくFoo0、それぞれに（タイプの）約5〜20の値がありますstd::map<int,double>。

4

2 に答える 2

2

見出しの質問に答えるには：はい、STLコンテナをネストすることはまったく問題ありません。ただし、使用プロファイルによっては、これにより、舞台裏で過度のコピーが発生する可能性があります。より良いオプションは、を使用してトップレベルコンテナを除くすべてのコンテンツをラップすることですBoost::shared_ptr。これにより、コンテナのハウスキーピングでは、ネストされたコンテナのコンテンツ全体のディープコピーが不要になります。VecElemこれは、トップレベルでの挿入と削除に多くの時間を費やすことを計画している場合に当てはまります-直接のvector場合は高価です。VecElemmultimap

データ構造のメモリオーバーヘッドは、同等の機能を使用して設計できるものよりも大幅に悪化することはなく、正常な状態よりも多くの時間を費やす予定がない限り、改善される可能性が高くなります。

于 2010-09-22T16:35:46.017 に答える
1

さて、あなたはこのアイデアに合理的なスタートを切っています...しかし、最初に対処しなければならないいくつかの質問があります。

たとえば、タイプはFoo変更可能ですか？そうである場合は、タイプを作成する際に注意する必要がありますFoo0（ええと...混乱を避けるために別の名前を聞くことをお勧めします）。への変更Fooは無効になる可能性があるためFoo0です。

次に、挿入/更新で適切に機能するためにこの構造も必要かどうかを判断する必要があります。の人口Fooが静的で不変の場合-これは問題ではありませんが、そうでない場合は、との維持に多くの時間を費やすことになる可能性がVecありVecElemます。

STLコンテナをネストするという問題に関する限り、これは問題ありません。多くの場合、任意の複雑な構造を作成するために使用されます。

于 2010-09-22T16:36:00.590 に答える