0

1つはvec1{e1、e2、e3、e4}で、もう1つはvec2 {e2、e4、e5、e7}の2つのベクトルがあります。

上記のベクトルから3つのベクトルを効果的に取得する方法。1。vec1でのみ使用可能な要素があります。同様に2にはvec2要素のみがあり、3。共通の要素があります。

4

4 に答える 4

6

std::set_intersection両方のベクトルがソートされている場合は、トリックを実行する必要があります：http: //msdn.microsoft.com/en-us/library/zfd331yx.aspx

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3));

カスタム述語も比較に使用できます。

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3), my_equal_functor());

並べ替えられていない場合は、もちろん最初に並べ替えることができます。または、vec1を繰り返し処理し、要素ごとにstd :: findを使用して、vec2に存在するかどうかを確認します。

于 2009-02-02T17:04:32.523 に答える
3

あなたが求めているのは、それが他の2つvec3の交差点であることです。Jalf は、ヘッダーの関数vec3を使用してデータを取り込む方法を示しています。ただし、セット関数が機能するには、ベクトルをソートする必要があることに注意してください。std::set_intersection<algorithm>

次に、 とが自分自身との違いになりたいvec1とvec2します。セット表記：vec3

vec1 := vec1 \ vec3;
vec2 := vec2 \ vec3;

そのために関数を使用できstd::set_differenceますが、ベクトルをその場で変更するために使用することはできません。差を保持するには、別のベクトルを計算する必要があります。

std::vector<foo> temp;
std::set_difference(vec1.begin(), vec1.end(),
                    vec3.begin(), vec3.end(),
                    std::back_inserter(temp));
vec1 = temp;
temp.clear();
std::set_difference(vec2.begin(), vec2.end(),
                    vec3.begin(), vec3.end(),
                    std::back_inserter(temp));
vec2 = temp;
于 2009-02-02T17:15:23.830 に答える
1

要素数が少ない場合は、実装が簡単で実行時間が O(n 2 )の単純なアプローチを使用できます。

多数の要素がある場合は、そのうちの 1 つからハッシュ テーブルを作成し、その中で他のベクターの要素を検索できます。または、それらの 1 つを並べ替えて、それをバイナリ検索することもできます。

于 2009-02-02T17:08:53.530 に答える
0

あなたが説明する問題は、ベクトルの交差です。これは、入力ベクトルのサイズによって異なります。

両方のベクトルのサイズが互いに近い場合は、(マージソートのように) マージが最適です。1 つのベクトルが他のベクトルよりもはるかに小さい場合は、次の手順を実行します。 小さい方のベクトルの各要素について、バイナリ検索を使用して大きい方のベクトル内のその要素を検索します。

これは、逆インデックスを交差させる必要がある情報検索でよくある問題です。これについてはいくつかの研究論文があります。

于 2009-02-02T17:09:40.627 に答える