6

I want the function to return true when there is any element matching between two vectors,

Note : My vectors are not sorted Following is my source code,

bool CheckCommon( std::vector< long > &inVectorA, std::vector< long > &inVectorB ) { std::vector< long > *lower, *higher; size_t sizeL = 0, sizeH = 0; if( inVectorA.size() > inVectorB.size() ) { lower = &inVectorA; sizeL = inVectorA.size(); higher = &inVectorB; sizeH = inVectorB.size(); } else { lower = &inVectorB; sizeL = inVectorB.size(); higher = &inVectorA; sizeH = inVectorA.size(); } size_t indexL = 0, indexH = 0; for( ; indexH < sizeH; indexH++ ) { bool exists = std::binary_search( lower->begin(), lower->end(), higher->at(indexH) ); if( exists == true ) return true; else continue; } return false; }

This is working fine when the size of vector B is less than the size of vector A , but returning false even there is match when size of vector B is greater than size of vector A .

Improve this question
6
  • Can we assume that the vectors are sorted? If so, the std::set_intersection is probably what you should try. Commented Nov 25, 2014 at 16:21
  • @PaulMcKenzie I thing yes, I see a std::binary_search Commented Nov 25, 2014 at 16:22
  • 1
    It's strange to see different suggestions as answers without answering the OP's question. Do you see anything wrong with OP's code? I don't see it yet. Commented Nov 25, 2014 at 16:25
  • @RSahu That's the answer...Choose already defined algorithm... else why use vector also. Commented Nov 25, 2014 at 16:28
  • Please post your sample data. Your code works fine for the sample data I test it with. See it at ideone.com/MguVjk. Commented Nov 25, 2014 at 16:35

6 Answers 6

Reset to default
10

The problem with posted code is that you should not use std::binary_search when the vector is not sorted. The behaviour is defined only for sorted range.

If the input vectors are not sorted then you can use find_first_of to check for existence of first common element found.

bool CheckCommon(std::vector<long> const& inVectorA, std::vector<long> const& nVectorB) { return std::find_first_of (inVectorA.begin(), inVectorA.end(), nVectorB.begin(), nVectorB.end()) != inVectorA.end(); }

Complexity of find_first_of is up to linear in inVectorA.size()*inVectorB.size(); it compares elements until a match is found.

If you want to fix your original algorithm then you can make a copy of one of vectors and std::sort it, then std::binary_search works with it.

In actual programs that do lot of such matching between containers the containers are usually kept sorted. On such case std::set_intersection can be used. Then the complexity of search is up to linear in inVectorA.size()+inVectorB.size().

std::find_first_of is more efficient than to sort both ranges and then to search for matches with std::set_intersection when both ranges are rather short or second range is shorter than binary logarithm of length of first range.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

It works, could you please tell the complexity for this.
4

You can use a well-defined algorithm called as std::set_intersection to check if there is any common element between these vectors.

Pre-condition :- Both vectors be sorted.

Improve this answer

Comments

0

You could do something like the following. Iterate over the first vector. For each element, use std::find to see if it exists in the other vector. If you find it, they have at least one common element so return true. Otherwise, move to the next element of the first vector and repeat this process. If you make it all the way through the first vector without finding a common element, there is no intersection so return false.

bool CheckCommon(std::vector<long> const& inVectorA, std::vector<long> const& nVectorB) { for (auto const& num : inVectorA) { auto it = std::find(begin(nVectorB), end(nVectorB), num); if (it != end(nVectorB)) { return true; } } return false; }
Improve this answer

1 Comment

@ravi It would be at worst O(N^2), but if it finds a common element, has short-circuiting behavior so will be faster.
0

Usage of std::set_intersection is one option. Since the vector's elements are sorted, the code can be simplified to this:

#include <algorithm> #include <iterator> bool CheckCommon( const std::vector< long > &inVectorA, const std::vector< long > &inVectorB ) { std::vector< long > temp; std::set_intersection(inVectorA.begin(), inVectorA.end(), inVectorB.begin(), inVectorB.end(), std::back_inserter(temp)); return !temp.empty() }

The drawback is that a temporary vector is being created while the set_intersection is being executed (but maybe in the future, this can be considered a "feature" if you want to know what elements are common).

Improve this answer

Comments

0

Here is an implementation which uses sorted vectors, doesn't construct a new container, and which has only linear complexity (more detailed: O(container1.size()+ container2.size()):

template< class ForwardIt1, class ForwardIt2 > bool has_common_elements( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last ) { auto it=first; auto s_it=s_first; while(it<last && s_it<s_last) { if(*it==*s_it) { return true; } *it<*s_it ? ++it : ++s_it; //increase the smaller of both } return false; }

DEMO

Improve this answer

5 Comments

My vectors are unsorted
When first is equal to last or s_first is equal to s_last (IOW one of sequences is empty) then it crashes.
@Noname: no problem, sort them. As mentioned by ÖöTiib, you'll get O(size1+size2) + O(size1*log(size1)) + O(size2*log(size2)) (the comparison + two times sorting) instead of O(size1*size2). This can be a huge difference.
@davidhigh The current complexity is just O(smallVecSize * log(vigVecSize) is that greater than O( smallVecSize + bigVecSize) ?
For moderate sizes (say, roughly up to 10000) you can safely forget about log-factors. There the constant prefactors hidden in the O are usually much more important. I would suggest you to forget about the asymptotic scaling and just make some tests.
0

Your code uses std::binary_search, whose pre-condition is that (From http://en.cppreference.com/w/cpp/algorithm/binary_search):

For std::binary_search to succeed, the range [first, last) must be at least partially ordered, i.e. it must satisfy all of the following requirements:

  • partitioned with respect to element < value or comp(element, value)
    • partitioned with respect to !(value < element) or !comp(value, element)
    • for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true

A fully-sorted range meets these criteria, as does a range resulting from a call to std::partition.

The sample data you used for testing (as posted at http://ideone.com/XCYdM8) do not meet that requirement. Instead of using:

 vectorB.push_back(11116); vectorB.push_back(11118); vectorB.push_back(11112); vectorB.push_back(11120); vectorB.push_back(11190); vectorB.push_back(11640); vectorB.push_back(11740);

if you use a sorted vector like below

 vectorB.push_back(11112); vectorB.push_back(11116); vectorB.push_back(11118); vectorB.push_back(11120); vectorB.push_back(11190); vectorB.push_back(11640); vectorB.push_back(11740);

your function will work just fine.

PS The you have designed your code, if the longer std::vector is sorted, the function will work fine.

PS2 Another option is to sort the longer std::vector before calling the function. 

std::sort(B.begin(), B.end());
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.