CODEWITHSUNDEEP
c++vector
jr27
jr27

Reputation: 11

Want to see if any value in one vector matches the value in another vector

I am writing code for a game called Bulls & Cows. I have already solved seeing if the value of one vector (if they are in the same index) are identical. However, I am not sure how to write a for loop that will move through two vectors and see if any value in one matches the value of any other index in the other vector. I would appreciate any help. Thank you!

Upvotes: 0

Views: 1001

Answers (3)

SCFrench
SCFrench

Reputation: 8374

This is the definition of std::find_first_of.

Upvotes: 1

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145457

The brute force approach is

for( auto& x1 : vec1 )
    for( auto& x2 : vec2 )
        if( x1 == x2 )
            return true;
return false;

If both vectors are of length n, this performs n2 comparisons in the not found case, and on average.

That's quadratic time, O(n2 ), which is pretty ungood.

For better performance you can just put all values of one vector in a set. Then you can check each value of the other vector, against the set. For a std::set the checking of each value is log(n), and so checking n values gives you O(n log n) time. For a std::unordered_set the checking is essentially constant time, which reduces the whole thing to O(n).

There is however a problem with std::unordered_set, that at least with the version of g++ that I use (MinGW 5.1), its standard library implementation lacks support for hashing enum values, so that you'd have to supply a hash function or general hashing support to make the code portable.

So,

using Item = decltype(v1)::value_type;
std::set<Item> v1_values{ v1.begin(), v1.end() };
for( auto& x2 : v2 )
    if( v1_values.count( x2 ) > 0 )
        return true;
return false;

Disclaimer: code not even glanced at by compiler, and I'm unsure about whether the count is the most elegant way to check since I generally just wrap the standard library things.

The best thing performance-wise would be to use an incremental approach, e.g. to update such a set each time you add a value to v1 or v2. This adds to the complexity of the code, and is not independent of what you use these vectors for. I.e. it's a more intrusive solution: you generally pay for the performance by added complexity.

Upvotes: 3

Mattia F.
Mattia F.

Reputation: 1740

Just do a simple loop:

vector<int> v1, v2;
//Initialize v1 and v2...

for (auto& i: v1) //Loop through each element of v1
    for (auto& j: v2) //Same for v2
        if (i == j) 
             std::cout << "Ok! They match!" << std::endl;

Upvotes: 0

Related Questions