如何比较两个向量是否相等？

Question

我有以下程序：

std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> nums2 = {5, 4, 3, 2, 1};

bool equal = std::equal(nums.begin(), nums.end(), nums2.begin());
if (equal)
{
    cout << "Both vectors are equal" << endl;
}

有两个向量具有相同的元素。 std::equal 函数在这里不起作用，因为它按顺序进行并比较相应的元素。有没有一种方法可以检查这两个向量是否相等，并且在我的情况下不排序就为真？在实际示例中，我没有整数，而是自定义对象，它们比较指针相等。

Answer 1

您正在寻找 set or a multiset。 C++ 标准库确实有这些数据结构的实现：

Answer 2

您可以从每个向量构造一个 std::unordered_set，然后比较它们，如下面的代码片段所示：

#include <iostream>  
#include <vector>  
#include <unordered_set> 

using namespace std;

int main()
{
    std::vector<int> nums = { 1, 2, 3, 4, 5 };
    std::vector<int> nums2 = { 5, 4, 3, 2, 1 };
    std::vector<int> nums3 = { 5, 4, 9, 2, 1 };

    std::unordered_set<int> s1(nums.begin(), nums.end());
    std::unordered_set<int> s2(nums2.begin(), nums2.end());
    std::unordered_set<int> s3(nums3.begin(), nums3.end());

    if (s1 == s2) {
        std::cout << "1 and 2 are equal";
    }
    else {
        std::cout << "1 and 2 are different";
    }
    std::cout << std::endl;

    if (s1 == s3) {
        std::cout << "1 and 3 are equal";
    }
    else {
        std::cout << "1 and 3 are different";
    }
    std::cout << std::endl;

    return 0;
}

不过，有几点需要注意：

对于自定义类型对象的向量，您需要为该类型提供 operator==（但无论如何都必须这样做，或者如果两个向量内容相同）。
包含重复项的向量将创建删除了这些重复项的集合：因此，{1, 2, 2, 3} 将显示等于 {1, 2, 3}。
您还需要为您的自定义类型提供 std:hash。对于一个简单的 class、bob，它只包含一个整数、散列和所需的 operator==，可以定义如下所示；然后，您可以将上面示例中的 <int> 专业化替换为 <bob>，它将起作用。（此 cppreference article 解释了有关哈希的更多信息。）

class bob {
public:
    int data;
    bob(int arg) : data{ arg } { }
};
bool operator==(const bob& lhs, const bob& rhs)
{
    return lhs.data == rhs.data;
}
template<> struct std::hash<bob> {
    std::size_t operator()(bob const& b) const noexcept {
        return static_cast<size_t>(b.data);
    }
};

Answer 3

如果我必须发明一种算法来从头开始执行此操作，因为无论出于何种原因使用集合或排序都不起作用，我会考虑删除匹配项。这将是低效的 - 它是 O(n^2) - 但它会工作，并且在许多情况下效率低下不太可能成为问题：

bool compare(A, B)
  copy B to BB
  for each a in A
    if BB contains a
      remove a from BB
    else
      return false

  if BB is empty
    return true

  return false

Answer 4

std::is_permutation 标准库算法完全符合您的要求。它 returns true 如果两个范围以任何顺序包含相同的元素。

它可能对某些应用程序来说很慢，但它只需要相等比较，不需要临时容器或额外的内存分配。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> nums = { 1, 2, 3, 4, 5 };
    std::vector<int> nums2 = { 5, 4, 3, 2, 1 };

    bool equal = std::is_permutation(nums.begin(), nums.end(), nums2.begin(), nums2.end());

    if (equal) {
        std::cout << "Both vectors are equal" << std::endl;
    }
}

Answer 5

使用 std::sort 另一种方法来解决您的任务。如果向量具有重复元素，它也能正常工作（如下例所示）。它也相当快，平均 O(N*Log(N)) 时间，在现实生活中将在时间上接近 std::unordered_set 或 std::unordered_multiset 的解决方案。

是的，我看到OP要求实现不排序，但实际上std::is_permutation几乎可以肯定也在下面进行排序。 std::set 也使用树进行间接排序。甚至 std::unordered_set 也做了一种按哈希值排序（哈希分桶是一种基数排序）。所以如果没有一种间接排序或其他类型的排序整个向量，这个任务可能无法解决。

Try it online!

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums1 = {1, 2, 3, 4, 1, 5}, nums2 = {5, 4, 3, 1, 2, 1};
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());
    std::cout << std::boolalpha << (nums1 == nums2) << std::endl;
}

输出：

true

如何比较两个向量是否相等？

How to compare two vectors for equality?

c++

algorithm

stl