Is it just me or are lowerBound and upperBound really unintuitively named? From DDOC:

c.lowerBound(v)   Returns a range of all elements strictly less than v
c.upperBound(v)   Returns a range of all elements strictly greater than v.

So c.lowerBound(v) will return a range for which v is the .. upper bound noninclusive. And c.upperBound(v) the lower bound noninclusive.


Over in the STL, we have set::lower_bound and set::upper_bound, but these are different in two ways

1) they return iterators
1.a) lower_bound is kinda meant to be a starting iterator, upper_bound is kinda meant to be a ending iterator. kinda. Anyways:
c.lower_bound(v)  points to the first element less than or equal to v
c.upper_bound(v)  points to the first element strictly greater than v

So iterators are like these half-ranges, they aren't really useful by themselves but you can pair them up and stuff.

Consider the ordered set C = {1,2,3,4,5}.

if you want the range [3,inf) intersect C, over in the STL you'd use the pair (C.lower_bound(3), C.end()). Here, I guess you'd use C.upperBound(2). Similarly,

(-inf, 3) -> (C.begin(), C.lower_bound(3))   vs   C.lowerBound(3)
(-inf, 3] -> (C.begin(), C.upper_bound(3))   vs   C.lowerBound(4)
(3, inf)  -> (C.upper_bound(3), C.end())     vs   C.upperBound(3)
[3, inf)  -> (C.lower_bound(3), C.end())     vs   C.upperBound(4)  // yeah, well I couldn't find it in the text above quickly enough
[2, 4)    -> (C.lower_bound(2), C.lower_bound(4))    vs     ???
(2, 4)    -> (C.upper_bound(2), C.lower_bound(4))    vs     ???
[2, 4]    -> (C.lower_bound(2), C.upper_bound(4))    vs     ???
(2, 4]    -> (C.upper_bound(2), C.upper_bound(4))    vs     ???

So now two things emerge that I wasn't exactly going for when I started this rumination, but hey:

1) lowerBound and upperBound are actually not especially useful as they capture only a small subset of the functionality of lower_bound and upper_bound

2) lower_bound and upper_bound are versatile, but rather unreadable

3) D can do better than this.

Suppose instead of having lowerBound and upperBound we have

bound!(string boundary = "[")(one_end)  // possible: "[","(","]",")"
bounds!(string boundaries = "[]")(lower, upper) // kinda like std.random.uniform

Anyways, back to the topic at hand.

I don't see much if any correlation between STL's lower bound and upper bound and std.container's, and I don't see much use of the current names/semantics except for confusing people, so I think at the very least the names should be changed to something like

belowBound
aboveBound


Am I missing anything?

Note: I have written the following by ignoring the RedBlackTree in the title. I have been thinking about std.range.lowerBound, but I think they have the same semantics.

On 02/19/2012 01:44 PM, Ellery Newcomer wrote:
> Is it just me or are lowerBound and upperBound really unintuitively
> named? From DDOC:

Perhaps. Though I have grown to appreciate historical accidents in general. They give character to everything. :)

> c.lowerBound(v) Returns a range of all elements strictly less than v
> c.upperBound(v) Returns a range of all elements strictly greater than v.
>
> So c.lowerBound(v) will return a range for which v is the .. upper bound
> noninclusive. And c.upperBound(v) the lower bound noninclusive.
>
>
> Over in the STL, we have set::lower_bound and set::upper_bound, but
> these are different in two ways
>
> 1) they return iterators
> 1.a) lower_bound is kinda meant to be a starting iterator,

If we go with the convention of open-ended ranges, lower_bound can be seen as the end iterator. So, the pair of c.begin() and c.lower_bound() is the equivalent of C.lowerBound().

> upper_bound
> is kinda meant to be a ending iterator. kinda.

With the same logic above, the pair of c.upper_bound() and c.end() make another range where c.upper_bound() is included in the range. And that is the equivalent of C.upperBound()

That's how I have been seeing lower_bound and upper_bound.

> Anyways:
> c.lower_bound(v) points to the first element less than or equal to v
> c.upper_bound(v) points to the first element strictly greater than v
>
> So iterators are like these half-ranges, they aren't really useful by
> themselves but you can pair them up and stuff.
>
> Consider the ordered set C = {1,2,3,4,5}.
>
> if you want the range [3,inf) intersect C, over in the STL you'd use the
> pair (C.lower_bound(3), C.end()).

Personally, I've never thought of lower_bound() as the beginning of a range.

> Here, I guess you'd use
> C.upperBound(2). Similarly,
>
> (-inf, 3) -> (C.begin(), C.lower_bound(3)) vs C.lowerBound(3)
> (-inf, 3] -> (C.begin(), C.upper_bound(3)) vs C.lowerBound(4)
> (3, inf) -> (C.upper_bound(3), C.end()) vs C.upperBound(3)
> [3, inf) -> (C.lower_bound(3), C.end()) vs C.upperBound(4) // yeah, well
> I couldn't find it in the text above quickly enough
> [2, 4) -> (C.lower_bound(2), C.lower_bound(4)) vs ???
> (2, 4) -> (C.upper_bound(2), C.lower_bound(4)) vs ???
> [2, 4] -> (C.lower_bound(2), C.upper_bound(4)) vs ???
> (2, 4] -> (C.upper_bound(2), C.upper_bound(4)) vs ???
>
> So now two things emerge that I wasn't exactly going for when I started
> this rumination, but hey:
>
> 1) lowerBound and upperBound are actually not especially useful as they
> capture only a small subset of the functionality of lower_bound and
> upper_bound

Iterators look more capable because they are a lower-lever abstraction. But I don't think closed-ended ranges are natural to C++ or D programmers anyway, so we should exclude those cases.

Phobos has other ranges that provide what lowerBound() and C.upperBound() seemingly lack. For example std.range.trisect() is very useful.

> 2) lower_bound and upper_bound are versatile, but rather unreadable

I will again refer to Andrei's article:

  http://www.informit.com/articles/printerfriendly.aspx?p=1407357

Andrei acknowledges the power of iterators under the heading "Weaknesses" and points at some range solutions.

> 3) D can do better than this.
>
> Suppose instead of having lowerBound and upperBound we have
>
> bound!(string boundary = "[")(one_end) // possible: "[","(","]",")"
> bounds!(string boundaries = "[]")(lower, upper) // kinda like
> std.random.uniform

Yes, that looks powerful but open-ended'ness is the norm. (Except, when we really want to include the T.max value. :-/)

> Anyways, back to the topic at hand.
>
> I don't see much if any correlation between STL's lower bound and upper
> bound and std.container's, and I don't see much use of the current
> names/semantics except for confusing people, so I think at the very
> least the names should be changed to something like
>
> belowBound
> aboveBound
>
>
> Am I missing anything?

They are valid points but I think it is because you are seeing lower_bound and upper_bound more flexible than they are intended use. At least that's always been my understanding.

Ali

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