Re: BinaryPredicate Question
Daniel T. wrote:
"James Kanze" <james.kanze@gmail.com> wrote:
Otis Bricker wrote:
I'm trying to figure out is the following technique is valid.
Given
std::vector<DataItem> cache;
which is sorted by the ID_ field of each DataItem.
And this Predicate class:
class IdLessThan: public std::binary_function<long, DataItem, bool>
{
public:
bool operator()
( long lhs, const DataItem& rhs)const{return lhs <
rhs.ID_;};
};
Is the following valid?
Vector<DataItem>::iterator it =
std::upper_bound(cache.begin(),cache.end(),ID, IdLessThan());
No. Given this call, IdLessThan must be callable with a first
argument of type DataItem, and a second of type long (and the
reverse).
Several people have said this now, but the OPs code works fine in gcc
and at http://www.comeaucomputing.com/tryitout/.
Also, Dikumware's and SGI's documentation say that upper_bound only uses
pred(x, y) where x is the 3rd argument passed in and y is the elements
in the container.
What am I missing?
Are you sure. I just looked at the Dinkumware site, and the
documentation for lower_bound 1) refers to the predicate
`*(first + M) < value' in the description of the three argument
form, and 2) says that the four argument form replaces
operator<(X, Y) with pred(X, Y). I'd interpret that as saying
that the dereferenced iterator is on the right.
In my case, I'm basing my comments on a recent draft, and I seem
to recall vaguely that there were some DR's on this subject.
(IIRC, the original STL was rather vague, and more or less
assumed that the T would be the value_type of the iterator.) If
I remember, I'll check Monday (when I have access to a machine
with both the 1998 version of the standard and the very latest
draft), but the draft I have here (N2009---I don't have an exact
date, but I think it's the next to last) very explicitly says:
"BinaryPredicate always takes the first iterator type as its
first argument, that is, in those cases when T value is part of
the signature, it should work correctly in the context of `if
(binary_pred (*first1 , value )){...}'."
In practice, the Dinkumware implementation, like all others, is
ultimately based on the original HP implementation, and I would
be very surprised if there were any differences in the
implementations in this point. The people at Dinkumware are
also very active in the library group, and I can't imagine their
not saying anything if a change in the draft broke all existing
implementations and existing user code (and I can't imagine the
rest of the committee not listening to them in such a case). So
I'm somewhat surprised that implementations do anything else
(and that the original poster's code ever worked anywhere).
FWIW: The following compiles with g++ (4.0.1), even when I set
all debugging options (including -D_GLIBCXX_CONCEPT_CHECKS) and
also with VC++ 8 (which uses the Dinkumware library):
struct Toto
{
int id ;
std::string value ;
Toto( int id, std::string const& value )
: id( id )
, value( value )
{
}
} ;
struct Cmp
{
bool operator()( Toto const& lhs, int rhs )
const
{
return lhs.id < rhs ;
}
} ;
int
main()
{
std::vector< Toto > v ;
static char const* const
init[] =
{
"one", "two", "three", "four", "five"
} ;
for ( int i = 0 ; i < 5 ; ++ i ) {
v.push_back( Toto( i + 1, init[ i ] ) ) ;
}
std::vector< Toto >::iterator
i = std::lower_bound( v.begin(),
v.end(),
3,
Cmp() ) ;
std::cout << i->value << std::endl ;
return 0 ;
}
Inverting the order of the arguments in Cmp, to correspond to
the code originally posted, and it fails to compile with either.
(Of course, providing all three operators: (Toto, int), (int,
Toto) and (Toto, Toto) is probably a good idea anyway.)
--
James Kanze (Gabi Software) email: james.kanze@gmail.com
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]