473,385 Members | 2,044 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,385 software developers and data experts.

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 1835
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Dylan | last post by:
Is there an STL algorithm that will return true if each element in coll1 is present in coll2
9
by: Patrick Guio | last post by:
Dear all, I am trying to use the std::transform algorithm to to the following vector< vector<char> >::iterator ik = keys.begin(); // key list iterator vector< vector<char> >::iterator is = ik;...
4
by: Generic Usenet Account | last post by:
I am seeing some unexpected behavior while using the STL "includes" algorithm. I am not sure if this is a bug with the template header files in our STL distribution, or if this is how it should...
8
by: Generic Usenet Account | last post by:
I have a need for a set operation (actually multi-set operation) on sorted structures that is not in the STL library. I call it the set_retain operation. It's kinda similar to the...
15
by: silverburgh.meryl | last post by:
Hi, I am trying to write a transform_until template. It is bascially doing what transform is doing except if UnaryOperation return NULL, it will break out from the loop. Here is the code, but...
13
by: Winbatch | last post by:
Is there a function that I can use that given a few vectors which elements are common to all? for example vector<int> a; vector<int> b; a.push_back( 1 ); a.push_back( 2 ); a.push_back( 3 );
0
by: Leslie Sanford | last post by:
I need an interative form of the std::transform algorithm. In other words, instead of letting transform do its work and accessing the results afterwards, I need to access each transformation as it...
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.