Prev: Exception alternatives
Next: class template syntax, maybe?
From: Daniel T. on 27 Jan 2007 23:09
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.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: James Kanze on 29 Jan 2007 04:29
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. 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(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: James Kanze on 29 Jan 2007 04:29
Otis Bricker wrote:
> "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);

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(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 29 Jan 2007 15:55
"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.

> (Of course, providing all three operators: (Toto, int), (int,
> Toto) and (Toto, Toto) is probably a good idea anyway.)

I can accept that.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: James Kanze on 29 Jan 2007 23:26
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. (I presume that the versions
for forward iterators make heavy use of std::advance and
std::distance. To be frank, I was rather surprised that they
were even supported.)

--
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! ]

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Exception alternatives
Next: class template syntax, maybe?