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.

Answer 3

This is what I probably would do:

typedef ::std::vector<int> MyList;
typedef MyList::iterator MyListIter;

MyList data;

// ... fill data ...

const int searchValue = 2;
const int addValue = 3;

// Find first occurence of searched value
MyListIter iter = ::std::find(data.begin(), data.end(), searchValue);

while(iter != data.end())
{
    // We want to add our value after searched one
    ++iter;

    // Insert value and return iterator pointing to the inserted position
    // (original iterator is invalid now).
    iter = data.insert(iter, addValue);

    // This is needed only if we want to be sure that out value won't be used
    // - for example if searchValue == addValue is true, code would create
    // infinite loop.
    ++iter;

    // Search for next value.
    iter = ::std::find(iter, data.end(), searchValue);
}

but as you can see, I couldn't avoid the incrementation you mentioned. But I don't think that would be bad thing: I would put this code to separate functions (probably in some kind of "core/utils" module) and - of course - implement this function as template, so I would write it only once - only once worrying about incrementing value is IMHO acceptable. Very acceptable.

template <class ValueType>
void insertAfter(::std::vector<ValueType> &io_data,
                 const ValueType &i_searchValue,
                 const ValueType &i_insertAfterValue);

or even better (IMHO)

template <class ListType, class ValueType>
void insertAfter(ListType &io_data,
                 const ValueType &i_searchValue,
                 const ValueType &i_insertAfterValue);

EDIT:

well, I would solve problem little different way: first count number of the searched value occurrence (preferably store in some kind of cache which can be kept and used repeatably) so I could prepare array before (only one allocation) and used memcpy to move original values (for types like int only, of course) or memmove (if the vector allocated size is sufficient already).

Answer 4

In place, O(1) additional memory and O(n) time (Live at Coliru):

template <typename T, typename A>
void do_thing(std::vector<T, A>& vec, T target, T inserted) {
    using std::swap;

    typedef typename std::vector<T, A>::size_type size_t;
    const size_t occurrences = std::count(vec.begin(), vec.end(), target);
    if (occurrences == 0) return;

    const size_t original_size = vec.size();
    vec.resize(original_size + occurrences, inserted);

    for(size_t i = original_size - 1, end = i + occurrences; i > 0; --i, --end) {
        if (vec[i] == target) {
            --end;
        }
        swap(vec[i], vec[end]);
    }
}