Michel Michaud wrote in message ...
<clip>
>It seems there is no function in <algorithm> that would
>test for equality using a Cmp function, although it could be
>done: if (!cmp(a,b) && !cmp(b,a)). I guess this is the
>answer to my original post (beside that it would require
>a different name than find, but I could accept that).
>
>I can then reformulate my question: how can we use a
>Cmp function to find a value using the library. For example,
>I was trying to do this (or something like it):
>
<clip>
>    IT it= find_cmp(begin, end, v, cmp); // Won't compile
<clip>
>
>The only way I can think of, is doing the search myself:
>
<clip>
>    for (; it!=end; ++it)
>        if (!cmp(v, *it) && !cmp(*it, v))
>            break;
<clip>
>
>Maybe the library should include an binder/adapter to convert
>a Cmp function and a value to a unary function that could be
>used with find_if:
>
<clip>
>    IT it= find_if(begin, end, MatchFinder<cmp, v>());
>    //...
<clip>

I believe that the standard library was engineered this way for a
reason.  The sort-related algorithms in the standard library use
comparators because they need to retrieve ordering information about two
values.  But the other algorithms don't need ordering information, they
need equality information.  It doesn't really make sense to include in
the standard library a find_cmp function because such a function is
asking for more (not to mention potentially different) information than
it really needs.  I realize I'm being rather picky here, but I do have a
point which I'm about to make....

I contest that using a comparator to test for equality is in general a
Bad thing.  It's not particularly effecient, and it doesn't really test
for equality at all, but rather for equivalence.  As such, I think that
the standard should encourage avoiding the use of comparators when an
equality BinaryPredicate is what is really required.  It apparently does
this by not providing any standard components such as those that you
suggest.  If you disagree with this philosophy, by all means try to
convince me otherwise.

There are always exceptions to every rule (especially in C++ :) so you
should feel free to roll your own find_cmp or MatchFinder.  I think that
a much better solution is to add an operator== or a BinaryPredicate that
does equality testing that is not based on operator< (or a comparator).

