Вставить несколько значений в вектор

Вот что я бы, вероятно, сделал:

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);

Поместите вызов, чтобы зарезервировать там, если хотите. Вы знаете, что вам нужно место как минимум для original.size() элементов. Вы также можете выполнить начальную итерацию по вектору (или использовать std::count), чтобы определить точное количество элементов для резервирования, но без тестирования я не знаю, улучшит ли это производительность.

Я предлагаю решение, которое работает на месте и за O(n) памяти и O(2n) времени. Вместо O(n^2) по времени решением, предложенным Лаэтнесом, и O(2n) по памяти решением, предложенным Бенджамином.

// 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;
}

Этот алгоритм может содержать ошибки, но идея состоит в том, чтобы скопировать каждый элемент только один раз:

1. Сначала подсчитайте, сколько элементов нам нужно вставить.
2. Во-вторых, просматривая данные с конца и перемещая каждый элемент в новый конец.

Вот что я, вероятно, сделал бы:

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);
}

но, как видите, я не мог избежать упомянутого вами приращения. Но я не думаю, что это было бы плохо: я бы поместил этот код в отдельные функции (вероятно, в какой-то модуль «core/utils») и, конечно же, реализовал бы эту функцию как шаблон, поэтому я бы написал только один раз - ИМХО приемлемо беспокоиться об увеличении значения только один раз. Очень приемлемо.

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

а то и лучше (ИМХО)

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

ИЗМЕНИТЬ:

ну, я бы решил проблему немного по-другому: сначала подсчитать количество вхождений искомого значения (предпочтительно хранить в каком-то кеше, который можно хранить и использовать многократно), чтобы я мог подготовить массив раньше (только одно выделение) и использовать memcpy для перемещения исходные значения (конечно, только для таких типов, как int) или memmove (если размер выделенного вектора уже достаточен).

Вместо этого O(1) дополнительной памяти и O(n) времени ):

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]);
    }
}