检查元素是否在两个向量中的最快方法

Question

所以，假设我们有两个向量，vec1 和 vec2。仅对两个向量中的元素执行某些操作的最快方法是什么。到目前为止，我已经做到了。简单地说，我们如何才能更快地实现这一目标，或者有什么办法：

vector<Test*> vec1;
vector<Test*> vec2;

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them.


for (Test* test : vec1){

    //Check if test is in vec2
    if (std::find(vec2.begin(), vec2.end(), test) != vec2.end){

        //Do some stuff

    }

}

Answer 1

您的方法是 O(M*N)，因为对于 vec1 的每个元素，它调用 std::find 与 vec2 的元素数量成线性关系。您可以通过多种方式对其进行改进：

排序 vec2 可以让您将时间减少到 O((N+M)*Log M) - 即您可以在范围 vec2.begin(), vec2.end()
对两个向量进行排序可以让您在 O(NLog N + MLog M) 中搜索 - 您可以使用类似的算法合并排序范围以在线性时间内找到匹配对
为 vec2 元素使用散列集可以让您将时间减少到 O(N+M) - 现在集的构造时间和在其中搜索是线性的。

Answer 2

一个简单的方法是 std::unordered_set

vector<Test*> vec1;
vector<Test*> vec2;

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them.
std::unordered_set<Test*> set2(vec2.begin(),vec2.end());

for (Test* t : vec1) {
   //O(1) lookup in hash set
   if (set2.find(t)!=set2.end()) {
     //stuff
    }
 }

O(n+m)，其中n为vec1的元素个数，m为vec2的元素个数 }

检查元素是否在两个向量中的最快方法

Fastest way to check if element is in both vectors

c++

algorithm

vector