0

假设您有 2 个向量v1，并且v2具有以下值：

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

检查它们是否“相等”的最 STL 方法是什么？我将“相等”定义为无论顺序如何，内容都是相同的。我宁愿这样做而不进行排序。

我倾向于建造两个std::map<double, int>来计算每个向量的元素。

所有，我需要的是算法中的布尔值是/否。

你说什么？

Stack Overflow 上的其他对话诉诸于对向量进行排序，我宁愿避免这种情况。因此，这个新线程。

4

6 回答 6

4

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

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

我只会对向量进行排序（或制作副本并对它们进行排序，如果您不允许销毁源副本），然后使用内置的向量operator ==。

于 2012-11-27T00:56:09.673 回答
4

对向量进行排序并调用 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;
于 2012-11-27T01:04:34.837 回答
3

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

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

于 2012-11-27T00:57:02.197 回答
1

最初是在考虑以集合的方式工作，因为这就是您实际考虑的方式，但这确实需要排序。这可以O(n)通过将两者都转换为哈希图并在那里检查是否相等来完成。

于 2012-11-27T00:52:15.220 回答
-1

只需取第一个向量并将其与第二个向量中的每个元素进行比较。

如果在第二个中找不到第一个值中的一个值，则向量是不同的。在最坏的情况下，它需要 O(n*m) 时间，其中 n = 第一个向量的大小，m = 第二个向量的大小。

于 2012-11-27T00:54:07.267 回答
-1

这个 util 方法将帮助您比较 2 个 int[]，如果有任何问题，请告诉我

公共静态布尔比较数组（int [] v1，int [] v2）{

    boolean returnValue = false;

    if(v1.length != v2.length)
        returnValue = false;

    if(v1.length == 0 || v2.length == 0)
        returnValue = false;

    List<Integer> intList =  Ints.asList(v2);

    for(int element : v1){
        if(!intList.contains(element)){
            returnValue = false;
            break;
        }else{
            returnValue = true;
        }
    }
于 2012-11-27T02:03:14.333 回答