c++ - 没有自然排序顺序的两个 std::vector 之间的区别

Question

我正在寻找一种有效的方法来获得两者之间的差异std::vectors。它们包含的对象没有任何自然顺序；我能做的最好的就是测试平等。这似乎排除了这个std::set_difference选项。

有比比较两个嵌套迭代器中的对象更好的解决方案吗？

Answer 1

目标是通过将可能的正匹配组合在一起来减少相等测试的数量。

我能想到的最好的方法是用第一个向量构建一个哈希图，然后从哈希图中减去第二个向量的所有元素。这意味着您需要为您的元素提供一个像样的散列函数。

简单地说，如果您正在存储指针，并且您的相等谓词基于它，您还可以将哈希基于该指针整数值。

请参阅什么是好的散列函数？.

如评论中所述，另一种可能性是对元素的某些属性建立排序，并使用它来减少相等的可能性。您可能必须先对两个向量进行排序。

Answer 2

您可以利用向量的一个属性，它们具有连续的内存分配，这意味着向量保留了一个很大的内存空间（通常比使用时更大），并且没有花哨的优化，您可以直接比较内存空间。

在 C++0x 中，您有 data() 方法，可以让您直接访问该内存空间的开头。您可以使用memcmp来比较向量内的所有数据。

std::vector<char> vector_1;
std::vector<char> vector_2;

// data in to vector_1
// data in to vector_2

if(!memcmp(vector1.data(),vector_2.data(),SIZE_OF_BUFFER_TO_COMPARE))
{
    std::cout <<< "equal vectors" << std::endl;
}