Which STL algorithm?

Hi

Consider lower_bound() and binary_search(). Despite what people say about
binary_search(), it is useful. If all you care about is the existence of an
element in a sequence, not its location,  binary_search() is great.

Now I wish to check if two vectors have any element in common. I am not
interested in locating the element.

I can do find_first_of() and see if I get end. This is fine if one or more
vectors is unsorted
It is complexity of O(M * N).
But what if they are sorted? Should be able to do better than
find_first_of().

I an also do set_intersection() which is much better in terms of complexity.
If set_intersection() generates empty output, you know there is no element
in common. But here, the snag is that set_intersection() _insists_ in
generating output, which I am not interested in.
Further a binary_set_intersection(), if it existed, would give up the moment
an element in common is found. So its complexity would even better.

Have I overlooked an algorithm?

Cheers

Stephen Howe

Stephen Howe wrote:
>
> Have I overlooked an algorithm?
>

No, but it's fairly easy to write the one you need (not tested):

template <class FwdIt1, class FwdIt2>
bool has_common_element(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2)
{
while (first1 != last1 && first2 != last2)
{
if (*first1 < *first2)
++first1;
else if (*first2 < *first1)
++first2;
else
return true;
return false;
}

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

> No, but it's fairly easy to write the one you need (not tested):
>
> template <class FwdIt1, class FwdIt2>
> bool has_common_element(FwdIt1 first1, FwdIt1 last1,
> FwdIt2 first2, FwdIt2 last2)
> {
> while (first1 != last1 && first2 != last2)
> {
> if (*first1 < *first2)
> ++first1;
> else if (*first2 < *first1)
> ++first2;
> else
> return true;

}

> return false;
> }

Thanks. That should be added to the standard library (as should is_sorted(),
is_heap(), copy_if())

Stephen Howe

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eEmuQ5oGFHA.2276@TK2MSFTNGP15.phx.gbl
> Now I wish to check if two vectors have any element in common. I am
> not interested in locating the element.
>
> I an also do set_intersection() which is much better in terms of
> complexity. If set_intersection() generates empty output, you know
> there is no element in common. But here, the snag is that
> set_intersection() _insists_ in generating output, which I am not
> interested in.

You could write an output iterator that simply sets a boolean flag
whenever it's assigned to, and ignore the data otherwise. Still,
set_intersection would process all elements in both sequences, instead
of stopping the moment a match is found.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Igor Tandetnik wrote:
> "Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
> news:eEmuQ5oGFHA.2276@TK2MSFTNGP15.phx.gbl
> 
>
>
> You could write an output iterator that simply sets a boolean flag
> whenever it's assigned to, and ignore the data otherwise. Still,
> set_intersection would process all elements in both sequences, instead
> of stopping the moment a match is found.

Surely an opportunity for an unconventional use of exceptions! Not
recommended of course - writing the new algorithm is the best option.

Tom

Igor Tandetnik wrote:

>You could write an output iterator that simply sets a boolean flag
>whenever it's assigned to, and ignore the data otherwise. Still,
>set_intersection would process all elements in both sequences, instead
>of stopping the moment a match is found.

Is there any prohibition on an output iterator throwing an exception? I
don't think so, and if not, you could write a set_any_in_common function
that catches this exception and terminates as soon as possible. This might
be appropriate for algorithms more complicated than the one Pete posted in
his message.

--
Doug Harrison
Microsoft MVP - Visual C++

"Doug Harrison [MVP]" <dsh@mvps.org> wrote in message
 news:ua4s11trpa08qlv034e5opjqbeoob7oaju@
4ax.com
> Igor Tandetnik wrote:
> 
>
> Is there any prohibition on an output iterator throwing an exception?
> I don't think so, and if not, you could write a set_any_in_common
> function that catches this exception and terminates as soon as
> possible. This might be appropriate for algorithms more complicated
> than the one Pete posted in his message.

I thought of that, but I suspect that for sequences of reasonable size
the overhead of throwing and catching an exception may be higher than
just letting the algorithm plow through all the elements.

Another approach might be to wrap the iterators on sequences themselves
so that they cooperate with the output iterator. The moment the output
iterator is assigned to, all iterators over both sequences begin to
compare equal to their respecting end-of-sequence iterators, causing the
algorithm to terminate. I'm not sure this is legal, and in any case it's
going to be complicated and obscure.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Igor Tandetnik wrote:

>I thought of that, but I suspect that for sequences of reasonable size
>the overhead of throwing and catching an exception may be higher than
>just letting the algorithm plow through all the elements.

That's definitely something to consider. It's somewhat like wanting to
implement std::copy in terms of memcpy for PODs, when normal std::copy might
be more efficient than memcpy for a given type and sequence length < some N.

--
Doug Harrison
Microsoft MVP - Visual C++

Doug Harrison [MVP] wrote:

> Is there any prohibition on an output iterator throwing an exception? I
> don't think so, and if not, you could write a set_any_in_common function
> that catches this exception and terminates as soon as possible. This might
> be appropriate for algorithms more complicated than the one Pete posted in
> his message.
>

No, it would not be appropriate. Exceptions aren't for normal returns.
They're for exceptional events. They create hidden execution paths, and
that makes understanding the code hard. Not to mention the performance hit.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

Doug Harrison [MVP] wrote:

> Pete Becker wrote:
>
> 
>
>
> In general I agree with that. However, provided there is no prohibition on
> the output iterator throwing exceptions, it would be appropriate to do jus
t
> that to adapt an algorithm too complex or lengthy to duplicate, or absent
> the source code, recreate entirely on your own. Consider:
>
> bool f()
> {
>    try
>    {
>        lengthy_f_that_provides_no_early_return(
Iter_that_throws());
>    }
>    catch (the_exception_type)
>    {
>       return true;
>    }
>    return false;
> }
>
> As lengthy_f is a black box that doesn't prohibit the iterator from
> throwing, the "hidden execution path" argument doesn't even apply to the
> person writing f. The performance hit argument may not apply, given that t
he
> poor performance of the algorithm that doesn't terminate ASAP is the whole
> reason for looking for an alternative. That's something that can only be
> determined empirically. But if duplicating the algorithm as you did is
> significantly harder than writing the Iter_that_throws class, looking for 
a
> way to work with what you've got surely is the way to go, at least until
> proven otherwise.
>

This is the first step down the slippery slope towards Java-style use of
exceptions. Don't do it.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)