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]

On 2007-12-10 08:19:27 -0500, ke****@gmail.com said:

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.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Vladislav.Lazarenko]

On Dec 10, 8:19 am, [e-mail] wrote:

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.