检查两个vector<T>之间的差异

Question

假设你有2个向量，比如v1和v2，它们的值如下：

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

检查它们是否“相等”的最常用的STL方法是什么？我对“相等”的定义是指无论顺序如何，内容都是相同的。我更喜欢在没有排序的情况下这样做。

我倾向于构建两个std::map<double, int>来对向量的每个元素进行计数。

我所需要的就是算法中的一个布尔值Yes/No。

你怎么说？

Stack Overflow上的其他对话求助于对向量进行排序，我倾向于避免这种情况。因此出现了这个新线程。

Answer 1

我倾向于构建两个std::map来计算向量的每个元素。

这将比仅仅创建排序向量慢得多。(还要注意，std::map是由排序驱动的；它只是使用红黑树或AVL树)Map是针对插入和查找的均匀组合而优化的数据结构；但您的用例是一大堆插入，然后是一大堆没有重叠的查找。

我只会对向量进行排序(或者复制并排序，如果不允许销毁源副本的话)，然后使用operator ==中内置的向量。

Answer 2

对向量进行排序并调用set_difference仍然是最好的方法。如果副本对你来说很重，那么两个未排序的数组之间的比较会更糟吗？

如果你希望当前数组保持不变，你可以复制当前数组吗？

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

// can trade before copy/sort heavy work
if (v1.size() != v2.size()){
}     
std::vector<int> v3(v1);
std::vector<int> v4(v2);

sort(v3.begin(), v3.end());
sort(v4.begin(), v4.end());

return v3 == v4;

Answer 3

我假设由于某种原因，你不能对向量进行排序，很可能是因为你仍然需要它们的原始顺序，或者它们的复制成本很高。否则，只需对它们进行排序。

在每个矢量中创建一个“视图”，允许您以任何顺序查看矢量。您可以使用一个指针向量来实现这一点，该向量从按顺序指向元素开始。然后对两个视图进行排序，在每个向量中生成一个排序的视图。然后比较两个视图，比较两个向量的视图顺序。这避免了对向量本身进行排序。