424,964 Members | 1,290 Online 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
5 Replies

 P: n/a On 2007-06-13, desktop

 P: n/a Charles Bailey wrote: On 2007-06-13, desktop In section 23.1.2 table 69 upper and lower bound are defined like:a.lower_bound(k) iterator; logarithmicreturns an iterator pointing to thefirst element with key not less than ka.upper_bound(k) iterator; logarithmicreturns an iterator pointing to thefirst element with key greater than k should "not less" in lower_bound not just be "less"? Or is it supposedto 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 >In section 23.1.2 table 69 upper and lower bound are defined like:a.lower_bound(k) iterator; logarithmicreturns an iterator pointing to thefirst element with key not less than ka.upper_bound(k) iterator; logarithmicreturns an iterator pointing to thefirst element with key greater than k should "not less" in lower_bound not just be "less"? Or is itsupposed 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. "Notless" is, conceptually, "greater than or equal" so lower_bound isupper_bound when there is no matching element for k. This meets thelogical requirement that [lower_bound, upper_bound) is empty. Iflower_bound is not the same as upper_bound it implies that there is atleast 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 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" 