c++ – Inserting multiple elements at known locations in a vector

Goal

In the vector x, I would like to insert the elements of the vector values at indices stored in vector positions. Note that the vector positions is not sorted.

For example, from the following input

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

I expect the following output

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

My implementation

The idea is first to sort positions and reorder values accordingly. Then, I resize the vector x so that it can welcome the new elements. Finally, I iterate through the vector x from its last index to the lowest position of insertion by asking at each step what element should go there and move this element (whether it comes from a lower index in x of from 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);
  
}

It prints, as expected

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

Are there faster (or better in some other respect) implementations?

Note that

  1. in practice, x‘s size typically ranges from 0 to 10^7 and positions (and values)’s size typically ranges from 0 to 50.
  2. I have good reasons for using a vector and not a deque despite this insertion.