Error in the C++ standard?

[desktop]

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"?

 

[Charles Bailey]

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.

 

[desktop]

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?

 

[Zeppe]

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

 

[Charles Bailey]

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.

 

[Andrew Koenig]

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