RedBlackTree.lowerBound

[Steven Schveighoffer]

On Sun, 19 Feb 2012 16:44:05 -0500, Ellery Newcomer  
<ellery-newcomer at utulsa.edu> 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