Error in the C++ standard? - c++

On 2007-06-13, desktop <fff@sss.com> wrote:
> In section 23.1.2 table 69 upper and lower bound are defined like:
>
> a.lower_bound(k) iterator; logarithmic
> returns an iterator pointing to the
> first element with key not less than k
>
> a.upper_bound(k) iterator; logarithmic
> returns an iterator pointing to the
> first element with key greater than k
>
>
> should "not less" in lower_bound not just be "less"? Or is it supposed
> to be interpreted as "greater than or equal"?

The standard is correct. Iterating through the range [lower_bound,
upper_bound) should iterate through elements which "equal" k. "Not
less" is, conceptually, "greater than or equal" so lower_bound is
upper_bound when there is no matching element for k. This meets the
logical requirement that [lower_bound, upper_bound) is empty. If
lower_bound is not the same as upper_bound it implies that there is at
least one element that matches k and [lower_bound, upper_bound)
contains all such elements.

Charles Bailey wrote:
> On 2007-06-13, desktop <fff@sss.com> wrote:
>> In section 23.1.2 table 69 upper and lower bound are defined like:
>>
>> a.lower_bound(k) iterator; logarithmic
>> returns an iterator pointing to the
>> first element with key not less than k
>>
>> a.upper_bound(k) iterator; logarithmic
>> returns an iterator pointing to the
>> first element with key greater than k
>>
>>
>> should "not less" in lower_bound not just be "less"? Or is it supposed
>> to be interpreted as "greater than or equal"?
>
> The standard is correct. Iterating through the range [lower_bound,
> upper_bound) should iterate through elements which "equal" k. "Not
> less" is, conceptually, "greater than or equal" so lower_bound is
> upper_bound when there is no matching element for k. This meets the
> logical requirement that [lower_bound, upper_bound) is empty. If
> lower_bound is not the same as upper_bound it implies that there is at
> least one element that matches k and [lower_bound, upper_bound)
> contains all such elements.

Ok so:

a.lower_bound(k) iterator; logarithmic
returns an iterator pointing to the
first element with key greater than or equal to k

is as valid a definition, right?

desktop wrote:
> Charles Bailey wrote:
>> On 2007-06-13, desktop <fff@sss.com> wrote:
>>> In section 23.1.2 table 69 upper and lower bound are defined like:
>>>
>>> a.lower_bound(k) iterator; logarithmic
>>> returns an iterator pointing to the
>>> first element with key not less than k
>>>
>>> a.upper_bound(k) iterator; logarithmic
>>> returns an iterator pointing to the
>>> first element with key greater than k
>>>
>>>
>>> should "not less" in lower_bound not just be "less"? Or is it
>>> supposed to be interpreted as "greater than or equal"?
>>
>> The standard is correct. Iterating through the range [lower_bound,
>> upper_bound) should iterate through elements which "equal" k. "Not
>> less" is, conceptually, "greater than or equal" so lower_bound is
>> upper_bound when there is no matching element for k. This meets the
>> logical requirement that [lower_bound, upper_bound) is empty. If
>> lower_bound is not the same as upper_bound it implies that there is at
>> least one element that matches k and [lower_bound, upper_bound)
>> contains all such elements.
>
> Ok so:
>
> a.lower_bound(k) iterator; logarithmic
> returns an iterator pointing to the
> first element with key greater than or equal to k
>
> is as valid a definition, right?

yes.


Regards,

Zeppe

On 2007-06-13, desktop <fff@sss.com> wrote:
>
> Ok so:
>
> a.lower_bound(k) iterator; logarithmic
> returns an iterator pointing to the
> first element with key greater than or equal to k
>
> is as valid a definition, right?

It should be "greater than or equivalent to k" to be consistent with
the language used in that section of the standard. As it mentions the
key type could have an operator== but this is irrelevant for the
purposes of lower_bound, upper_bound, etc. Equivalence of k1 and k2
means that neither one sorts before the other according to the
container's ordering relation.

I suspect that this is why they chose the working "not less than" in
this case.

"desktop" <fff@sss.com> wrote in message
news:f4okjk$aad$1@news.net.uni-c.dk...

> Ok so:

> a.lower_bound(k) iterator; logarithmic
> returns an iterator pointing to the
> first element with key greater than or equal to k

> is as valid a definition, right?

Well, sort of. The problem is that "less" is the only relation that is
required to be defined in order for lower_bound to work, so the behavior of
lower_bound really should be described in terms of "less", not "greater than
or equal".