By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,964 Members | 1,290 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,964 IT Pros & Developers. It's quick & easy.

Error in the C++ standard?

P: n/a
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"?

Jun 13 '07 #1
Share this Question
Share on Google+
5 Replies


P: n/a
On 2007-06-13, desktop <ff*@sss.comwrote:
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.
Jun 13 '07 #2

P: n/a
Charles Bailey wrote:
On 2007-06-13, desktop <ff*@sss.comwrote:
>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?
Jun 13 '07 #3

P: n/a
desktop wrote:
Charles Bailey wrote:
>On 2007-06-13, desktop <ff*@sss.comwrote:
>>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
Jun 13 '07 #4

P: n/a
On 2007-06-13, desktop <ff*@sss.comwrote:
>
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.

Jun 13 '07 #5

P: n/a
"desktop" <ff*@sss.comwrote in message
news:f4**********@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".
Jun 13 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.