Fastest way to check if element is in both vectors

Question

So, think that we have two vectors, vec1 and vec2. What would be the fastest way to only perform some operation to elements, which are in both vectors. This far, I have made this. Simply, how can we achieve this faster, or is there any way:

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

Your approach is O(M*N) because it calls std::find linear in the number of elements of vec2 for each element of vec1. You can improve upon it in several ways:

• Sorting vec2 would let you reduce the time to O((N+M)*Log M) - i.e. you can use binary search on the range vec2.begin(), vec2.end()
• Sorting both vectors would let you search in O(NLog N + MLog M) - you could use an algorithm similar to merging sorted ranges to find matching pairs in linear time
• Using a hash set for vec2 element would let you reduce the time to O(N+M) - now both the construction time of the set and the search in it are linear.