 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Seungbeom Kim
Guest
|
 Posted: Mon May 01, 2006 10:06 pm Post subject: upper_bound(first, last, ...) cannot return last? |
 |
|
ISO/IEC 14882:2003 says:
25.3.3.1 lower_bound
Returns: The furthermost iterator i in the range [first, last] such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: *j < value or comp(*j, value) != false
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
--------
| Quote: | From these descriptions, it seems that lower_bound can return first but
upper_bound cannot; which I cannot understand why. |
Suppose
int a[] = {7}, *first = a, *last = a + sizeof(a) / sizeof(*a);
int *x = std::upper_bound(first, last, 7);
int *y = std::upper_bound(first, last,  ;
then shouldn't x and y be last in this case?
Furthermore, what should or could upper_bound return if it's given an
empty range (first==last) and nothing can be in the range [first, last)?
Is this a known defect?
--
Seungbeom Kim
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
 |
Howard Hinnant
Guest
|
| Posted: Tue May 02, 2006 4:06 pm Post subject: Re: upper_bound(first, last, ...) cannot return last? |
|
|
In article <e35nfm$3su$1 (AT) news (DOT) Stanford.EDU>,
Seungbeom Kim <musiphil (AT) bawi (DOT) org> wrote:
| Quote: | ISO/IEC 14882:2003 says:
25.3.3.1 lower_bound
Returns: The furthermost iterator i in the range [first, last] such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: *j < value or comp(*j, value) != false
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
--------
From these descriptions, it seems that lower_bound can return first but
upper_bound cannot; which I cannot understand why.
Suppose
int a[] = {7}, *first = a, *last = a + sizeof(a) / sizeof(*a);
int *x = std::upper_bound(first, last, 7);
int *y = std::upper_bound(first, last, ;
then shouldn't x and y be last in this case?
|
Yes:
x == last; !(7 < *first) is true
y == last; !(8 < *first) is true
I'm not seeing the problem with the description.
| Quote: | Furthermore, what should or could upper_bound return if it's given an
empty range (first==last) and nothing can be in the range [first, last)?
|
In this case there the furtherest iterator i in the range [first, first)
is first.
| Quote: | Is this a known defect?
|
I suppose the wording could be improved by saying:
Returns: The furthermost iterator i in the range [first, last) such that
for any <ins>dereferenceable</ins> iterator j in the range [first, i)
the following corresponding conditions hold: !(value < *j) or
comp(value, *j) == false
However it seems like a stretch that one can not easily infer that j
must be dereferenceable. But I do not mind opening an issue that
proposes we add "dereferenceable" if anyone thinks that is a significant
clarification.
-Howard
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Guest
|
| Posted: Tue May 02, 2006 9:06 pm Post subject: Re: upper_bound(first, last, ...) cannot return last? |
|
|
Howard Hinnant wrote:
| Quote: | Seungbeom Kim <musiphil (AT) bawi (DOT) org> wrote:
From these descriptions, it seems that lower_bound can return [last] but
upper_bound cannot; which I cannot understand why.
Suppose
int a[] = {7}, *first = a, *last = a + sizeof(a) / sizeof(*a);
int *x = std::upper_bound(first, last, 7);
int *y = std::upper_bound(first, last, ;
then shouldn't x and y be last in this case?
Yes:
x == last; !(7 < *first) is true
y == last; !(8 < *first) is true
I'm not seeing the problem with the description.
|
I think that the issue is that upper_bound() is required to return an
iterator in the range [first, last) -- note that the interval is open
on one end. Since last is not within this range, upper_bound() is
never allowed to return last.
The corresponding interval for lower_bound() is closed, so it can
return last when appropriate.
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
mark
Guest
|
| Posted: Tue May 02, 2006 9:06 pm Post subject: Re: upper_bound(first, last, ...) cannot return last? |
|
|
Howard Hinnant wrote:
| Quote: | In article <e35nfm$3su$1 (AT) news (DOT) Stanford.EDU>,
Seungbeom Kim <musiphil (AT) bawi (DOT) org> wrote:
ISO/IEC 14882:2003 says:
25.3.3.1 lower_bound
Returns: The furthermost iterator i in the range [first, last] such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: *j < value or comp(*j, value) != false
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
--------
From these descriptions, it seems that lower_bound can return first but
|
I think he meant "last" rather than "first"
| Quote: | upper_bound cannot; which I cannot understand why.
Suppose
int a[] = {7}, *first = a, *last = a + sizeof(a) / sizeof(*a);
int *x = std::upper_bound(first, last, 7);
int *y = std::upper_bound(first, last, ;
then shouldn't x and y be last in this case?
Yes:
x == last; !(7 < *first) is true
y == last; !(8 < *first) is true
I'm not seeing the problem with the description.
|
The problem is that last is not an iterator in the range [first,last).
Note the assymetry between lower_bound and upper_bound; lower_bound
returns an iterator in [first, last], and upper_bound returns one in
[first,last).
It looks like a typo to me.
Mark Williams
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Wed May 03, 2006 12:06 am Post subject: Re: upper_bound(first, last, ...) cannot return last? |
|
|
In article <1146596120.437679.243850 (AT) i40g2000cwc (DOT) googlegroups.com>,
"mark" <markw65 (AT) gmail (DOT) com> wrote:
| Quote: | Note the assymetry between lower_bound and upper_bound; lower_bound
returns an iterator in [first, last], and upper_bound returns one in
[first,last).
|
Thanks I missed that point.
| Quote: | It looks like a typo to me.
|
<nod>
-Howard
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Thu May 04, 2006 12:21 am Post subject: Defect Report: upper_bound(first, last, ...) cannot return l |
|
|
ISO/IEC 14882:2003 says:
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
| Quote: | From the description above, upper_bound cannot return last, since it's
not in the interval [first, last). This seems to be a typo, because if |
value is greater than or equal to any other values in the range, or if
the range is empty, returning last seems to be the intended behaviour.
The corresponding interval for lower_bound is also [first, last].
Proposed Change: change [first, last) into [first, last].
--
Seungbeom Kim
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Sat May 06, 2006 6:21 pm Post subject: Re: Defect Report: upper_bound(first, last, ...) cannot retu |
|
|
Seungbeom Kim wrote:
| Quote: | Defect Report: upper_bound(first, last, ...) cannot return last
ISO/IEC 14882:2003 says:
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
From the description above, upper_bound cannot return last, since it's
not in the interval [first, last). This seems to be a typo, because if
value is greater than or equal to any other values in the range, or if
the range is empty, returning last seems to be the intended behaviour.
The corresponding interval for lower_bound is also [first, last].
Proposed Change: change [first, last) into [first, last].
|
Why am I not seeing the moderator's note saying
"Forwarded to C++ Committee" for the defect report above?
Is there anything missing to be a valid defect report?
(I would appreciate it very much if I could see a note saying
what was missing in what was definitely meant to be a defect report
to be forwarded to the C++ committee.)
--
Seungbeom Kim
---
[ 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.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Sun May 07, 2006 4:21 am Post subject: Re: Defect Report: upper_bound(first, last, ...) cannot retu |
|
|
In article <e3hmml$bc7$1 (AT) news (DOT) Stanford.EDU>,
musiphil (AT) bawi (DOT) org (Seungbeom Kim) wrote:
| Quote: | Seungbeom Kim wrote:
Defect Report: upper_bound(first, last, ...) cannot return last
ISO/IEC 14882:2003 says:
25.3.3.2 upper_bound
Returns: The furthermost iterator i in the range [first, last) such that
for any iterator j in the range [first, i) the following corresponding
conditions hold: !(value < *j) or comp(value, *j) == false
From the description above, upper_bound cannot return last, since it's
not in the interval [first, last). This seems to be a typo, because if
value is greater than or equal to any other values in the range, or if
the range is empty, returning last seems to be the intended behaviour.
The corresponding interval for lower_bound is also [first, last].
Proposed Change: change [first, last) into [first, last].
Why am I not seeing the moderator's note saying
"Forwarded to C++ Committee" for the defect report above?
Is there anything missing to be a valid defect report?
(I would appreciate it very much if I could see a note saying
what was missing in what was definitely meant to be a defect report
to be forwarded to the C++ committee.)
|
I got it. This is now lwg issue 577.
-Howard
Library Working Group Chair
---
[ 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.comeaucomputing.com/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
