BinaryPredicate Question
in [C++]
|
From: Otis Bricker on 26 Jan 2007 06:14 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()); 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? Thanks. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Carl Barron on 26 Jan 2007 14:00 In article <Xns98C4680FC6F84obrickermydejanewsco(a)216.196.97.136>, Otis Bricker <obricker(a)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()); > > > > 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? > > Thanks. since std::upper_bound requires a less than predicate [or operator < () for other version] it uses this predicate to effectively test equality and greater than by using the less than predicate. x is equivalent to y as !pred(x,y)&& !pred(y,x) == true. x is greater than y as pred(y,x) == true. Similiar expressions to test <= ,>= ,!= in terms of <. You need both arguments, you don't need to inherit from [directly or in effect] to use the predicate in algorithms in <algorithm> so something like this: struct lessThan { bool operator () (const DataItem &x,const Data &y) const { // normal less than even if it just forwards to // DataItem::operator < } bool operator () (int x,const DataItem &y) const { // ... } bool operator () (const DataItem &x,int x) const { // ... } }; Or add a [preferably explicit to help prevent accidents] ctor to DataItem to take an int arg. and construct as little as needed for lessThan to work. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Greg Herlihy on 26 Jan 2007 14:14 On Jan 26, 3:14 pm, Otis Bricker <obric...(a)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()); No, the first parameter of the IdLessThan predicate function object should be the dereferenced iterator value, while the second parameter should be the comparison value (see �25/8). In other words, the current declaration has the parameters in the reverse of their expected order. > 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); Yes, the above declaration is the overload that function object has to implement. Now, it's conceivable that an overload that had the parameters reversed - would still "work." In particular, if an int is convertible to a DataItem (and vice versa) then it would be the case that each parameter could implicitly convert to the other. And it's exactly this kind of apparently correct, but incorrect behavior, that makes implicit conversions (especially those involving integer types) so problematic. Now, I am not stating that this program necessarily has a bug due to implicit conversions (without DataItem's declaration it's not possible to tell). On the other hand, it would be difficult to see how the current overload with its mismatched parameters could be called (if it is being called) in any other way. > Is this version required or is it just a case of a debug version > requiring it for 'testing', which I believe can be disabled? This version is required and is in fact the only version that is required. > And would it be a good idea to include the extra form to allow the > testing by the debug build? No, not as long as the overload that is implemented is the right one. Greg -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Daniel T. on 26 Jan 2007 14:14 In article <Xns98C4680FC6F84obrickermydejanewsco(a)216.196.97.136>, Otis Bricker <obricker(a)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() ); } > 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.) -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Carl Barron on 27 Jan 2007 06:15
Greg Herlihy <greghe(a)pacbell.net> wrote: > > Yes, the above declaration is the overload that function object has to > implement. Now, it's conceivable that an overload that had the > parameters reversed - would still "work." In particular, if an int is > convertible to a DataItem (and vice versa) then it would be the case > that each parameter could implicitly convert to the other. And it's > exactly this kind of apparently correct, but incorrect behavior, that > makes implicit conversions (especially those involving integer types) > so problematic. Now, I am not stating that this program necessarily has > a bug due to implicit conversions (without DataItem's declaration it's > not possible to tell). On the other hand, it would be difficult to see > how the current overload with its mismatched parameters could be called > (if it is being called) in any other way. Where in the wtandard does it state that there is no uwe of simulating >,>=,<=,==,!= with the less than predicate? Safest is to provide all three op ()'s in the predicate struct and use it for all the algorithms involving DataItem compares. Its not that much work , to do this. It makes maintaince easier as all the compares are in one place. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |