Fastest way to check if element is in both vectors

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

    }

}

Answers


One easy way is to 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), where n is the number of elements in vec1, m is the number of elements in vec2 }


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.

Need Your Help

ios autolyouts: labels centering

ios objective-c autolayout constraints

In my app, I have two UILabels that can contain different length text inside, depends on selected localization. I want to center both labels to the superview's horizontal center.

How do you write the degrees symbol (°) into EXIF on iOS?

objective-c ios6 exif

I'm struggling to write a string into a JPG's Exif: user comments section, that contains the degress symbol (°).

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.