stefan_heinzmann@yahoo.com (Stefan Heinzmann) writes:

> Hi all,
>
> I am unsure what the requirements for a predicate are which is
> supposed to be used with std::equal_range, std::lower_bound and
> similar algorithms. I am of course talking about the "long" form of
> the algorithm which takes the predicate as an explicit argument.
>
> I've got a case where the element in the collection is actually a
> key/value pair, but the predicate is supposed to compare the key
> only. Now I could in theory do this:
>
> template<typename Key, typename Val>
> struct Element {
>      Key key;
>      Val val;
> };
>
> template<typename Key, typename Val>
> struct Predicate {
>      typedef const Element<Key,Val> Elem;
>      bool operator()(Elem &e, const Key &k) const { return e.key < k; }
>      bool operator()(const Key &k, Elem &e) const { return k < e.key; }
> };
>
> // pseudo code, somewhere in the application code...
>      Key k = ...;
>      std::lower_bound(from_iter, to_iter, key, Predicate<...>());
>
>
> In other words, the predicate is not comparing equal types. This would
> allow me to avoid constructing an element just to pass it to
> lower_bound, which would in any case make use of the key only.
>
> GCC 3.3 and VC++ 7.1 accept this, but the Comeau compiler bombs out
> because a concept check fails. Is Comeau overly restrictive?

I think
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
addresses your question.  The proposed wording from this paper (with
minor changes) is current for
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 which
has WP status.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote in message news:<VsMqc.21467$KE6.17835@newsread3.news.atl.earthlink.net>...
> On Wed, 19 May 2004 14:42:46 +0000 (UTC), kuyper@wizard.net (James
> Kuyper) wrote:
>
> > jpotter@falcon.lhup.edu (John Potter) wrote in message news:<AMmqc.20053$KE6.15110@newsread3.news.atl.earthlink.net>...
>
> > > On Tue, 18 May 2004 04:42:53 +0000 (UTC), kuyper@wizard.net (James
> > > Kuyper) wrote:
>
> > > > The standard doesn't directly require that the ForwardIterator type
> > > > have a value type of T, though it might be argued that this is implied
> > > > by the name "ForwardIterator". The standard defines the behavior of
>
> > > The remaining error is iterator::value_type is not the same type as
> > > value type.  Nothing will remove that.  Where is that requirement?
>
> > It's not explicitly required; I'm not sure whether we're supposed to
> > infer such a requirement from the type names. The standard does
> > specify that we are supposed to infer some requirements from those
> > names: ForwardIterator is definitely required to be a forward
> > iterator.
..
> However, the question in csc++ is whether the library is conformant in
> producing concept checks which reject the original code.  IMO, concept
> checks which reject working code is about as useful as compilers which
> run nethack for undefined behavior.  There is a difference between
> might not work and malicious breakage.

Agreed. However, since I can see a way to read the standard as
imposing that requirement, I'm willing to give them the benefit of the
doubt and say that it's not malicious. They might even be correct, in
which case it doesn't even count as breakeage.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Thu, 20 May 2004 18:45:06 +0000 (UTC), kuyper@wizard.net (James
Kuyper) wrote:

> Agreed. However, since I can see a way to read the standard as
> imposing that requirement, I'm willing to give them the benefit of the
> doubt and say that it's not malicious.

Sorry for forgetting the history of this.  See lwg issue 270.  Who knows
what is allowed today, but the WP says the original code will be valid
in the future.

Here is another interesting, not malicious, version.

struct P { int x, y; };
bool operator< (int lhs, P const& rhs) { return lhs < rhs.x; }
bool operator< (P const& lhs, int rhs) { return lhs.x < rhs; }
void f (vector<P> const& v) { lower_bound(v.begin(), v.end(), 42); }

I know that there exists an STL implementation which will not
accept this code.  It is good programming practice not any attempt
to enforce maybe rules.  The same implementation will accept the
code using a function object.  It seems that issue 270 will make
the operator< version non-conforming.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hi all,

I am unsure what the requirements for a predicate are which is supposed
to be used with std::equal_range, std::lower_bound and similar
algorithms. I am of course talking about the "long" form of the
algorithm which takes the predicate as an explicit argument.

I've got a case where the element in the collection is actually a
key/value pair, but the predicate is supposed to compare the key only.
Now I could in theory do this:

template<typename Key, typename Val>
struct Element {
     Key key;
     Val val;
};

template<typename Key, typename Val>
struct Predicate {
     typedef const Element<Key,Val> Elem;
     bool operator()(Elem &e, const Key &k) const { return e.key < k; }
     bool operator()(const Key &k, Elem &e) const { return k < e.key; }
};

// pseudo code, somewhere in the application code...
     Key k = ...;
     std::lower_bound(from_iter, to_iter, key, Predicate<...>());


In other words, the predicate is not comparing equal types. This would
allow me to avoid constructing an element just to pass it to
lower_bound, which would in any case make use of the key only.

GCC 3.3 and VC++ 7.1 accept this, but the Comeau compiler bombs out
because a concept check fails. Is Comeau overly restrictive?

