 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Stefan Heinzmann
Guest
|
 Posted: Mon May 17, 2004 3:01 am Post subject: Requirements for a binary predicate |
 |
|
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 ]
|
|
| Back to top |
|
 |
James Kuyper
Guest
|
| Posted: Tue May 18, 2004 4:42 am Post subject: Re: Requirements for a binary predicate |
|
|
[email]stefan_heinzmann (AT) yahoo (DOT) com[/email] (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1 (AT) news (DOT) t-online.com>...
| Quote: | 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
struct Predicate {
typedef const Element
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 ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Tue May 18, 2004 6:30 am Post subject: Re: Requirements for a binary predicate |
|
|
In article <c88nii$bjb$00$1 (AT) news (DOT) t-online.com>, Stefan Heinzmann
<stefan_heinzmann (AT) yahoo (DOT) com> wrote:
| Quote: | 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 ]
|
|
| Back to top |
|
|
Stefan Heinzmann
Guest
|
| Posted: Tue May 18, 2004 4:57 pm Post subject: Re: Requirements for a binary predicate |
|
|
James Kuyper schrieb:
| Quote: | stefan_heinzmann (AT) yahoo (DOT) com (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1 (AT) news (DOT) t-online.com>...
[...]
template<typename Key, typename Val
struct Element {
Key key;
Val val;
};
template
struct Predicate {
typedef const Element
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 ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Tue May 18, 2004 4:57 pm Post subject: Re: Requirements for a binary predicate |
|
|
On Tue, 18 May 2004 04:42:53 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (James
Kuyper) wrote:
| Quote: | stefan_heinzmann (AT) yahoo (DOT) com (Stefan Heinzmann) wrote in message news:<c88nii$bjb$00$1 (AT) news (DOT) 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
struct Predicate {
typedef const Element
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 ]
|
|
| Back to top |
|
|
James Kuyper
Guest
|
| Posted: Wed May 19, 2004 2:42 pm Post subject: Re: Requirements for a binary predicate |
|
|
[email]jpotter (AT) falcon (DOT) lhup.edu[/email] (John Potter) wrote in message news:<AMmqc.20053$KE6.15110 (AT) newsread3 (DOT) news.atl.earthlink.net>...
| Quote: | On Tue, 18 May 2004 04:42:53 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (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 ]
|
|
| Back to top |
|
|
James Kuyper
Guest
|
| Posted: Wed May 19, 2004 5:15 pm Post subject: Re: Requirements for a binary predicate |
|
|
[email]stefan_heinzmann (AT) yahoo (DOT) com[/email] (Stefan Heinzmann) wrote in message news:<c8cg27$p5$00$1 (AT) news (DOT) t-online.com>...
| Quote: | 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 ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed May 19, 2004 5:48 pm Post subject: Re: Requirements for a binary predicate |
|
|
On Wed, 19 May 2004 14:42:46 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (James
Kuyper) wrote:
| Quote: | jpotter (AT) falcon (DOT) lhup.edu (John Potter) wrote in message news:<AMmqc.20053$KE6.15110 (AT) newsread3 (DOT) news.atl.earthlink.net>...
On Tue, 18 May 2004 04:42:53 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (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 ]
|
|
| Back to top |
|
|
James Kuyper
Guest
|
| Posted: Thu May 20, 2004 6:45 pm Post subject: Re: Requirements for a binary predicate |
|
|
[email]jpotter (AT) falcon (DOT) lhup.edu[/email] (John Potter) wrote in message news:<VsMqc.21467$KE6.17835 (AT) newsread3 (DOT) news.atl.earthlink.net>...
| Quote: | On Wed, 19 May 2004 14:42:46 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (James
Kuyper) wrote:
[email]jpotter (AT) falcon (DOT) lhup.edu[/email] (John Potter) wrote in message news:<AMmqc.20053$KE6.15110 (AT) newsread3 (DOT) news.atl.earthlink.net>...
On Tue, 18 May 2004 04:42:53 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (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 ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Fri May 21, 2004 3:10 am Post subject: Re: Requirements for a binary predicate |
|
|
On Thu, 20 May 2004 18:45:06 +0000 (UTC), [email]kuyper (AT) wizard (DOT) net[/email] (James
Kuyper) wrote:
| Quote: | 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
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 ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Wed May 26, 2004 6:00 pm Post subject: Re: Requirements for a binary predicate |
|
|
[email]stefan_heinzmann (AT) yahoo (DOT) com[/email] (Stefan Heinzmann) writes:
| Quote: | 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
struct Predicate {
typedef const Element
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 ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
