Searching and inserting in a sorted array with std::lower_bound

Once a range of data has been sorted, it becomes possible to search within that data using binary search, as opposed to the slower linear search. The standard algorithm that implements binary search is called std::lower_bound(a,b,v):

    template<class FwdIt, class T, class C>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& value, C lessthan)
    {
      using DiffT = typename std::iterator_traits<FwdIt>::difference_type;
      FwdIt it;
      DiffT count = std::distance(first, last);

      while (count > 0) {
        DiffT step = count / 2;
        it = first;
        std::advance(it, step);
        if (lessthan(*it, value)) {
          ++it;
          first = it;
          count -= step + 1;
        } else {
          count = step;
        }
      }
      return first;
    }

    template<class FwdIt, class T>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& value) 
    {
      return std::lower_bound(first, last, value, std::less<>{});
    }

This function returns an iterator to the first element in the range that is not less than the given value v. If there is an instance of the value v already in the range, then the returned iterator will point at it (in fact, it will point at the first such value in the range). If there's no instance already in the range, then the returned iterator will point at the place where v should go.

We can use the return value of lower_bound as the input to vector::insert in order to insert v into the proper place in a sorted vector while preserving its sorted order:

    std::vector<int> vec = {3, 7};
    for (int value : {1, 5, 9}) {
      // Find the appropriate insertion point...
      auto it = std::lower_bound(vec.begin(), vec.end(), value);
      // ...and insert our value there.
      vec.insert(it, value);
    }
    // The vector has remained sorted.
    assert((vec == std::vector{1, 3, 5, 7, 9}));

The similar function std::upper_bound(a,b,v) returns an iterator to the first element in the range that is greater than the given value v. If v is not in the given range, then std::lower_bound and std::upper_bound will have the same return value. But if v is present in the range, then lower_bound will return an iterator pointing to the first instance of v in the range and upper_bound will return an iterator pointing "one past" the last instance of v in the range. In other words, using the two functions together will give you a half-open range [lower, upper) containing nothing but instances of the value v:

    std::vector<int> vec = {2, 3, 3, 3, 4};
    auto lower = std::lower_bound(vec.begin(), vec.end(), 3);

    // First approach:
    // upper_bound's interface is identical to lower_bound's.
    auto upper = std::upper_bound(vec.begin(), vec.end(), 3);
 
    // Second approach:
    // We don't need to binary-search the whole array the second time.
    auto upper2 = std::upper_bound(lower, vec.end(), 3);
    assert(upper2 == upper);

    // Third approach:
    // Linear scan from the lower bound might well be faster
    // than binary search if our total range is really big.
    auto upper3 = std::find_if(lower, vec.end(), [](int v) {
      return v != 3;
    });
    assert(upper3 == upper);

    // No matter which approach we take, this is what we end up with.
    assert(*lower >= 3);
    assert(*upper > 3);
    assert(std::all_of(lower, upper, [](int v) { return v == 3; }));

This handles searching and inserting values in a sorted array. But what about deletion?