Re: [boost] Boost.Algorithm library

From: Jeff King (peff-boost_at_[hidden])
Date: 2001-12-04 21:51:34

On Tue, 4 Dec 2001, Joe Gottman wrote:

> There is a similar function that takes a predicate as a third template
> parameter.  You could use std::set_intersection() to determine if two ranges
> intersect, but this function has two advantages.  You do not have to
> allocate space for the output set,

This could also be solved by the concept of a "counting" output
iterator. That is, the output iterator would start as "0"; whenever it
was incremented, it would increment the count by one; assignments would
be a noop.

So you could write:

template <class Iter>
bool sets_intersect(Iter first1, Iter last1, Iter first2, Iter last2) {
  counting_iterator c;
  c = std::set_intersection(first1, last1, first2, last2, c);
  return *c == 0;
}

The nice thing is that such a counting_iterator might be useful with
other algorithms.

> and this function returns true as soon as
> the first point of intersection is found.  The one thing I'm not sure about

You definitely get an efficiency gain from yours, although not in terms
of algorithmic complexity. However, I consider the use of the algorithm
three ways:

 - you want to know which elements are in the intersection
 - you want to know how many elements are in the intersection
 - you want to know whether there are any elements in the intersection

std::set_intersection answers the first. Yours answers the third. Should
there be another algorithm to answer the second?

-Jeff