Just for the heck of it (I can't get to sleep), here is a (Evil?)
adaptor like the one you requested:

template <class Compare>
class CompToUnaryPred_Adapter :
  std::unary_function<bool, typename Compare::first_argument_type>
{
public:
  CompToUnaryPred_Adapter(Compare comp, const argument_type& value)
    : myComp(comp), myValue(value) {}
  result_type operator()(const argument_type& arg)
    {return !myComp(arg, myValue) && !myComp(myValue, arg);}

private:
  Compare myComp;
  argument_type myValue;
};

And a utility function for using it:

template <class Compare>
CompToUnaryPred_Adapter<Compare>
compToUnaryPred(Compare comp,
  const typename Compare::first_argument_type& value)
{
  return CompToUnaryPred_Adapter<Compare>(comp, value);
}

And an example of using it:

vector<int> v;
....
less<int> comp;
vector<int>::iterator it;
it = find_if(v.begin(), v.end(), compToUnaryPred(comp, 0));

Which is the same as, but probably slower than, these two:

it = find_if(v.begin(), v.end(), bind2nd(equal_to<int>(), 0));
if = find(v.begin(), v.end(), 0);

Standard Disclaimer: Use the code above AT YOUR OWN RISK, it is
completely untested.

-Chris Gurnee



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher M. Gurnee wrote <66zZ1.1$Nc5.45045@brnws01.ne.mediaone.net>...
><clip>
>for equality at all, but rather for equivalence.  As such, I think that
>the standard should encourage avoiding the use of comparators when an
>equality BinaryPredicate is what is really required.  It apparently does
>this by not providing any standard components such as those that you
>suggest.  If you disagree with this philosophy, by all means try to
>convince me otherwise.

No no I agree and understand (that's what my post was about I thought).
Although I suppose binary_search needs to test for equality even in
the Cmp version, so you're half right (see below).

>There are always exceptions to every rule (especially in C++ :) so you
>should feel free to roll your own find_cmp or MatchFinder.  I think that

There is a problem: I could also roll my own bind2nd or ptr_fun, etc. But
these are included in the standard library, I would prefer other
"ordinary" adapters (like your try below) to be included, or to have
a function that would not require it. There is no find_cmp nor adapter
in the standard library so it's lacking something. I think the
template I was trying to write shows it's not that farfetched to
need something like that.

>a much better solution is to add an operator== or a BinaryPredicate that
>does equality testing that is not based on operator< (or a comparator).

Can't do that in a template where you only have access to one function.
Of course, I could ask the user to provide more functions. But then maybe
binary_search, lower_bound etc. should ask for == and < because they
probably need them (they will use Cmp i.e. "<" to test for equality).

>Just for the heck of it (I can't get to sleep), here is a (Evil?)
>adaptor like the one you requested:

>template <class Compare>
>class CompToUnaryPred_Adapter :
>  std::unary_function<bool, typename Compare::first_argument_type>
>{
>public:
>  CompToUnaryPred_Adapter(Compare comp, const argument_type& value)
>    : myComp(comp), myValue(value) {}
>  result_type operator()(const argument_type& arg)
>    {return !myComp(arg, myValue) && !myComp(myValue, arg);}
>
>private:
>  Compare myComp;
>  argument_type myValue;
>};
>
>And a utility function for using it:
>
>template <class Compare>
>CompToUnaryPred_Adapter<Compare>
>compToUnaryPred(Compare comp,
>  const typename Compare::first_argument_type& value)
>{
>  return CompToUnaryPred_Adapter<Compare>(comp, value);
>}
>Standard Disclaimer: Use the code above AT YOUR OWN RISK, it is
>completely untested.

I didn't finish mine so I check yours too...

Michel Michaud micm19@removethis.mail2.cstjean.qc.ca
http://www3.sympatico.ca/michel.michaud





[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Why is there no find with binary predicate? I mean:

   bool Compare(..., ...);
   vector<...> v;
   vector<...>::iterator it;

   it= find(v.begin(), v.end(), value, Compare); // NO!

You can use binary_search, sort, max_element,
lower_bound, etc. with a predicate but there is no find
(nor count but that's a little different).

I know I could use:

   it= search_n(v.begin(), v.end(), 1, value, Compare);

but I could also use the non predicate version instead
of find, everywhere. So I guess it's not because of
redundancy...

BTW find_if is not the same (it takes a unary predicate
and no value). Again I know I could use it, but it's
not even as simple and clear as search_n.

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud wrote:

> Why is there no find with binary predicate? I mean:

>    bool Compare(..., ...);
>    vector<...> v;
>    vector<...>::iterator it;

>    it= find(v.begin(), v.end(), value, Compare); // NO!

> You can use binary_search, sort, max_element,
> lower_bound, etc. with a predicate but there is no find
> (nor count but that's a little different).

> I know I could use:

>    it= search_n(v.begin(), v.end(), 1, value, Compare);

> but I could also use the non predicate version instead
> of find, everywhere. So I guess it's not because of
> redundancy...

> BTW find_if is not the same (it takes a unary predicate
> and no value). Again I know I could use it, but it's
> not even as simple and clear as search_n.

So, just add:

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T&
value,
     BinaryPredicate pred)
{
    return search_n(first, last, 1, value, pred);
}

to your program and be happy. :-)

--
Jon Biggar
Floorboard Software
jon@floorboard.com
jon@biggar.org


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jonathan Biggar wrote <363288E2.40AD8AA6@floorboard.com>...

>Michel Michaud wrote:

>> Why is there no find with binary predicate? I mean:
[...]
>So, just add:
>
>template<class InputIterator, class T>
>InputIterator find(InputIterator first, InputIterator last, const T&
>value,
>    BinaryPredicate pred)
>{
>    return search_n(first, last, 1, value, pred);
>}
>
>to your program and be happy. :-)

I can't (be happy) because I'll have to add this somewhere... and
I would prefer it to be in <algorithm>, don't you?

I'm sure there is a good reason, something I can say to my student
to explain this omission... Or maybe I could say: "That day, Jon
Biggar was late at the committee meeting..." :-]]

Michel Michaud micm19@removethis.mail2.cstjean.qc.ca
http://www3.sympatico.ca/michel.michaud




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud wrote in message ...
>
>Why is there no find with binary predicate? I mean:
>
>   bool Compare(..., ...);
>   vector<...> v;
>   vector<...>::iterator it;
>
>   it= find(v.begin(), v.end(), value, Compare); // NO!

<clip>

>BTW find_if is not the same (it takes a unary predicate
>and no value). Again I know I could use it, but it's
>not even as simple and clear as search_n.

I don't understand what's so bad about:

  it = find_if(v.begin(), v.end(), bind2nd(Compare, value));

Or, if Compare is only a function, then even this isn't all that bad:

  it = find_if(v.begin(), v.end(), bind2nd(ptr_fun(Compare), value));

That is, after all, what header <functional> is for.  It may take a
little getting used to, but eventually anyone who claims to be fluent in
Standard C++ should immediately recognize this idiom for what it is.  Do
you disagree?

-Chris Gurnee




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher M. Gurnee wrote ...
>
>I don't understand what's so bad about:
>
>  it = find_if(v.begin(), v.end(), bind2nd(Compare, value));
>
>Or, if Compare is only a function, then even this isn't all that bad:
>
>  it = find_if(v.begin(), v.end(), bind2nd(ptr_fun(Compare), value));

The problem is, my Compare function was not testing equality, it was
replacing <, the same I would use in sort(v.begin(), v.end(), Compare).
See my other post for a better analysis...

>That is, after all, what header <functional> is for.  It may take a
>little getting used to, but eventually anyone who claims to be fluent in
>Standard C++ should immediately recognize this idiom for what it is.  Do
>you disagree?
In a way, yes. Because I'm a teacher I like to introduce things a little
slower (vector is easy, find is easy, binder/adapter are not until you
explain templates in details... that's much later for me).

Michel Michaud micm19@removethis.mail2.cstjean.qc.ca
http://www3.sympatico.ca/michel.michaud




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

My original post introduced some confusion, that I just cleared
up, in my mind at least... Maybe I can help other people
understand (because nobody really answered me). Please stay
with me...

I got mixed up because I used MSVC online help to find information
about <algorithm> functions. But there is a catch: they use
"Pred pr" everywhere there is a predicate function. For example:

template<class FwdIt, class T, class Pred>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);
template<class FwdIt, class Dist, class T, class Pred>
    FwdIt search_n(FwdIt first, FwdIt last,
        Dist n, const T& val, Pred pr);
template<class InIt, class Pred>
    InIt find_if(InIt first, InIt last, Pred pr);

But pr CANNOT be the same function because in lower_bound it is
used to test for "less than" while in search_n it is used for
testing equality! And both of them are binary predicate while
in find_if it is a unary function.

In Stroustrup (and everywhere else it seems), we can see things like:

template<class FwdIt, class T, class Cmp>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Cmp cmp);
template<class FwdIt, class Dist, class T, class BinPred>
    FwdIt search_n(FwdIt first, FwdIt last,
        Dist n, const T& val, BinPred pr);
template<class InIt, class Pred>
    InIt find_if(InIt first, InIt last, Pred pr);

While not exactly clear, this tells that they are not the same
kind of things...

It seems there is no function in <algorithm> that would
test for equality using a Cmp function, although it could be
done: if (!cmp(a,b) && !cmp(b,a)). I guess this is the
answer to my original post (beside that it would require
a different name than find, but I could accept that).

I can then reformulate my question: how can we use a
Cmp function to find a value using the library. For example,
I was trying to do this (or something like it):

template <typename IT, typename T, typename Cmp>
void SomethingToDo(IT begin, IT end, T v, Cmp cmp)
    {
    IT it= find_cmp(begin, end, v, cmp); // Won't compile

    if (it != end)
        {
        sort(begin, end, cmp);
        it= lower_bound(begin, end, v, cmp);
    // etc.
    }

The only way I can think of, is doing the search myself:

template <typename IT, typename T, typename Cmp>
void SomethingToDo(IT begin, IT end, T v, Cmp cmp)
    {
    IT it=begin;
    for (; it!=end; ++it)
        if (!cmp(v, *it) && !cmp(*it, v))
            break;

    if (it != end)
        //...

But why don't I like that?... Don't you think having a find_cmp
would be better? Is there a "secret" way?

Maybe the library should include an binder/adapter to convert
a Cmp function and a value to a unary function that could be
used with find_if:

template <typename IT, typename T, typename Cmp>
void SomethingToDo(IT begin, IT end, T v, Cmp cmp)
    {
    IT it= find_if(begin, end, MatchFinder<cmp, v>());
    //...

I'll try to do that...

Michel Michaud micm19@removethis.mail2.cstjean.qc.ca
http://www3.sympatico.ca/michel.michaud



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]