Inserting multiple elements at known locations in a vector

Question

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.

Answer 1

• We need to include <algorithm> for std::sort and <cassert> for assert.

• void print(std::vector<T> &x): Since we don't modify the vector, this should take a const& (and use a const& internally in the range-based for loop).

• void reorder(std::vector<T> &v, std::vector<uint32_t> &order): Again, order can be a const&.

• We should use std::size_t for indices into a vector, not uint32_t or size_t.

• If we need a signed type for dealing with index differences, we should use std::ptrdiff_t, not int. It might be easier to count forwards, and then calculate the indices we need inside the loop though.

• There's no point in std::moveing a char.

---

Rather than inserting elements in-place, we can create a new vector and copy the elements over, selecting from the appropriate source at each index. This doesn't require any more memory than calling x.resize().

e.g.:

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

Since we expect the x vector to be much larger than the values to be inserted, we could copy larger ranges from x in the else branch above, something like:

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

(Warning: code not properly tested).