6

我需要一个算法或标准库函数来比较两个向量元素，如下所示：

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

标准方法是对这两个向量进行排序并使用 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 );

如果你不能这样做，那么在即将发布的 boost 1.50 版本中，将会有

boost::algorithm::is_permutation

具有相同的界面。

于 2012-05-08T21:36:21.827 回答
3

从每个向量创建一个multiset，然后比较它们是否相等。

于 2012-05-08T21:16:02.350 回答
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

最简单的方法是创建 Vec1 和 Vec2 的副本，对它们进行排序并使用==.

另一种方法是从 Vec1 和 Vec2 构建两个多重集，并使用==.

另一种方法是使用映射（std::map 或 unordered_map）来存储计数器 - 即增加 Vec1 的每个元素的存储值并减少 Vec2 的每个存储元素，然后检查 map 是否包含非零元素。如果 map 中存储了非零元素，则向量不相等。

凌乱的伪代码示例：

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（或 boost）实现、数据类型和向量中存储数据的顺序）其中一种方法会更快，但很难分辨是哪一种。

于 2012-05-08T21:27:04.450 回答
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;

在上述条件下，函数比较将返回真或假。我失去了计数。如果返回真。我们不能使用这种方式：标准方式是对这两个向量进行排序并使用运算符 == 来比较相应的值。

于 2012-05-09T23:22:39.753 回答