has_set_intersection

[gast128@…]

We sometimes have the requirement that we are only interested if two ranges have overlap. While in general for ranges this is somewhat difficult, for sorted ranges it seems easy:

template<class In1, class In2, class BinaryPredicate> bool has_set_intersection(In1 itFirst1, In1 itLast1, In2 itFirst2, In2 itLast2, BinaryPredicate comp) {

bool bOverlap = false;

while (itFirst1 != itLast1 && itFirst2 != itLast2) {

if (comp(*itFirst1, *itFirst2)) {

++itFirst1;

} else if (comp(*itFirst2, *itFirst1)) {

++itFirst2;

} else {

bOverlap = true; break;

}

}

return bOverlap;

}

Ofc this can be achieved with the normal set_intersection as well but that loops until the end of one of the ranges and requires an extra output iterator functor.

Maybe an idea?

[Marshall Clow]

Yes, maybe an idea ;-)

Although I might be tempted to call it ranges_intersect or something.

[Marshall Clow]

I thought that I knew what you were asking, but then I realized I did not.

What do you mean by "overlap"? An example would be helpful, I think.

[gast128@…]

Example:

• int a1[] = {1, 2, 3};
• int a2[] = {2, 3, 4};
• int a3[] = {4, 5, 6};

a1 and a2 have overlap; a1 and a3 not. Basically it is just the set_intersection algorithm but without storing the results and break out early if possible.

I get btw a lot of 'trac' errors: 'Submission rejected as potential spam (StopForumSpam says this is spam (ip))'

[gast128@…]

It seems that std::includes is more or less the Boolean version of std::set_difference though it uses reversed arguments.