• Ellery Newcomer (47/47) Feb 19 2012 Is it just me or are lowerBound and upperBound really unintuitively
• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (30/80) Feb 19 2012 Note: I have written the following by ignoring the RedBlackTree in the
• Steven Schveighoffer (39/41) Mar 05 2012 It's not just you. Quoting from one of my proposed implementation of

Ellery Newcomer <ellery-newcomer utulsa.edu> writes:

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?

=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:

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

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

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