Вставка нескольких элементов в известные места в векторе

Цель

В векторе x, Я хотел бы вставить элементы вектора values по индексам, хранящимся в векторе positions. Обратите внимание, что вектор positions не сортируется.

Например, из следующего ввода

std::vector<char> x = {'H','e','l','l','W','o','l','d'};
std::vector<char> values = {'r','o'};
std::vector<size_t> positions = {6,4};

Я ожидаю следующего вывода

std::vector<char> x = {'H','e','l','l','o','W','o','r','l','d'};

Моя реализация

Идея в первую очередь сортировать positions и переупорядочить values соответственно. Затем я изменяю размер вектора x так что он может приветствовать новые элементы. Наконец, я перебираю вектор x от его последнего индекса до самой нижней позиции вставки, спрашивая на каждом шаге, какой элемент должен быть туда и перемещать этот элемент (происходит ли он из более низкого индекса в x из от values).

#include <iostream>
#include <vector>
#include <numeric>

//// Print a vector
template <typename T>
void print(std::vector<T>& x)
{
    for (auto& e : x) std::cout << e << " ";
    std::cout << "n";
}

//// Return the indices to inform on how to sort the inputted vector
template <typename T>
std::vector<uint32_t> sort_indices(const std::vector<T> &v)
{

  // initialize original index locations
  std::vector<uint32_t> idx(v.size());
  std::iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  std::sort(idx.begin(), idx.end(),
       [&v](uint32_t i1, uint32_t i2) {return v[i1] < v[i2];});

  return idx;
}

//// reorder vector based on indices
template <typename T>
void reorder(std::vector<T>& v, std::vector<uint32_t>& order)  
{   
    auto v2 = v;
    for (uint32_t i = 0 ; i < v.size() ; i++)
    {
        v[i] = v2[order[i]];
    }
}


//// Insert multiple elements at specified positions into vector
template<typename T>
void insertAtPositions(std::vector<T>& x, std::vector<T>& values, std::vector<size_t>& positions)
{
  // assert values and positions are the same size
  assert(values.size() == positions.size());

  // Special case - values is empty
  if (values.size() == 0) return;

  // sort the values and the positions where those values should be inserted
  auto indices = sort_indices(positions);
  reorder(positions, indices);
  reorder(values, indices);

  // Special case - x is empty
  if (x.size() == 0)
  {
      x.swap(values);
      return;
  }

  // Allocate memory to x
  x.resize(x.size() + values.size());

  
  // Move things to make room for insertions and insert
  int pos_index = positions.size()-1;
  for (size_t i = x.size()-1 ; pos_index >= 0 ; --i)
  {
    if (i == positions[pos_index] + pos_index)
    {
      // A new value should go at index i
      x[i] = std::move(values[pos_index]);
      --pos_index;
    } else
    {
      // The value from index 'i-pos_index-1' must go to index 'i'
      x[i] = std::move(x[i-pos_index-1]);
    }
  }
}


int main()
{
  std::vector<char> x = {'H','e','l','l','W','o','l','d'};
  std::vector<char> values = {'r','o'};
  std::vector<size_t> positions = {6,4};
  
  print(x);
  insertAtPositions(x,values,positions);
  print(x);
  
}

Он печатает, как и ожидалось

H e l l W o l d 
H e l l o W o r l d 

Есть ли более быстрые (или лучшие в каком-то другом отношении) реализации?

Обратите внимание, что

1. на практике, xразмер обычно составляет от 0 до 10 ^ 7 и positions (и values) размер обычно составляет от 0 до 50.
2. У меня есть веские причины использовать вектор, а не двухстороннюю очередь, несмотря на эту вставку.

• Нам нужно включить <algorithm> для std::sort и <cassert> для assert.

• void print(std::vector<T> &x): Поскольку мы не изменяем вектор, это должно занять const& (и используйте const& внутри цикла for на основе диапазона).

• void reorder(std::vector<T> &v, std::vector<uint32_t> &order): Очередной раз, order может быть const&.

• Мы должны использовать std::size_t для индексов в вектор, а не uint32_t или же size_t.

• Если нам нужен подписанный тип для работы с различиями индексов, мы должны использовать std::ptrdiff_t, нет int. Возможно, будет проще посчитать вперед, а затем вычислить нужные нам индексы внутри цикла.

• Нет смысла в std::moveing a char.

Вместо того, чтобы вставлять элементы на место, мы можем создать новый вектор и скопировать элементы, выбирая из соответствующего источника для каждого индекса. Это не требует больше памяти, чем вызов x.resize().

например:

{
    std::vector<char> x = {'H', 'e', 'l', 'l', 'W', 'o', 'l', 'd'};
    std::vector<char> values = {'r', 'o'};
    std::vector<size_t> positions = {6, 4};

    auto indices = sort_indices(positions);
    reorder(positions, indices);
    reorder(values, indices);

    auto size = x.size() + values.size();

    auto y = std::vector<char>();
    y.reserve(size);

    auto v = std::size_t{ 0 }; // index into x
    auto p = std::size_t{ 0 }; // index into positions / values

    for (auto i = std::size_t{ 0 }; i != size; ) // index into y
    {
        if (v == positions[p])
        {
            y.push_back(values[p]);
            ++p;
            ++i;
        }
        else
        {
            y.push_back(x[v]);
            ++v;
            ++i;
        }
    }

    print(y);
}

Поскольку мы ожидаем x вектор быть намного больше, чем values для вставки, мы могли бы скопировать большие диапазоны из x в else ветка выше, что-то вроде:

            auto beg = v;
            auto end = (p == positions.size() ? x.size() : positions[p]);

            y.insert(y.end(), x.begin() + beg, x.begin() + end);
            v = end;
            i += (beg - end);

(Предупреждение: код не протестирован должным образом).