Home > Archive > VC STL > February 2005 > Which STL algorithm?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Which STL algorithm?
|
|
| Stephen Howe 2005-02-24, 4:04 pm |
| 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
| |
| Pete Becker 2005-02-24, 4:04 pm |
| 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)
| |
| Stephen Howe 2005-02-24, 4:04 pm |
| > 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
| |
| Igor Tandetnik 2005-02-24, 4:04 pm |
| "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
| |
| Tom Widmer 2005-02-24, 4:04 pm |
| 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
| |
| Doug Harrison [MVP] 2005-02-24, 4:04 pm |
| 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++
| |
| Igor Tandetnik 2005-02-24, 4:04 pm |
| "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
| |
| Doug Harrison [MVP] 2005-02-24, 4:04 pm |
| 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++
| |
| Pete Becker 2005-02-24, 4:04 pm |
| 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] 2005-02-24, 4:04 pm |
| Pete Becker wrote:
>Doug Harrison [MVP] wrote:
>
>
>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.
In general I agree with that. However, provided there is no prohibition on
the output iterator throwing exceptions, it would be appropriate to do just
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 the
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.
--
Doug Harrison
Microsoft MVP - Visual C++
| |
| Pete Becker 2005-02-24, 4:04 pm |
| 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 just
> 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 the
> 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)
| |
| Doug Harrison [MVP] 2005-02-24, 9:00 pm |
| Pete Becker wrote:
>This is the first step down the slippery slope towards Java-style use of
>exceptions. Don't do it.
I disagree completely with this latest objection. Instead of stating in
negative terms how this should not be dealt with, state in positive terms
how it should be dealt with. If I understand you correctly, you're saying,
"You must rewrite the function yourself regardless of its complexity, even
if you don't have the source code and have no idea a priori how to do it,
even if it's possible to co-opt its documented exception safety to achieve
the effect you need in a totally safe way." That's what you're saying when
you respond to what I wrote last time with, "Don't do it."
FWIW, I think the solution you posted to the OP is the right one for this
case. It just doesn't scale very far beyond the trivial.
--
Doug Harrison
Microsoft MVP - Visual C++
| |
| Pete Becker 2005-02-24, 9:00 pm |
| Doug Harrison [MVP] wrote:
> Pete Becker wrote:
>
>
>
>
> I disagree completely with this latest objection. Instead of stating in
> negative terms how this should not be dealt with, state in positive terms
> how it should be dealt with. If I understand you correctly, you're saying,
> "You must rewrite the function yourself regardless of its complexity, even
> if you don't have the source code and have no idea a priori how to do it,
> even if it's possible to co-opt its documented exception safety to achieve
> the effect you need in a totally safe way." That's what you're saying when
> you respond to what I wrote last time with, "Don't do it."
>
Don't take things so seriously.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Doug Harrison [MVP] 2005-02-24, 9:00 pm |
| Pete Becker wrote:
>Don't take things so seriously.
<McEnroe>
You can't be serious!
</McEnroe>
--
Doug Harrison
Microsoft MVP - Visual C++
| |
| Stephen Howe 2005-02-24, 9:00 pm |
| > FWIW, I think the solution you posted to the OP is the right one for this
> case. It just doesn't scale very far beyond the trivial.
In what way? Seems to scale very well. Complexity can't be more than
O(max(N,M)) comparisions if M, N are the number of elements in each
container. I call that very efficient. And the containers can be different.
Stephen Howe
| |
| Doug Harrison [MVP] 2005-02-24, 9:00 pm |
| Stephen Howe wrote:
>In what way? Seems to scale very well. Complexity can't be more than
>O(max(N,M)) comparisions if M, N are the number of elements in each
>container. I call that very efficient. And the containers can be different.
In this thread, I've been talking about finding a way to use an existing
function vs writing your own from scratch. Writing a half-dozen line trivial
function to get the behavior you need is easy, but it doesn't scale to
intricate algorithms that require a lot of code to implement. For more, read
the thread starting with my reply to Igor.
--
Doug Harrison
Microsoft MVP - Visual C++
|
|
|
|
|