Boost C++ Libraries: Ticket #11180: has_set_intersection
https://svn.boost.org/trac10/ticket/11180
<p>
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:
</p>
<p>
template<class In1, class In2, class <a class="missing wiki">BinaryPredicate</a>>
bool has_set_intersection(In1 itFirst1, In1 itLast1, In2 itFirst2, In2 itLast2, <a class="missing wiki">BinaryPredicate</a> comp)
{
</p>
<blockquote>
<p>
bool bOverlap = false;
</p>
</blockquote>
<blockquote>
<p>
while (itFirst1 != itLast1 && itFirst2 != itLast2)
{
</p>
<blockquote>
<p>
if (comp(*itFirst1, *itFirst2))
{
</p>
<blockquote>
<p>
++itFirst1;
</p>
</blockquote>
<p>
}
else if (comp(*itFirst2, *itFirst1))
{
</p>
<blockquote>
<p>
++itFirst2;
</p>
</blockquote>
<p>
}
else
{
</p>
<blockquote>
<p>
bOverlap = true;
break;
</p>
</blockquote>
<p>
}
</p>
</blockquote>
<p>
}
</p>
</blockquote>
<blockquote>
<p>
return bOverlap;
</p>
</blockquote>
<p>
}
</p>
<p>
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.
</p>
<p>
Maybe an idea?
</p>
en-usBoost C++ Libraries/htdocs/site/boost.png
https://svn.boost.org/trac10/ticket/11180
Trac 1.4.3Marshall ClowFri, 10 Apr 2015 14:44:45 GMT
<link>https://svn.boost.org/trac10/ticket/11180#comment:1 </link>
<guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11180#comment:1</guid>
<description>
<p>
Yes, maybe an idea ;-)
</p>
<p>
Although I might be tempted to call it <code>ranges_intersect</code> or something.
</p>
</description>
<category>Ticket</category>
</item>
<item>
<dc:creator>Marshall Clow</dc:creator>
<pubDate>Sat, 11 Apr 2015 06:43:37 GMT</pubDate>
<title/>
<link>https://svn.boost.org/trac10/ticket/11180#comment:2 </link>
<guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11180#comment:2</guid>
<description>
<p>
I thought that I knew what you were asking, but then I realized I did not.
</p>
<p>
What do you mean by "overlap"?
An example would be helpful, I think.
</p>
</description>
<category>Ticket</category>
</item>
<item>
<author>gast128@…</author>
<pubDate>Mon, 13 Apr 2015 07:34:00 GMT</pubDate>
<title/>
<link>https://svn.boost.org/trac10/ticket/11180#comment:3 </link>
<guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11180#comment:3</guid>
<description>
<p>
Example:
</p>
<ul><li>int a1[] = {1, 2, 3};
</li><li>int a2[] = {2, 3, 4};
</li><li>int a3[] = {4, 5, 6};
</li></ul><p>
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.
</p>
<p>
I get btw a lot of 'trac' errors: 'Submission rejected as potential spam (<a class="missing wiki">StopForumSpam</a> says this is spam (ip))'
</p>
</description>
<category>Ticket</category>
</item>
<item>
<author>gast128@…</author>
<pubDate>Fri, 12 May 2017 08:05:01 GMT</pubDate>
<title/>
<link>https://svn.boost.org/trac10/ticket/11180#comment:4 </link>
<guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11180#comment:4</guid>
<description>
<p>
It seems that std::includes is more or less the Boolean version of std::set_difference though it uses reversed arguments.
</p>
</description>
<category>Ticket</category>
</item>
</channel>
</rss>