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_boundon 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);
}