Inserting into a vector of move-only type

Question

I have a std::vector<std::unique_ptr<T>>. I would like to insert some nullptrs into the middle of this vector. I tried vec.insert(first, size, nullptr) but this obviously doesn’t work because the nullptr needs to be copied. I could repeatedly call the singular version of insert but I was wondering if there was a more efficient way.

Rhetorician

Answer 1

"Efficient" is something to be measured. But if your desire is to shift the elements in one go instead of constantly moving them one item to the right, you can do it with std::rotate. Here's how

vec.resize(vec.size() + size); // Add the "null" pointers to the end.
// Obtain valid first after resize
std::rotate(first, vec.end() - size, vec.end());

Since the function of rotate is to make the middle iterator the "new first" of the range, while the iterator preceding it is the "new last", the above choice of iterators will shift the range of null pointers to their intended location (before first).

Furthermore, since you tagged C++17, you can also pass the standard algorithm an execution policy, and hopefully gain some parallelism to boot.

Eclectic

Beware that the resize() may invalidate first… in general, first should be determined after the resize() (or at least, reserve()). – Uppermost

That's a rotate: youtube.com/watch?v=W2tWOdzgXHA – Farika

Answer 2

You can put together your own iterator that creates default instances upon being dereferenced. These are prvalues, which enables construction of move-only types in a vector. Use counting instances of such an iterator to call std::vector::insert. Here's an example that's probably not standard compliant, but works.

template <class T>
class DefaultCtorInputIt {
   public:
      DefaultCtorInputIt(size_t n) : n(n) {}

      using value_type = T;
      using reference = T;
      using pointer = T;
      using iterator_category = std::input_iterator_tag ;
      using difference_type = int;
      using Self = DefaultCtorInputIt; // save typing (below)

      value_type operator *() { return T(); }
      Self& operator ++() { ++n; return *this; }

      friend bool operator == (const Self& lhs, const Self& rhs) {
         return lhs.n == rhs.n;
      }

      friend bool operator != (const Self& lhs, const Self& rhs) {
         return !(lhs == rhs);
      }

   private:
      size_t n;
};

This way, you can

std::vector<std::unique_ptr<int>> v;

 // Fill v with some values...

using NullUPtr =DefaultCtorInputIt<std::unique_ptr<int>>; // save typing

// Insert 10 default constructed instances at desired position:
v.insert(v.begin() + 42, NullUPtr(0), NullUPtr(10));

Note that for this to be as efficient as possible, you should probably make sure the above iterator qualifies as a random access iterator, such that the size of the range [NullUPtr(0), NullUPtr(10)) can be computed with O(1) upfront to allocate memory only once. When handcrafting your own iterator type, it's also worth having a look at Boost iterator facade.

Dipstick

Interesting solution. A smart iterator hadn’t crossed my mind. I’ll give you an upvote if you make this a RandomAccessIterator. 😉 – Rhetorician

Answer 3

Resize the vector and use std::move_backward.

e.g.

vec.resize(vec.size() + num_new)
std::move_backward(vec.begin() + num_unmoved,
                   vec.end() - num_new,
                   vec.end());

Kremlin