Lower and Upper Bound Insert Iterators

Published December 27, 2019

This is a guest post by Anton Vodostoev. Anton is a C++ developer and follower of Fluent C++.

I liked the idea of creating different types of smart iterators when reading the articles “About Smart Output Iterators” by Jonathan. One of them suggested me an idea I wanted to talk about.

The problem

Imagine we have a sequence container (such as vector, deque, list, string, …any other STL-compatible custom container) that has already been sorted. Operating on sorted containers is quite frequent in day-to-day code. And imagine we have some objects to be added to the container. It may be one or several objects or a range (a container) of objects (in general case, unsorted). It’s important that after all these insertions our container should remain sorted.

Let assume that the target (sorted) container is a big one while the source container is a little one.

std::vector source{ 7, 1, 5 };
std::vector target{ 1, 2, 3, 4, 5, 6, 8, ... };

There are some variations below on how it can be implemented with existing language tools (some things such as reserve or references were omitted).

Implementation #1

std::copy(begin(source), end(source), back_inserter(target));
std::sort(begin(target), end(target));

std::copy broke the original order until std::sort,
std::sort does extra work to sort the almost sorted container.

Implementation #2

std::sort(begin(source), end(source));
std::vector<int> new_target;

std::merge(begin(target), end(target),
           begin(source), end(source),
           std::back_inserter(new_target));

std::sort does not work if the source container is const,
we need an additional container and we have a name to think about for it (new_target), and we need additional memory,
elements from the first range always precede the elements from the second range.

Implementation #3

std::sort(begin(source), end(source));
auto border_it = target.insert(end(target), begin(source), end(source));
std::inplace_merge(begin(target), border_it, end(target));

std::sort does not work if the source container is const,
elements from the first range always precede the elements from the second range.

Implementation #4

for (auto elem : source)
{
    auto it = std::lower_bound(begin(target), end(target), elem);
    target.insert(it, elem);
}

this code relies on a for loop and not STL algorithms

Isn’t it a little bit wordy to implement “insert some objects to already sorted container in a way that keeps its ordering”? And what if we have a single object to insert? For this case only the implementation #4 loop’s body is suitable.

All these implementations are about the how, or said differently, at a too low level of abstraction. It messes up the business logic of the surrounding code. So the programmer needs to read out our code to find out what’s happening.

It would be great to hide this details under the hood and keep coding at a higher level of abstraction.

Expressive implementation (using a smart iterator)

Here is another approach to solve this problem:

std::copy(begin(source), end(source), lower_bound_inserter(target));

There is no unnecessary word in this code (except, maybe, using begin/end iterators instead of range 🙂 ). The smart iterator gives us expressiveness to write what we want and relieves us from writing how we are going to do that.

How this works

lower_bound_inserter is not itself an iterator, but rather a function that generates an iterator of type lower_bound_insert_iterator. This iterator’s interface and peculiarities of its implementation are almost exactly the same as they are for std::back_insert_iterator (produced by the std::back_inserter function).

All the magic happens when you assign through it. It calls a std::lower_bound to find an appropriate position and then calls the container type’s insert function:

lower_bound_insert_iterator& operator=(const typename Container::value_type& value)
{
    auto it = std::lower_bound(container_->begin(), container_->end(), value);
    container_->insert(it, value);
    return *this;
}

About naming

First time, I thought about sorted_inserter, but it may make a difference if we need lower or upper bound to use. So I decided to add this kind of implementation detail to smart iterator’s type name. It should be OK for C++ programmers because C++ programmers are supposed to be familiar with the meaning of lower/upper bound.

So we have lower/upper_bound_insert_iterator and lower/upper_bound_inserter function that produces it.

Different kinds of ordering

Since as std::sort can be customized with a compare-function that says if two objects are “sorted” we need to provide a possibility to configure our smart iterator with a predicate to be used by lower/upper_bound.

The interesting challenge I have encountered after adding a predicate into the class is that with a lambda predicate, the iterator stops being copy-assignable (with operator=) because lambda-functions, which are usually the tools of choice as a predicate, are not copy-assignable. So we need to explicitly provide a copy-assignment operator to our iterator.

How to do that?

First, I thought of allocating the predicate dynamically in iterator constructor’s list of initializations holding raw pointer to that allocated predicate. Then I thought I could simply call the predicate’s destructor and construct it with placement new. Then I found out that std::optional::emplace does something like that.

And then I found this assignable-helper that uses std::optional under the hood that seems to be the best choice to solve the problem. It also relieves us from providing a copy-assignment operator explicitly.

As a result, to add elements to a descending target container, we could write something like this:

std::copy(begin(source), end(source), lower_bound_inserter(target, std::greater{});

To go further

Sometimes we have sorted container of unique elements. For such kind of containers we could implement sorted_unique_inserter that uses lower_bound and checks if to-be-inserted element was found or not. If not, it could insert the new element.

What do you think of such components to insert values in sorted containers?

Here you can find a draft of lower_bound_insert_iterator and sorted_unique_insert_iterator implementations.