On Sun, 19 Feb 2012 16:44:05 -0500, Ellery Newcomer
<[email protected]> wrote:
Is it just me or are lowerBound and upperBound really unintuitively
named?
It's not just you. Quoting from one of my proposed implementation of
std.container.RedBlackTree (I hope Andrei doesn't mind, but I have
included his response, which I think explains rather well the reasoning
behind the naming):
----------------------
The attached version has added upperBound(Elem e) and lowerBound(Elem e).
I found the docs to be confusing regarding upperBound and lowerBound.
According to the docs, lowerBound is supposed to return all keys less than
e, but wouldn't that make e the upper bound? Ditto for upperBound.
Also, shouldn't one of these ranges actually include e?
In any case, I made lowerBound(e) return all elements >= e and
upperBound(e) returns all elements < e, that seemed like the most
intuitive. Let me know if I'm wrong.
----------------------
Andrei's response:
----------------------
STL docs are written in a confusing manner but after you get used they are
pretty logical. The docs at
http://www.cplusplus.com/reference/stl/map/lower_bound/ say:
"Returns an iterator pointing to the first element in the container whose
key does not compare less than x (using the container's comparison
object), i.e. it is either equal or greater."
The idea is that everything in the range
[begin(), lower_bound(x))
is strictly less than x. Of course we need to return a range instead, and
I think we should return exactly the range above: all elements strictly
less than x.
Then upperBound would return all elements strictly greater than x.
Finally equalRange would return all elements neither less nor greater than
x.
The beauty of it is that the three ranges are disjoint and cover the map
completely.
----------------------
Note that dcollections uses slice notation instead of
upperBound/lowerBound, which I find vastly more intuitive. But they are
not as powerful.
-Steve
