STL implementation of bool intersects(first1,last1,first2,last2)

[keindl]

I'd like to test if two sorted vectors intersect each other. What is
the most efficient implementation for this? I could calculate the
intersection but that would not be efficient since after finding only
one element in the intersection the algorithm should stop. I am
looking for something like the includes function.

 

[Pete Becker]

I'd like to test if two sorted vectors intersect each other. What is
the most efficient implementation for this? I could calculate the
intersection but that would not be efficient since after finding only
one element in the intersection the algorithm should stop. I am
looking for something like the includes function.

Seems straightforward: start at the beginning of each sequence. If the
two elements are equal, you're done. If not, move forward in the
sequence that holds the lesser of the two elements. If you reach the
end of the sequence, you're done. Otherwise, repeat.

 

[Vladislav.Lazarenko]

I'd like to test if two sorted vectors intersect each other. What is
the most efficient implementation for this? I could calculate the
intersection but that would not be efficient since after finding only
one element in the intersection the algorithm should stop. I am
looking for something like the includes function.

STL has only algorithm that performs intersection operation (see
http://www.sgi.com/tech/stl/set_intersection.html). Basically, what
you are looking for is:

1) Set intersection
2) Check if resulting container is not empty

For performance tuning try to modify that algorithm to break after
first element of intersection found.

Vlady.

 

[keindl]

Thank you. I managed to find the original function in stl_algo.h. Here
is the modified version:

template < typename _InputIterator1, typename
_InputIterator2>
bool
intersects (_InputIterator1 __first1, _InputIterator1
__last1,
_InputIterator2 __first2, _InputIterator2
__last2)
{
// concept
requirements
__glibcxx_function_requires (_InputIteratorConcept < _InputIterator1

)

__glibcxx_function_requires (_InputIteratorConcept <
_InputIterator2

)

__glibcxx_function_requires (_SameTypeConcept < typename
iterator_traits
<
_InputIterator1

::value_type,

typename iterator_traits
<
_InputIterator2 >::value_type

)

__glibcxx_function_requires (_LessThanComparableConcept
<
typename iterator_traits
<
_InputIterator1 >::value_type

)

__glibcxx_requires_sorted (__first1,
__last1);
__glibcxx_requires_sorted (__first2,
__last2);

while (__first1 != __last1 && __first2 !=
__last2)
if (*__first1 <
*__first2)
+
+__first1;
else if (*__first2 <
*__first1)
+
+__first2;
else
{
return
true;
}
return
false;
}