Insert multiple values into vector

Question

I have a std::vector<T> variable. I also have two variables of type T, the first of which represents the value in the vector after which I am to insert, while the second represents the value to insert.

So lets say I have this container: 1,2,1,1,2,2

And the two values are 2 and 3 with respect to their definitions above. Then I wish to write a function which will update the container to instead contain:

1,2,3,1,1,2,3,2,3

I am using c++98 and boost. What std or boost functions might I use to implement this function?

Iterating over the vector and using std::insert is one way, but it gets messy when one realizes that you need to remember to hop over the value you just inserted.

Answer 1

This is what I would probably do:

vector<T> copy;
for (vector<T>::iterator i=original.begin(); i!=original.end(); ++i)
{
    copy.push_back(*i);
    if (*i == first)
        copy.push_back(second);
}
original.swap(copy);

Put a call to reserve in there if you want. You know you need room for at least original.size() elements. You could also do an initial iteraton over the vector (or use std::count) to determine the exact amount of elements to reserve, but without testing, I don't know whether that would improve performance.

Answer 2

I propose a solution that works in place and in O(n) in memory and O(2n) time. Instead of O(n^2) in time by the solution proposed by Laethnes and O(2n) in memory by the solution proposed by Benjamin.

// First pass, count elements equal to first.
std::size_t elems = std::count(data.begin(), data.end(), first);
// Resize so we'll add without reallocating the elements.
data.resize(data.size() + elems);
vector<T>::reverse_iterator end = data.rbegin() + elems;
// Iterate from the end. Move elements from the end to the new end (and so elements to insert will have some place).
for(vector<T>::reverse_iterator new_end = data.rbegin(); end != data.rend() && elems > 0; ++new_end,++end)
{
  // If the current element is the one we search, insert second first. (We iterate from the end).
  if(*end == first)
  {
    *new_end = second;
    ++new_end;
    --elems;
  }
  // Copy the data to the end.
  *new_end = *end;
}

This algorithm may be buggy but the idea is to copy only once each elements by:

1. Firstly count how much elements we'll need to insert.
2. Secondly by going though the data from the end and moving each elements to the new end.