插入移动语义类型的向量

Question

我有一个 std::vector<std::unique_ptr<T>>。我想在这个向量的中间插入一些 nullptr。我尝试使用 vec.insert(first, size, nullptr)，但这显然行不通，因为需要复制 nullptr。我可以反复调用单数版本的 insert，但我想知道是否有更有效的方法。

- Indiana Kernick

Answer 1

"高效"是可以衡量的。但如果你希望一次性移动元素而不是不断地将它们向右移动一个项目，你可以使用std::rotate。以下是方法：

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

rotate函数的功能是将中间迭代器作为新序列的“第一个”，而前一个迭代器作为“最后一个”，因此选择上述迭代器会将空指针范围移至其预期位置（在第一个之前）。

此外，由于您标记了C++17，您还可以向标准算法传递执行策略，并希望获得一些并行性。

- StoryTeller - Unslander Monica

---

需要翻译的内容：请注意，resize() 可能会使 first 无效……通常情况下应该在 resize()（或至少是 reserve()）之后确定 first。 警惕 resize() 可能导致 first 失效……一般来说，在确定 first 之前，应该进行 resize()（或至少是 reserve()）。 - Arne Vogel

这是一个旋转：https://www.youtube.com/watch?v=W2tWOdzgXHA - schoetbi

Answer 2

你可以组合自己的迭代器，在被解引用时创建默认实例。这些是prvalues，可以在vector中构造移动类型。使用此类迭代器的计数实例来调用std::vector::insert。下面是一个示例，可能不符合标准，但是可行。

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

这样，您就可以

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

请注意，为了使其尽可能高效，您应该确保上述迭代器符合随机访问迭代器的要求，以便可以预先使用O(1)计算范围[NullUPtr(0), NullUPtr(10))的大小，从而只分配内存一次。当手工制作自己的迭代器类型时，也值得看一看Boost iterator facade。

- lubgr

---

有趣的解决方案。聪明的迭代器没有在我的脑海中出现过。如果您将其变成RandomAccessIterator，我会给您点赞。 - Indiana Kernick

Answer 3

调整向量大小并使用 std :: move_backward。

例如：

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

- Mark Borgerding