What is the most painless approach to insert an element in the middle of the std::vector

Question

I want to be able to insert an element in the middle (or another location) in the vector without overwriting existing element.

Say my vector has 3 6 9 10 and I want to insert 7 right after 6. How should it be done without causing issues? It's very infrequent operation so efficiency is not a problem here. Also, at this point, I cannot switch to another container ( for example: std::list) that are good for insertions in the middle.

Will std::insert in vector do what I want? How?

thanks

Answer 1

There is vector::insert for this operation.

iterator insert(
   iterator _Where,
   const Type& _Val
);
void insert(
   iterator _Where,
   size_type _Count,
   const Type& _Val
);

Answer 2

You probably want to use your vector's insert member function.

Answer 3

I've edited the example to insert '7' directly after '6' as the question is more about inserting at a specific location than arbitrarily at the centre of the vector.

std::vector<int> v;
v.push_back(3);
v.push_back(6);
v.push_back(9);
v.push_back(10);
std::vector<int>::iterator insert_pos = std::find(v.begin(), v.end(), 6);
// only increment iterator if we've found the insertion point,
// otherwise insert at the end of the vector
if (insert_pos != v.end()) {
    ++insert_pos;
}
v.insert(insert_pos, 7);
// v now contains 3, 6, 7, 9, 10

Answer 4

Mash's example code is to the point (but be careful that it will insert where you're expecting with an odd size). Also, even though you said efficiency is not an issue, you might consider using vector's reserve() member function to avoid reallocation and hidden copying. ("Don't pessimize prematurely", as Sutter and Alexandrescu say in C++ Coding Standards.)

Answer 5

Using both vector::find and vector::insert, as per the above comments, gives the following code:

std::vector<int> v;
v.push_back(3);
v.push_back(6);
v.push_back(9);
v.push_back(10);
std::vector<int>::iterator pos = std::find(v.begin(),v.end(), 6);
v.insert(pos, 7);

Answer 6

If your vector is ordered, you can optimise the insert somewhat by avoiding the linear search:

std::vector<int> v;
v.push_back(3);
v.push_back(6);
v.push_back(9);
v.push_back(10);

std::insert(std::upper_bound(v.begin(), v.end(), 7), 7);