How the STL inserter iterator really works

The inserter iterators such as std::back_inserter and std::inserter are important components in the STL that participate in letting us improve the expressiveness of our code.

Here we delve into std::inserter. We’ll start with a basic question concerning how it can work, have a peek at the inside, and answer that question. This will make us better understand what it really does.

Special thanks to my colleague Gabriel Fournier with whom we scratched our heads dangerously hard over this, and who’s always a source of valuable feedbacks and ideas.

How can the thing work?

Quoting cppreference.com, the object generated by std::inserter “inserts elements into a container for which it was constructed, at the position pointed to by the supplied iterator”. Here is how it looks like in code:

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> newElements = {7, 8, 9, 10};

std::copy(begin(newElements), end(newElements), std::inserter(v, v.end()));

for (int i : v) std::cout << i << ' ';

The above code aims at appending the elements in newElements at the end of v.

(Actually std::inserter really becomes useful for more complex uses. For such a basic use as the one above you’d rather blast the elements at the end using a range insertion method on vector. But here let’s consider the simplest usage to better demonstrate how std::inserter works. And if you want to know how to to make efficient insertions, you can read Inserting several elements into an STL container efficiently).

But how can this work? std::inserter takes a position inside the container, and make repeated insertions. So, at some point we would expect the buffer inside the vector to overgrow, causing an reallocation and an invalidation of the position passed to std::inserter, right? And even if the buffer was large enough so as not to be reallocated, repeatedly inserting at a position should produce the elements in reverse order, shouldn’t it?

If these suspicions turn out to be founded, then we would have a spectacular bug in the STL. Quick, let’s test this and see if we got this right. Compile, execute, and the output is…

1 2 3 4 5 6 7 8 9 10

Yeah well, the STL works. Duh. Now the question is: how?

What it looks like it does

Let’s try to simulate the behaviour we were assuming std::inserter had. We take a position inside a container, and repeatedly insert elements at this position:

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> newElements = {7, 8, 9, 10};

auto position = v.end();
for (int i : newElements) v.insert(position, i);

for (int i : v) std::cout << i << ' ';

The following code outputs:

Segmentation fault

Just as we expected. The vector’s buffer is reallocated and position is invalidated. The next insertion through it leads to undefined behaviour.

Let’s try to work around this by reserving buffer space in advance:

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> newElements = {7, 8, 9, 10};

v.reserve(10);
auto position = v.end();
for (int i : newElements) v.insert(position, i);

for (int i : v) std::cout << i << ' ';

With this the program now longer crashes, but we get the following output:

1 2 3 4 5 6 10 9 8 7

The inserted elements are in reverse order because, as we predicted, repeatedly inserting at the same position pushes the last insertions to the right every time.

What it actually does

So how does std::inserter do to insert the elements in the right order without crashing? How does it just do the right thing?

Let’s look into an implementation of the STL to understand what’s going on. Here is the code that actually performs the insertion of an element inside the container:

_Self& operator=(const typename _Container::value_type& __val) {
  _M_iter = container->insert(_M_iter, __val);
  ++_M_iter;
  return *this;
}

_M_iter is the position that was passed to std::inserter. As you can see, there is more than just an insertion:

• the position is refreshed by using the one returned by the insert method. insert returns the position of the inserted element. This ensures to always keep _M_iter in the vector’s current buffer, even if it was just reallocated.

• the position is incremented. This way each inserted element is positioned right after the previous one. This ensures to have the elements inserted in the right order.

So here was std::inserter mystified and then demystified. Hope you appreciated the little journey, and learned a thing or two along the way. We sure did.

Related articles:

• sorted_inserter: smart iterator for inserting into a sorted container in C++
• map_aggregator: smart iterator for aggregating data into a map in C++

Don't want to miss out ? Follow:   
Share this post!