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, 8);

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                      ]

In article <e35nfm$3su$1@news.Stanford.EDU>,
 Seungbeom Kim <musiphil@bawi.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
> 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, 8);
>
> 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.

> 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.

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

Howard Hinnant wrote:
> In article <e35nfm$3su$1@news.Stanford.EDU>,
>  Seungbeom Kim <musiphil@bawi.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"

> > 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, 8);
> >
> > 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                      ]

Howard Hinnant wrote:
>  Seungbeom Kim <musiphil@bawi.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, 8);
> >
> > 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                      ]

In article <1146596120.437679.243850@i40g2000cwc.googlegroups.com>,
 "mark" <markw65@gmail.com> wrote:

> 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.

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