c++ - 检查元素是否在两个 vector 中的最快方法

Question

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

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)，因为它调用 std::find 与 vec2 的每个元素的元素数量成线性 vec1。您可以通过多种方式改进它:

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