1

私のプロジェクトでは、いくつかのリレーショナル データ (それらの間の関係を表す 2 つの類似したオブジェクトを保持する構造体) を持つベクトルがあり、ベクトル内のすべてのデータ間の関係の組み合わせを確認する必要があります。

私がやっていることは、ベクトルを反復処理することであり、最初の for ループ内で、データ間の関係を探すために再度反復処理を行っています。

これは私がやっていることの単純化されたモデルです

for(a=0; a<vec.size(); a++)
{
    for(b=0; b<vec.size(); b++)
    {
        if(vec[a].something==vec[b].something) {...}
    }
}

私のコレクションには 2800 の要素があり、これは 2800*2800 回反復することを意味します...

この種の操作には、どのようなデータ構造が適していますか? for_each を使用すると、このようにベクトルをトラバースするよりも速くなりますか?

前もって感謝します！

vec には、2 つの整数で構成される 2 つの構造体があり、何も順序付けされていません。

4

3 に答える 3

4

いいえ、 for_each は引き続き同じことを行います。

ハッシュ マップを使用すると、問題が改善される可能性があります。空のハッシュから始めて、リストを反復処理します。各要素について、それがハッシュに含まれているかどうかを確認します。そうでない場合は、追加します。そうであれば、重複があり、コードを実行します。

C++ では、std::map を使用できます。C にはマップ データ構造が組み込まれていないため、独自に作成する必要があります。

高レベルの擬似コードは次のようになります

foreach (element in array)
  if map.has_key(element)
    do_stuff(element)
  else
    map.add_key(element)
于 2013-07-25T18:30:16.410 に答える
0

ベクトルに次のような「関係」構造が含まれていると仮定します。

class Entity;

struct Relation {
  Entity* something;
  Entity* relative;
};

そして、あなたは「関係」のベクトルを持っています:

std::vector<Relation> ties;

私の理解が正しければ、関係をセグメント化し、各エンティティの関係のリストを作成する必要があります。これは、マップで表すことができます。

std::map<Entity*,std::vector<Relation*>> entityTiesIndex;

次に、すべての関係を1 回スキャンして、各エンティティの関係を収集できます。

for (int i=0; i < ties.size(); ++i ) {
  Relation* relation = &ties[i];
  entityTiesIndex[relation->something].push_back(relation);
}

コンテナが変更されると変更される可能性があるため、コンテナ要素への参照に関する通常の免責事項に注意してください。

これが理にかなっていることを願っています。

于 2013-07-25T19:06:31.660 に答える