Check if two elements have a common element in C ++
I want the function to return true when there is any element matching two vectors,
Note : My vectors are not sorted
Below 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 works fine when vector B is smaller than vector A, but returns false even if there is a match when vector B is larger than vector A.
source to share
The problem with the posted code is that you shouldn't use std::binary_search
when the vector is not sorted. The behavior is only defined for the sorted range.
If the input vectors are not sorted, you can use find_first_of
to check for the existence of the first 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();
}
Difficulty find_first_of
up to linear in inVectorA.size()*inVectorB.size()
; it compares the elements until a match is found.
If you want to fix your original algorithm, you can make a copy of one of the vectors and std::sort
then it std::binary_search
will work with it.
In real programs that make a lot of this correspondence between containers, containers are usually sorted. Then the search complexity is up to a linear value in inVectorA.size()+inVectorB.size()
.
std::find_first_of
more efficient than sorting both ranges and then looking for a match when both ranges are fairly short or the second range is shorter than the binary logarithm of the length of the first range.
source to share
You can use a well-defined algorithm called std::set_intersection
to check if there is any common element between these vectors.
Precondition: - Both vectors will be sorted.
source to share
Here's an implementation that uses sorted vectors, doesn't create a new container, and only has linear complexity (in more detail 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;
}
source to share
You can do something like the following. Iterations over the first vector. For each element, use std::find
to see if it exists in another vector. If you find it, they have at least one element in common, so return true. Otherwise, move on to the next element of the first vector and repeat this process. If you go 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;
}
source to share
Usage std::set_intersection
is one option. Since vector 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 downside is that set_intersection
a temporary vector is created at runtime (but perhaps in the future this can be thought of as a "function" if you want to know which elements are in common). In the meantime, there is no need to know about it. ”
source to share
Your code uses std::binary_search
which precondition (From http://en.cppreference.com/w/cpp/algorithm/binary_search ):
To be successful, the
std::binary_search
range[first, last)
must be at least partially ordered, that is, it must satisfy all of the following requirements:
- divided into
element < value
orcomp(element, value)
- divided into
!(value < element)
or!comp(value, element)
- for all elements, if
element < value
orcomp(element, value)
-true
, then!(value < element)
or!comp(value, element)
alsotrue
The fully sorted range meets these criteria, as well as the range resulting from the call
std::partition
.
The sample data you used for testing (as stated at http://ideone.com/XCYdM8 ) does not meet this 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 are using 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 fine.
PS . You worked out your code, if the sorted is longer std::vector
, the function will work fine.
PS2 Another option is to sort for longer std::vector
before calling the function.
std::sort(B.begin(), B.end());
source to share