--
Cheers
Stefan

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

stefan_heinzmann@yahoo.com (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1@news.t-online.com>...
> Hi all,
>
> I am unsure what the requirements for a predicate are which is supposed
> to be used with std::equal_range, std::lower_bound and similar
> algorithms. I am of course talking about the "long" form of the
> algorithm which takes the predicate as an explicit argument.
>
> I've got a case where the element in the collection is actually a
> key/value pair, but the predicate is supposed to compare the key only.
> Now I could in theory do this:
>
> template<typename Key, typename Val>
> struct Element {
>      Key key;
>      Val val;
> };
>
> template<typename Key, typename Val>
> struct Predicate {
>      typedef const Element<Key,Val> Elem;
>      bool operator()(Elem &e, const Key &k) const { return e.key < k; }
>      bool operator()(const Key &k, Elem &e) const { return k < e.key; }
> };
>
> // pseudo code, somewhere in the application code...
>      Key k = ...;
>      std::lower_bound(from_iter, to_iter, key, Predicate<...>());
>
>
> In other words, the predicate is not comparing equal types. This would
> allow me to avoid constructing an element just to pass it to
> lower_bound, which would in any case make use of the key only.
>
> GCC 3.3 and VC++ 7.1 accept this, but the Comeau compiler bombs out
> because a concept check fails. Is Comeau overly restrictive?

The standard doesn't directly require that the ForwardIterator type
have a value type of T, though it might be argued that this is implied
by the name "ForwardIterator". The standard defines the behavior of
the algorithm in terms of  pred(*k,value), which must therefore be a
valid expression, where 'k' is an instance of ForwardIterator, and
value is an instance of T. Your use of the algorithm does conform to
that requirement.

However, it's also required (25.3p3) that 'pred' induce a strict weak
ordering on the values. If *k and value are allowed to be different
types, it's not clear from the description which of the two types it
must induce that ordering on; probably both. Your Predicate class
can't do that for either type, because it doesn't have an operator()
overload that works on two arguments of the same type.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <c88nii$bjb$00$1@news.t-online.com>, Stefan Heinzmann
<stefan_heinzmann@yahoo.com> wrote:

> In other words, the predicate is not comparing equal types. This would
> allow me to avoid constructing an element just to pass it to
> lower_bound, which would in any case make use of the key only.
>
> GCC 3.3 and VC++ 7.1 accept this, but the Comeau compiler bombs out
> because a concept check fails. Is Comeau overly restrictive?
  [25.3] states that the predicate called comp in this section is a
strict weak ordering.  The strict means that !comp(x,x) is all ways
true.  This means comp must have two arguments of the same type.

All is not lost if you write an iterator that iterates over your
sequence of your class but points to the key values.

boist::transform_iterator does this but it is not in the standard or
tr1 therefore I skip the details here, but using it or a specialize
hand written iterator over pairs, but 'pointing to' only the
first_type.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper schrieb:
> stefan_heinzmann@yahoo.com (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1@news.t-online.com>...
[...]
>>template<typename Key, typename Val>
>>struct Element {
>>     Key key;
>>     Val val;
>>};
>>
>>template<typename Key, typename Val>
>>struct Predicate {
>>     typedef const Element<Key,Val> Elem;
>>     bool operator()(Elem &e, const Key &k) const { return e.key < k; }
>>     bool operator()(const Key &k, Elem &e) const { return k < e.key; }
>>};
>>
>>// pseudo code, somewhere in the application code...
>>     Key k = ...;
>>     std::lower_bound(from_iter, to_iter, key, Predicate<...>());
[...]
> The standard doesn't directly require that the ForwardIterator type
> have a value type of T, though it might be argued that this is implied
> by the name "ForwardIterator". The standard defines the behavior of
> the algorithm in terms of  pred(*k,value), which must therefore be a
> valid expression, where 'k' is an instance of ForwardIterator, and
> value is an instance of T. Your use of the algorithm does conform to
> that requirement.
>
> However, it's also required (25.3p3) that 'pred' induce a strict weak
> ordering on the values. If *k and value are allowed to be different
> types, it's not clear from the description which of the two types it
> must induce that ordering on; probably both. Your Predicate class
> can't do that for either type, because it doesn't have an operator()
> overload that works on two arguments of the same type.

Would that requirement be met if I added a third overload to the
predicate like this?

bool operator()(Elem &a, Elem &b) const { return a.key < b.key; }

I would still pass the key instead of a complete element to the
lower_bound function.

--
Cheers
Stefan

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Tue, 18 May 2004 04:42:53 +0000 (UTC), kuyper@wizard.net (James
Kuyper) wrote:

> stefan_heinzmann@yahoo.com (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1@news.t-online.com>...

> > I am unsure what the requirements for a predicate are which is supposed
> > to be used with std::equal_range, std::lower_bound and similar
> > algorithms. I am of course talking about the "long" form of the
> > algorithm which takes the predicate as an explicit argument.

> > I've got a case where the element in the collection is actually a
> > key/value pair, but the predicate is supposed to compare the key only.
> > Now I could in theory do this:

> > template<typename Key, typename Val>
> > struct Element {
> >      Key key;
> >      Val val;
> > };

> > template<typename Key, typename Val>
> > struct Predicate {
> >      typedef const Element<Key,Val> Elem;
> >      bool operator()(Elem &e, const Key &k) const { return e.key < k; }
> >      bool operator()(const Key &k, Elem &e) const { return k < e.key; }
> > };

> > // pseudo code, somewhere in the application code...
> >      Key k = ...;
> >      std::lower_bound(from_iter, to_iter, key, Predicate<...>());

> > In other words, the predicate is not comparing equal types. This would
> > allow me to avoid constructing an element just to pass it to
> > lower_bound, which would in any case make use of the key only.

> > GCC 3.3 and VC++ 7.1 accept this, but the Comeau compiler bombs out
> > because a concept check fails. Is Comeau overly restrictive?

> The standard doesn't directly require that the ForwardIterator type
> have a value type of T, though it might be argued that this is implied
> by the name "ForwardIterator". The standard defines the behavior of
> the algorithm in terms of  pred(*k,value), which must therefore be a
> valid expression, where 'k' is an instance of ForwardIterator, and
> value is an instance of T. Your use of the algorithm does conform to
> that requirement.

> However, it's also required (25.3p3) that 'pred' induce a strict weak
> ordering on the values. If *k and value are allowed to be different
> types, it's not clear from the description which of the two types it
> must induce that ordering on; probably both. Your Predicate class
> can't do that for either type, because it doesn't have an operator()
> overload that works on two arguments of the same type.

One of the errors generated involves using the pred for the values.
Adding the compare for two ints clears that error.  Adding the compare
for two iterator::value_types does nothing.  It is now a strict weak
order for either.

The remaining error is iterator::value_type is not the same type as
value type.  Nothing will remove that.  Where is that requirement?

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote in message news:<AMmqc.20053$KE6.15110@newsread3.news.atl.earthlink.net>...
> On Tue, 18 May 2004 04:42:53 +0000 (UTC), kuyper@wizard.net (James
> Kuyper) wrote:
..
> > The standard doesn't directly require that the ForwardIterator type
> > have a value type of T, though it might be argued that this is implied
> > by the name "ForwardIterator". The standard defines the behavior of
..
> The remaining error is iterator::value_type is not the same type as
> value type.  Nothing will remove that.  Where is that requirement?

It's not explicitly required; I'm not sure whether we're supposed to
infer such a requirement from the type names. The standard does
specify that we are supposed to infer some requirements from those
names: ForwardIterator is definitely required to be a forward
iterator.

This requirement can be met: create a special iterator that iterates
through Elements, but which has an operator*() which returns a
reference to the Key that is contained in the Element that it points
at.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

stefan_heinzmann@yahoo.com (Stefan Heinzmann) wrote in message news:<c8cg27$p5$00$1@news.t-online.com>...
> James Kuyper schrieb:
..
> > However, it's also required (25.3p3) that 'pred' induce a strict weak
> > ordering on the values. If *k and value are allowed to be different
> > types, it's not clear from the description which of the two types it
> > must induce that ordering on; probably both. Your Predicate class
> > can't do that for either type, because it doesn't have an operator()
> > overload that works on two arguments of the same type.
>
> Would that requirement be met if I added a third overload to the
> predicate like this?
>
> bool operator()(Elem &a, Elem &b) const { return a.key < b.key; }
>
> I would still pass the key instead of a complete element to the
> lower_bound function.

I think so. To be safe, add an overload for two Keys, as well.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Wed, 19 May 2004 14:42:46 +0000 (UTC), kuyper@wizard.net (James
Kuyper) wrote:

> jpotter@falcon.lhup.edu (John Potter) wrote in message news:<AMmqc.20053$KE6.15110@newsread3.news.atl.earthlink.net>...

> > On Tue, 18 May 2004 04:42:53 +0000 (UTC), kuyper@wizard.net (James
> > Kuyper) wrote:

> > > The standard doesn't directly require that the ForwardIterator type
> > > have a value type of T, though it might be argued that this is implied
> > > by the name "ForwardIterator". The standard defines the behavior of

> > The remaining error is iterator::value_type is not the same type as
> > value type.  Nothing will remove that.  Where is that requirement?

> It's not explicitly required; I'm not sure whether we're supposed to
> infer such a requirement from the type names. The standard does
> specify that we are supposed to infer some requirements from those
> names: ForwardIterator is definitely required to be a forward
> iterator.

> This requirement can be met: create a special iterator that iterates
> through Elements, but which has an operator*() which returns a
> reference to the Key that is contained in the Element that it points
> at.

Yes.  Either transform (value) or projection (reference) iterator from
boost will do the job.

However, the question in csc++ is whether the library is conformant in
producing concept checks which reject the original code.  IMO, concept
checks which reject working code is about as useful as compilers which
run nethack for undefined behavior.  There is a difference between
might not work and malicious breakage.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]