R@M3\$H.NBlog

lower_bound ans upper_bound

20 April, 2013 - 1 min read

• Lower bound: first element that is greater-or-equal.
• Upper bound: first element that is strictly greater.

Example:

``````+- lb(2) == ub(2)           +- lb(6)
|        == begin()         |   +- ub(6) == end()
V                           V   V
+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 5 | 6 |
+---+---+---+---+---+---+---+---+
^               ^           ^
|               |           |
+- lb(4)        +- ub(4)    +- lb(9) = ub(9) == end()

|- eq-range(4) -|``````

As you can see, the half-open equal-range for n is [lb(n), ub(n)).

Note that both bounds give you meaningful insertion locations for an element of the desired value so that the ordering is maintained, but `lower_bound` has the distinguishing feature that if the element already exists, then you get an iterator which actually points to that element. Thus you can use `lower_bound`on an ordered range to implement your own unique-membership or multiple-membership container.

``````void insert(Container &amp; c, T const &amp; t)
{
auto it = std::lower_bound(c.begin(), c.end(), t);

// if unique container:
if (it != c.end() &amp;&amp; *it == t) { /* error, element exists! */ return; }

c.insert(it, t);
}``````