Re: BinaryPredicate Question
Otis Bricker wrote:
"Daniel T." <daniel_t@earthlink.net> wrote in
news:daniel_t-242458.00025327012007@news.west.earthlink.net:
In article <Xns98C4680FC6F84obrickermydejanewsco@216.196.97.136>,
Otis Bricker <obricker@my-dejanews.com> 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());
The following should compile fine:
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
struct DataItem
{
long ID_;
};
class IdLessThan: public binary_function<long, DataItem, bool>
{
public:
bool operator()( long lhs, const DataItem& rhs ) const {
return lhs < rhs.ID_;
}
};
int main()
{
long ID;
vector<DataItem> cache;
vector<DataItem>::iterator it =
upper_bound( cache.begin(), cache.end(), ID, IdLessThan() );
}
Thank you for doing the work I should have. Why I didn't just post a
'working' sample is beyond me.
I ask because the compiler I am using is unable to compile the debug
build of this. It seems to be trying to test the predicate by
calling:
IdLessThan::operator()(const DataItem& lhs,long rhs);
Is this version required or is it just a case of a debug version
requiring it for 'testing', which I believe can be disabled?
And would it be a good idea to include the extra form to allow the
testing by the debug build?
Adding the extra op() is better than not being able to compile in
debug! Maybe you should get a newer compiler instead (if you can.)
Actually, this happened while we are trying to update our compiler to a
newer version that is supposed to be more Standard complient.
It seems that the debug STL code is trying to be helpful and tries to
test that Pred(x,y)!=Pred(y,x).
if (!_Pred(_Left, _Right))
return (false);
else if (_Pred(_Right, _Left))
_DEBUG_ERROR2("invalid operator<", _Where, _Line);
return (true);
I don't think this is legal. The standard makes absolutely no
requirement that std::iterator_traits<
ForwardIterator >::value_type and T are the same, or even
related types. What it says is that the code will call
"comp( *j, value )" (and it seems reasonable to interpret this as
a requirement that this expression be legal).
AS many have suggested, it makes sense to just include both versions.
And perhaps a version for operator()(const DataItem&,const DataItem&) so
that it could even check that the range is ordered, if that is
implemented for debug.
It's reasonable, but I don't think it's a requirement. In fact,
the requirements for BinaryPredicate in the current draft
standard seem to address you're situation quite explicitly:
The BinaryPredicate parameter is used whenever an algorithm
expects a function object that when applied to the result of
dereferencing two corresponding iterators or to
dereferencing an iterator and type T when T is part of the
signature returns a value testable as true. In other words,
if an algorithm takes BinaryPredicate binary_pred as its
argument and first1 and first2 as its iterator arguments, it
should work correctly in the construct if (binary_pred
(*first1 , *first2 )){...}. 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)){...}. binary_pred shall not apply any non-constant
function through the dereferenced iterators.
It seems to me that there is a specific requirement that the
iterator always provide the first argument to the predicate.
(Note that the only version of the standard I have on this
machine is the next to the last draft---N2009. The original
standard may have been worded differently, and there's also a
slight chance that the wording here has changed since the draft
I'm looking at.)
But I am a bit surprised that some have said that the version
operator()(const DataItem&,long) is the one that is needed, though I
might have misunderstood the comments.
See above. That seems to be the current status, at least.
The couple of compilers I had
tried all worked with the operator()(long,const DataItem&). I tried
something else and found that for lower_bound my current compiler does
seem to want (const DI&,long). I can understand this.
If the test was simply std::less<DataItem>, I would have expected the
upper_bound to be calling less::operator()(myvalue,testValue) and the
first point that passed( or the end of range) would be the result. With
lower_bound and less, I would expect it to be testing
not(less::operator()(testValue,myValue)) and terminating the same way.
The test if you do not provide the predictate operator is *j <
value. Again, the dereferenced iterator on the left. (It's
interesting that lower_bound does not use std::less.
Presumably, this is intentionally, in order to allow the
dereferenced iterator and the value to have different types. It
does mean, however, that you can't use the three argument form
on a container of pointers.)
--
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! ]