468,509 Members | 1,430 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,509 developers. It's quick & easy.

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

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.
Dec 10 '07 #1
2 1668
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)

Dec 10 '07 #2
On Dec 10, 8:19 am, kei...@gmail.com 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.
Dec 10 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

9 posts views Thread by Patrick Guio | last post: by
4 posts views Thread by Generic Usenet Account | last post: by
8 posts views Thread by Generic Usenet Account | last post: by
15 posts views Thread by silverburgh.meryl | last post: by
13 posts views Thread by Winbatch | last post: by
reply views Thread by Leslie Sanford | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.