§ C++ lower_bound, upper_bound API

I never remember what precisely lower_bound returns, so this is me collecting this information in a way that makes sense to me. The API docs say
Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.
  • So lower_bound(first, last, bound) it finds the leftmost location l in [first..last) such that as[l] >= bound.
  • See that it can be equal to the value bound.
In contrast, upper_bound says:
Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.
  • So upper_bound(first, last, bound) it finds the leftmost location l in [first..last) such that as[l] > bound.

§ Pictorially

If we have a range: 
<<<<<<< ======= >>>>>>>>
        |     |
        L     R
  • The < values are less than bound, = values are equal to bound, and > values are greater than bound, then lower_bound and upper_bound return iterators to represent the = range [L, R] in half-open form.
  • So we will have [lower_bound, upper_bound) = [L, R]. This matches the C++ API where everything uses half-open intervals. 
<<<<<<< ======= >>>>>>>>
        L     R |
        lower   upper

§ Traversals

  • [L,H][L, H]: loop as for(auto it = lowerbound(l); it < upperbound(h); ++it) {}. This works since upperbound(h) will find first index > h, so we include all =h.
  • [L,H)[L, H): loop as for(auto it = lowerbound(l); it <= lowerbound(h); ++it) {}. This works lowerbound(h) first first index >= h, so we don't include any =h.
  • (L,H](L, H]: use for(auto it = upperbound(l); it <= upperbound(h); ++it) {}. upperbound(l) finds first index >l, so we ignore values =l.
  • (L,H)(L, H): use for(auto it = upperbound(l); it < lowerbound(h); ++it) {}.
How to think about which one we want? This about it as lowerbound shifts iterators towards the left, and upperbound shifts iterators to right.
  • For [L, we want to shift beginning leftwards, so lowerbound(L).
  • For (L, we want to shift beginning rightwards, so upperbound(L).
  • For H], we want to shift ending rightwards, so upperbound(H).
  • For H), we want to shift ending leftwards, so lowerbound(H).

§ equal_range

  • To unify the above description, one can simply use std::equal_range(fst, last, val) which returns the half-open interval [l, r) where the array has value val. This is equivalent to returning a pair of lower_bound, upper_bound.