6

以下のように、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を使用した）方法はありますか？そうでない場合、このアルゴリズムをどのように記述できますか? それは私をあまりにも混乱させました。

4

7 に答える 7

21

標準的な方法は、これら 2 つのベクトルを並べ替えて==、対応する値を比較する operator を使用することです。

このアルゴリズムを実現するサンプル ソリューションは次のとおりです。

#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*log(n)) です。

于 2012-05-08T21:15:04.740 に答える
19

C ++ 11ソリューションだけで生活できる場合std::is_permutationは、まさにあなたが望むものです

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

それができない場合は、次のブースト 1.50 リリースで、

boost::algorithm::is_permutation

同じインターフェースで。

于 2012-05-08T21:36:21.827 に答える
3

multiset各ベクトルから を作成し、それらが等しいかどうかを比較します。

于 2012-05-08T21:16:02.350 に答える
0

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

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

さらに別の方法は、マップ（std :: mapまたはunordered_map）を使用してカウンターを格納することです。つまり、Vec1のすべての要素の格納値をインクリメントし、Vec2のすべての格納要素をデクリメントしてから、マップにゼロ以外の要素が含まれているかどうかを確認します。マップにゼロ以外の要素が格納されている場合、ベクトルは等しくありません。

厄介な擬似コードの例：

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;

STL（またはブースト）の実装、データ型、およびベクトルに格納されたデータの順序に応じて、これらのメソッドの1つは高速になりますが、どちらを使用するかを判断するのは困難です。

于 2012-05-08T21:27:04.450 に答える
0

ソートされていない入力に対するこの問題に対する 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 (偽)
1 (真)
0 偽
1 真
于 2012-05-08T21:20:33.437 に答える
0

int が次のアルゴリズムで実行される計算に十分な大きさであると考える場合、単純な O(N) アルゴリズムがあります。

0: 初期化: max(v1,v2) のサイズに素数があり、product1=1、product2=1

1: v1 のサイズ != v2 のサイズの場合は false を返す

2:

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

3.

result product1 == product2;
于 2012-05-08T22:08:46.720 に答える
-1 
  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;

上記の条件では、compare 関数は true または false を返します。カウントを失いました。true を返す場合。この方法は使用できません。標準的な方法は、これら 2 つのベクトルを並べ替えて、対応する値を比較する演算子 == を使用することです。

于 2012-05-09T23:22:39.753 に答える