2つのstd :: vectorに同じ要素だけが含まれているかどうかを確認するにはどうすればよいですか？

Question

私は以下のような2つのベクトルの要素を、比較するためのアルゴリズムや標準ライブラリ関数が必要になります。

class Utility 
{ 
    template <class T> 
    static bool CheckIfVectorsEquivalent( const std::vector<T> & Vec1, 
              const std::vector<T> & Vec2) 
    { 
     // ??? 
    } 
}; 

は、以下の仕様の下での作業：

std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8; 

// Returns false when not all the elements are matching between vectors 
v1.push_back(1); 
v1.push_back(3); 
v1.push_back(5); 
v2.push_back(2); 
v2.push_back(3); 
v2.push_back(8); 
Utility::CheckIfVectorsEquivalent(v1, v2); // Must return false 

// Returns true when all the elements match, even if the are not in the same order 
v3.push_back(3); 
v3.push_back(1); 
v3.push_back(7); 
v4.push_back(7); 
v4.push_back(3); 
v4.push_back(1); 
Utility::CheckIfVectorsEquivalent(v3, v4); // Must return true 

// Returns false when one of the vectors is subset of the other one 
v5.push_back(3); 
v5.push_back(1); 
v5.push_back(7); 
v6.push_back(7); 
v6.push_back(3); 
v6.push_back(1); 
v6.push_back(18); 
v6.push_back(51); 
Utility::CheckIfVectorsEquivalent(v5, v6); // Must return false 

// Returns true when the both vectors are empty 
Utility::CheckIfVectorsEquivalent(v7, v8); // Must return true 

は、任意の（STL付き）標準的な方法はありますこれをする？そうでない場合は、どうやってこのアルゴリズムを書くことができますか？それは私をあまりにも混乱させた。

Answer 1

あなただけのC++ 11ソリューションと一緒に暮らすことができる場合は、今後のブースト1で、その後、それを行うことができない場合は、std::is_permutationはあなたが

template <class FI1, class FI2> 
bool is_permutation (FI1 first, FI1 last, FI2 d_first); 

たい正確に何です。50リリースでは、同じインタフェースで

boost::algorithm::is_permutation 

が存在します。

Answer 2

標準的な方法は、これらの2つのベクトルをソートし、対応する値を比較する演算子==を使用します。

このアルゴリズムを実現する試料溶液である：

#include <vector> 
#include <algorithm> 

template<typename T> 
bool compare(std::vector<T>& v1, std::vector<T>& v2) 
{ 
    std::sort(v1.begin(), v1.end()); 
    std::sort(v2.begin(), v2.end()); 
    return v1 == v2; 
} 

その複雑さはO（N *ログ（N））のでソート。

Answer 3

各ベクターからmultisetを作成して、それらの値が等しいかどうか比較してください。

Answer 4

O（n）のソートされていない入力に対して、この問題に対する解決策があります：

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <boost/function_output_iterator.hpp> 

template <typename T> 
T xorfunc(const T& a, const T& b) { 
    return a^b; 
} 

template <typename T> 
bool compare(const std::vector<T>& v1, const std::vector<T>& v2) { 
    if (v1.size() != v2.size()) 
    return false; 

    T result = 0; 
    std::transform(v1.begin(), v1.end(), v2.begin(), boost::make_function_output_iterator([&result](const T& r) { result ^= r; }), std::ptr_fun(&xorfunc<T>)); 
    return !result; 
} 

整数入力のために動作し、対になった値の任意の組み合わせのためにそのa^b^c^d == 0事実を利用します。それは偽のネガティブを与えることは決してありません。は潜在的に偽陽性を示しますが、O（n）の空間/時間でさらに偽陽性を減らすことができます。ほとんどがネガティブを打つ場合は、プレソート+比較ステップとして役立ちます。それはあなたが示されたすべてのテストケースのために働く：

int main() { 
    std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8; 

    // Returns false when not all the elements are matching between vectors 
    v1.push_back(1); 
    v1.push_back(3); 
    v1.push_back(5); 
    v2.push_back(2); 
    v2.push_back(3); 
    v2.push_back(8); 
    std::cout << compare(v1, v2) << " (false)" << std::endl; // Must return false 

    // Returns true when all the elements match, even if the are not in the same order 
    v3.push_back(3); 
    v3.push_back(1); 
    v3.push_back(7); 
    v4.push_back(7); 
    v4.push_back(3); 
    v4.push_back(1); 
    std::cout << compare(v3, v4) << " (true)" << std::endl; // Must return true 

    // Returns false when one of the vectors is subset of the other one 
    v5.push_back(3); 
    v5.push_back(1); 
    v5.push_back(7); 
    v6.push_back(7); 
    v6.push_back(3); 
    v6.push_back(1); 
    v6.push_back(18); 
    v6.push_back(51); 
    std::cout << compare(v5, v6) << " false" << std::endl; // Must return false 

    // Returns true when the both vectors are empty 
    std::cout << compare(v7, v8) << " true" << std::endl; // Must return true 

} 

は与える：それを行うには

 
0 (false) 
1 (true) 
0 false 
1 true 

Answer 5

最も簡単な方法は、VEC1とVEC2のコピーを作成し、それらを並べ替えると==を使用して比較することです。

もう1つの方法は、Vec1とVec2から2つのマルチセットを作成し、==を使用してそれらを比較することです。

これを行うもう1つの方法は、カウンタを格納するためにマップ（std :: mapまたはunordered_map）を使用することです。つまり、Vec1のすべての要素に格納値をインクリメントし、Vec2の格納要素ごとにインクリメントし、ゼロ要素非ゼロ要素がマップに格納されている場合、ベクトルは等しくはありません。

乱雑擬似コード例：あなたのSTL（またはブースト）に応じて、

std::vector<Value> vec1, vec2; 
//initialize vec1 and vec2, fill with data 
typedef int Counter; 
typedef unordered_map<Value, Counter> CounterMap; 

CounterMap counters; 
for (size_t i = 0; i < vec1.size(); i++) 
    counters[vec1[i]]++; 
for (size_t i = 0; i < vec2.size(); i++) 
    counters[vec2[i]]--; 

bool equal = true; 
for (CounterMap::const_iterator i = coutners.begin(); equal && (i != counters.end()); i++) 
    if (i->second != 0) 
     equal = false; 

実装、データ型、およびベクターにおける保存されたデータの順序）これらの方法の一つは速くなりますが、伝えるのは難しいですどれ。

Answer 6

次のアルゴリズムで行われる計算にintが十分に大きいと考えると、単純なO（N）アルゴリズムがあります。

0：初期設定：最大の大きさ（V1、V2）、製品1 = 1、product2 = 1

1に素数があります！V1の大きさの場合はfalseを返すには= V2

のサイズ2：

foreach ( i in v1) { 
    product1 *= primes[v1[i]] 
    product2 *= primes[v2[i]] 
} 

result product1 == product2; 

Answer 7

v7.push_back(3); 
    v7.push_back(1); 
    v7.push_back(7); 

    v8.push_back(7); 
    v8.push_back(3); 
    v8.push_back(1); 
    v8.push_back(1); 
    v8.push_back(7); 

    std::cout << compare(v7, v8) << " true or false" << std::endl; 

上記のような条件は、関数の比較はtrueまたはfalseを返します。私はカウントを失った。 の場合はtrueを返します。 我々は方法を使用することはできません： 標準的な方法は、これらの2つのベクトルをソートし、対応する値を比較する演算子==を使用します。