How to Insert Several Elements in a Vector (With No Memory Errors)
Inserting elements in a vector sounds like the most basic use case we can think of when it comes to using collections in C++.
Nevertheless, this is a complex topic in itself, because std::vector offers various ways to insert several elements. Choosing the most appropriate depending on your exact use case allows to write more expressive code. And misusing the interface of std::vector can lead to memory errors.
Let’s navigate the various ways to insert several elements in a vector in a safe way, so that you can choose the one that fits best for your code.
Inserting several values from a range
The simplest case is when the elements you want to insert in a vector are themselves part of a range, that is to say that they’re between two iterators.
In this case we can use the range insert in the destination vector:
auto const source = std::vector<int>{1, 2, 3, 4, 5};
auto destination = std::vector<int>{10, 20};
destination.insert(begin(destination) + 1, begin(source), end(source));
If we print the contents of destination we get:
10 1 2 3 4 5 20
Inserting in reverse order
If ever you’d like to insert the elements of the source in reverse order, the range insert function of vector is of no use here. We’ll see later that this is not the case for other use cases.
To insert in reverse order, we need to operate a reverse operation on the source, for example by using reverse iterators:
destination.insert(begin(destination) + 1, rbegin(source), rend(source));
As a result destination contains the following values:
10 5 4 3 2 1 20
Inserting several values one by one
Let’s now examine the use case of inserting several values but that don’t come from a range. That is to say, we’d like to insert them one by one.
In this case we need to be careful in order to insert them in the order we want (in order or in reverse order). Paradoxically, the code is slightly simpler to insert in reverse order, so let’s start with this case.
Inserting in reverse order
Here is the most simple code (I can think of) to insert several values in reverse order with standard C++:
auto v = std::vector<int>{10, 20};
v.insert(begin(v) + 1, 1);
v.insert(begin(v) + 1, 2);
v.insert(begin(v) + 1, 3);
v.insert(begin(v) + 1, 4);
v.insert(begin(v) + 1, 5);
It is interesting to note that, when glancing at it, this code may not look like it’s inserting in reverse order. Indeed, it seems to use the same code to insert 1, then 2, etc.
Of course when you run the code in you head you find that it inserts each new value at the same position as the previous one, which shifts forward the previously inserted values. But code that needs to be run in our head to be understood is not the most expressive code.
Another interesting point to note is that there is a repetition of the expression begin(v) + 1. And in general, we want to avoid duplicated logic in code.
So it may be tempting to replace this expression with an intermediary value:
auto v = std::vector<int>{10, 20};
auto const position = begin(v) + 1;
v.insert(position, 1);
v.insert(position, 2);
v.insert(position, 3);
v.insert(position, 4);
v.insert(position, 5);
But this code has a bug. Can you see it?
..
..
..
(leaving you a bit of time to find the bug for yourself)
…
…..
When we run this code, we get the following output:
double free or corruption (out)
This is a memory error.
The problem is that after adding some values to the vector, the vector needs to reallocate its elements to a location in memory where there is more space in order to store all the values. This implies that the position iterator, pointing into the original location of the vector, becomes invalid. Using it results in undefined behaviour, leading to the memory error we see here.
Now would this error happen in real life? It certainly happened to me, when designing the insert pipe in the pipes library! This is what motivated me in the first place to analyse the various use cases of insertion in a vector and write this article.
So do we have the repeat the begin(v) + 1 expression?
Another way is to take advantage of the returned value of the insert member function of std::vector. insert returns the position of the inserted element. And this is a valid iterator, even if the vector reallocated its storage:
auto v = std::vector<int>{10, 20};
auto position = begin(v) + 1;
position = v.insert(position, 1);
position = v.insert(position, 2);
position = v.insert(position, 3);
position = v.insert(position, 4);
v.insert(position, 5);
Is this better than begin(v) + 1? It reduced code duplication, but it increased code in total. I’m not sure which one is the best alternative here. It’s not that important anyway, the most important point here is to avoid the above memory error.
Inserting in order
To insert several individual values in order in a vector, we can use the insert interface this way:
auto v = std::vector<int>{10, 20};
v.insert(begin(v) + 1, 1);
v.insert(begin(v) + 2, 2);
v.insert(begin(v) + 3, 3);
v.insert(begin(v) + 4, 4);
v.insert(begin(v) + 5, 5);
If we print the collection we get this:
10 1 2 3 4 5 20
This code is less robust than its counterpart to insert in reverse order that repeated begin(v) + 1. Indeed, if we need to change the code and add a new value between the existing ones, we have to remember to update the positions of all the other insertions down the line:
auto v = std::vector<int>{10, 20};
v.insert(begin(v) + 1, 1);
v.insert(begin(v) + 2, 2);
v.insert(begin(v) + 3, 42);
v.insert(begin(v) + 4, 3);
v.insert(begin(v) + 5, 4);
v.insert(begin(v) + 6, 5);
There is coupling between the lines of code, and coupling leads to all sorts of problems.
How can we rewrite this code to make the addition of an intermediary line more straightforward?
Unfortunately I don’t know an elegant way here. The only solution I can see is to adapt the code that used the return value of insert. The adaptation consists in inserting the new value after the position returned by the previous insertion:
auto v = std::vector<int>{10, 20};
auto position = begin(v) + 1;
position = v.insert(position, 1);
position = v.insert(std::next(position), 2);
position = v.insert(std::next(position), 3);
position = v.insert(std::next(position), 4);
v.insert(std::next(position), 5);
Then to add a new value we can just add a new line:
auto v = std::vector<int>{10, 20};
auto position = begin(v) + 1;
position = v.insert(position, 1);
position = v.insert(std::next(position), 2);
position = v.insert(std::next(position), 42);
position = v.insert(std::next(position), 3);
position = v.insert(std::next(position), 4);
v.insert(std::next(position), 5);
But, this doesn’t look like welcoming code! If you can see a better solution, I’d be happy if you let me know in the comments section.
In any case, what is certain is that it is beneficial to know well the interface of std::vector, especially since this is the most commonly used container in C++. The better you know it, the easier you can write expressive and correct code for each of the use cases you encounter.
You will also like
- Inserting several elements into an STL container efficiently
- Lower and Upper Bound Insert Iterators
- How to Check If an Inserted Object Was Already in a Map (with Expressive Code)
- Overview of std::map’s Insertion / Emplacement Methods in C++17
Share this post!
