BinaryPredicate Question
in [C++]
|
From: James Kanze on 27 Jan 2007 06:10 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). > 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? It's required. It is, in fact, the only version required. > And would it be a good idea to include the extra form to allow the > testing by the debug build? Generally, if you can't build the debug version, it's best to suppose that the production version won't work correctly anyway. (In this case, I'd be surprised if you could build any version.) -- James Kanze (Gabi Software) email: james.kanze(a)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! ]
From: Otis Bricker on 27 Jan 2007 12:14 "Daniel T." <daniel_t(a)earthlink.net> wrote in news:daniel_t-242458.00025327012007(a)news.west.earthlink.net: > 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() ); > } > 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); 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. 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. 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. Of course, I imagine that it could be implemented in other ways. Or I could just have my head on backwards today. Thanks again to all for the help thinking about this. Otis Bricker -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Daniel T. on 27 Jan 2007 12:13 "James Kanze" <james.kanze(a)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? -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Otis Bricker on 27 Jan 2007 16:54 "Greg Herlihy" <greghe(a)pacbell.net> wrote in news:1169873749.305383.305950(a)v45g2000cwv.googlegroups.com: > > > 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 guess it would help to have a copy of the standard to review. The draft version I usually reference online says: "Returns: The furthermost iterator i in the range [first,last) such that any iterator j in the range of [first,i) the following corresponding conditions hold: !(value<*j) or comp(value,*j)==false" The this param order, (long,const DataItem&) seems more in line with a standard binary predicate like std::less. And since the release build does not compile if I include only the (const dataItem&,long) version, does that mean the compiler is non-conforming? Guess I need to pop for a copy of the standard. 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 27 Jan 2007 16:55 Otis Bricker <obricker(a)my-dejanews.com> wrote: > 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. 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. > > Of course, I imagine that it could be implemented in other ways. Or I > could just have my head on backwards today. > > Thanks again to all for the help thinking about this. > > Otis Bricker Well upper_bound and lower_bound assume a sorted sequence and a weak ordering, so that the other relops can be emulated with just the code for less than. [a user specifiec binary predicate, or operator < ()] That said there is using normal operators x > y iff y < x x <= y iff !(y<x) x >= y iff !(x < y) x == y iff !(x<y) && !(y<x) x != y iff x < y && y < x note some swaps of the arguments. Safer to provide them all so changing a compiler again does not provide a problem. Further it makes the predicate more reusable, and easier to maintain/ -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 Prev: Exception alternatives Next: class template syntax, maybe? |