Re: [Boost-users] std::set_intersection without results

Subject: Re: [Boost-users] std::set_intersection without results
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2012-09-14 11:33:11

On Sep 14, 2012, at 2:36 AM, Jens Müller <blog_at_[hidden]> wrote:

> Hi everyone,
> 
> I'm trying to test whether two std::vector's intersect.

When you say, "intersect", I interpret that to mean "Have any elements in common"

> A straightforward way is to sort them, apply std::set_intersection and test whether the result set is non-empty.
> 
> However, I don't need the result. Is there some algorithm in boost that just _tests_ for intersection, i.e., stops when it has found one common element?

I don't know of one, but it should be simple to write:

Here's a brute force implementation (uncompiled code):

        bool any_elements_in_common ( first1, last1, first2, last2 ) {
                for ( auto f = first1; f != last1; ++f )
                        if ( find ( first2, last2, *f ) != last2 ))
                                return true;
                return false; // no elements in common
                }

You can cut down the search time if you can sort the first vector (or whatever it is), and then use std::binary_search

        bool any_elements_in_common ( first1, last1, first2, last2 ) {
                std::sort ( first2, last2 );
                for ( auto f = first1; f != last1; ++f )
                        if ( std::binary_search ( first2, last2, *f ) != last2 ))
                                return true;
                return false; // no elements in common
                }

Alternately, if you can afford the space to make a copy of the first set, then you could use std::set:

        bool any_elements_in_common ( first1, last1, first2, last2 ) {
                std::set<int> s (first2, last2);
                for ( auto f = first1; f != last1; ++f )
                        if ( s.find ( f ) != s.end ())
                                return true;
                return false; // no elements in common
                }

Note that neither of these actually requires that the data be stored in a vector.

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow.lists_at_[hidden]>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki