BinaryPredicate Question
in [C++]
|
From: James Kanze on 30 Jan 2007 14:25 Daniel T. wrote: > "James Kanze" <james.kanze(a)gmail.com> wrote: > > Daniel T. wrote: > > > "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? > > Are you sure. > Yes. > > I just looked at the Dinkumware site, and the > > documentation for lower_bound... > Isn't relevant because we are talking about upper_bound, not lower_bound. Which explains the confusion. The current draft of the standard is contradictory here. In the requirements specifications of algorithms (which I quoted elsewhere), it explicitly says that the iterator will always be on the right; in the documentation of upper_bound, however, it speaks of "!(comp(value, e)", where e corresponds to something dereferenced by the iterator. (Come to think about it: in the most general cases---equal_range, for example---, you need all four operators: <, >, <=, and >=. To get them from just one operator---and !---you need to be able to call that operator in both directions. So I suspect that the text in the current draft still needs some work.) -- 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: Daniel T. on 30 Jan 2007 14:22
"James Kanze" <james.kanze(a)gmail.com> wrote: > Daniel T. wrote: > > 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. > > > Your logic is correct. Upper and lower range functions need to be able > > to work with forward interators so they must start at the beginning of > > the range and progress from there. There really is no reason to have a > > op() for going the other way in the container. > > The specification says that they may make at most log n > comparisons, which isn't possible if they simply progress > linearly through the container. Progressing linearly through the container would be ridiculous in any case. We are talking about a container that is known to be sorted. The key point here is that the algorithm doesn't need to know if two elements are equal, so it doesn't need to be able to reverse the arguments of the predicates operator. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |