By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,710 Members | 1,208 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,710 IT Pros & Developers. It's quick & easy.

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

P: n/a
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
Share this Question
Share on Google+
2 Replies


P: n/a
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

P: n/a
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.