没有自然排序顺序的两个std ::向量之间的区别

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

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

来源

2013-03-22 Dunnie

有多大的载体？ – 2013-03-22 10:56:17

最糟糕的情况下，每个可能有多达7000个元素。 – Dunnie 2013-03-22 10:57:28

只要您可以施加人为的，内部一致的排序，就不需要*自然排序。它没有必要，只需满足严格的弱排序标准即可。 – 2013-03-22 10:58:21

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

我能想到的最好是建立与所述第一向量一个HashMap，然后从。减去的散列映射所述第二向量的所有元素。这意味着你需要为你的元素提供一个体面的散列函数。

中平凡，如果你存储的指针，你的等式谓词是基于它，你也可以的基础上指针的积分值的散列。

参见What is a good hash function?。

作为评价所提到的，可替换的可能性是建立在元件上的某些属性的排序，并用它来降低平等的可能性。您可能必须先排序两个载体。

来源

2013-03-22 11:43:36 didierc

我的答案是非常不相关的语言。我不知道哪个解决方案会有更好的表现。 – didierc 2013-03-22 11:49:49

你可以把向量的性质的优势，他们有连续的内存分配，这意味着，向量已经一个大的内存空间预留（然后使用更大的，正常），没有花哨的优化，你可以比较直接内存空间。

在C++ 0x中，你有数据（）方法，即给你的存储空间的开始的直接访问。您可以使用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; 
}

来源

2013-03-22 15:28:42

毫无意义：'std :: equal_range'对于'std :: vector'也是一样，但也适用于'std :: list'。更重要的是，你错过了这一点。这2个向量可以按不同的顺序具有它们的元素。 – MSalters 2013-03-22 23:24:20

没有自然排序顺序的两个std ::向量之间的区别

回答

相关问题