将一个向量添加到另一个向量的最佳方法

Question

std::vector<int> a;
std::vector<int> b;
std::vector<int> c;

我想将这三个向量连接起来，通过将b和c的元素附加到a。哪种方法最好，为什么?

---

1) 通过使用 vector::insert:

a.reserve(a.size() + b.size() + c.size());
a.insert(a.end(), b.begin(), b.end());
a.insert(a.end(), c.begin(), c.end());
b.clear();
c.clear();

2) 通过使用 std::copy：

a.reserve(a.size() + b.size() + c.size());
std::copy(b.begin(), b.end(), std::inserter(a, a.end()));
std::copy(c.begin(), c.end(), std::inserter(a, a.end()));
b.clear();
c.clear();

3) 通过使用C++11中的std::move：

a.reserve(a.size() + b.size() + c.size());
std::move(b.begin(), b.end(), std::inserter(a, a.end()));
std::move(c.begin(), c.end(), std::inserter(a, a.end()));
b.clear();
c.clear();

- vdenotaris

---

我相信移动是最好的选择，因为它将“移动”对象，而不是在清除时调用复制构造函数和析构函数。 - Uman

我看到你根据我的回答添加了对reserve()的调用... - Michael Goldshteyn

是的，我添加了调用 reverse() 的语句以确保全面。 - vdenotaris

顺便说一下，std::back_inserter(a) 可能会比 std::inserter(a, a.end()) 更方便和清晰。 - Christian Rau

我喜欢那些能够回答我正在谷歌搜索的问题的问题。感谢您包含源代码示例！ - Tomáš Zato

Answer 1

在我看来，你的第一种解决方案是最好的选择。

vector<>::insert 旨在添加元素，因此它是最合适的解决方案。

你可以在目标向量上调用 reserve 来预留一些空间，但除非你大量添加向量，否则它可能不会提供太多好处：vector<>::insert 知道将要添加的元素数量，并且只需避免一次 reserve 调用。

注意：如果这些是更复杂类型的 vector（例如自定义类或甚至 std::string），那么使用 std::move 可以为您提供良好的性能提升，因为它会避免拷贝构造函数。然而，对于 int 类型的向量，它不会给您带来任何好处。

注意2：值得一提的是，使用 std::move 将导致源 vector 的内容无法使用。

- Xaqq

---

而且，例如，在std::map<int, My_Obj*>上使用std::move来做到这一点？有什么好处吗？ - vdenotaris

不太可能，因为你的地图类型是基本类型：整数和指针。如果你的地图是 std::map<int, My_Obj>（即不是指向 My_Obj 的指针），那么就会有一些好处，前提是你的移动构造函数比复制构造函数更有效率。 - Xaqq

Answer 2

假设你想要复制而不是移动，以下是最佳方法：

a.reserve(a.size()+b.size()+c.size()); // Reserve space first
a.insert(a.end(),b.begin(),b.end());
a.insert(a.end(),c.begin(),c.end());

如果您想要搬家：

a.reserve(a.size()+b.size()+c.size()); // Reserve space first
a.insert(a.end(),std::make_move_iterator(b.begin()),
         std::make_move_iterator(b.end()));
a.insert(a.end(),std::make_move_iterator(c.begin()),
         std::make_move_iterator(c.end()));
b.swap(std::vector<int>()); // Clear and deallocate space
c.swap(std::vector<int>()); // Clear and deallocate space

更新：你已经多次编辑了你的问题，使其成为一个移动目标。你的第一个选项现在与我的第一个建议非常相似。

更新2：从C++11开始，根据你的库对vector的实现方式，你可能不再需要使用"与空向量交换"的技巧来清除和释放空间。以下方法可能更直观地完成这个任务：

// Empty the vectors of objects
b.clear(); 
c.clear();

// Deallocate the memory allocated by the vectors 
// Note: Unlike the swap trick, this is non-binding and any space reduction
//       depends on the implementation of std::vector
b.shrink_to_fit();
c.shrink_to_fit();

- Michael Goldshteyn

---

在我的工作中，我正在使用指针向量（std::vector<T_MY_OBJ*>），我希望能够进行良好的（避免内存泄漏问题）和安全的内存管理。 - vdenotaris

您的示例提供了一个整数向量。如果您有一个指针向量，根据您的用例，您可能希望考虑使用std::unique_ptr或std::shared_ptr来持有它们，以处理适当的清理工作。 - Michael Goldshteyn

+1 对于 make_move_iterator：如果你有一些数据不再使用，就从中进行 move 操作。 - Yakk - Adam Nevraumont

std::vector需要方便的insert_back()函数：在第一个参数固定为.end()的位置插入。 - NoSenseEtAl

+1 std::vector::insert在清晰度和内存分配性能之间找到了最佳平衡点，并且std::move提供了每个元素的高性能。 - Christian Rau

clear() 有什么不好的地方？ - exa

Answer 3

第一个选项是最佳选择，因为insert可以确定它正在添加多少个元素，并在开始复制之前调整向量大小以适应。其他选项没有这些信息，因此可能会在某些复制后重新调整大小，这比在开始时调整大小慢，或者调整大小超过一次。

然而，正如@michaelgoldshteyn所示，由于您将执行两次插入操作，您也可以使用最终大小自己调整数组的大小，从而节省一次调整大小的时间。

- Pete Becker

Answer 4

如果你真的想把向量 b 和 c 的数据追加到向量 a 中，你需要进行插入操作（这其实就是你的1.）：

a.reserve( a.size() + b.size() + c.size() ); // preallocate memory (see why)
a.insert( a.end(), b.begin(), b.end() );
a.insert( a.end(), c.begin(), c.end() );

根据编译器，std::copy（你的2.）通常应该很快。

由于std::vector必须始终在内存中连续，因此您不能仅仅进行移动（如C++11中所定义），如果您知道结束大小，则必须保留您的向量（这将避免不必要的向量重新分配）。但是，如果您真的关心性能，让它作为三个std::vector，并在需要读取其数据时对它们进行迭代。

- Kyle_the_hacker

---

不确定遍历3个向量是否更快。如果所有数据都打包到一个向量中，就像你说的那样，它们是连续的，并且访问连续内存更快。然而，对我来说，这太微小的优化了，不值得讨论。 - Xaqq

@Xaqq：是的，实际上这取决于你将要迭代数据的次数...如果只有一次，那么你应该将向量保持为三个不同的向量；如果超过两次，你应该合并它们。 - Kyle_the_hacker

啥？他的第二和第三个解决方案也可以，他不必使用他的第一个解决方案。同样，他不必保留任何东西，这只是一种优化。即使如此，使用随机访问迭代器（如std::vector）的std::vector::insert可能会进行适当的保留，从而仅通过初始保留避免整个操作的单个重新分配。 “由于std::vector始终必须在内存中连续，因此您不能仅移动数据”-当然，如果源向量之后被清除，则元素可以移动。 - Christian Rau

@ChristianRau：既然他要求“最佳方法”，我给了他最优化的答案...由于他需要进行多个插入，因此很可能会发生两次重新分配。当然，你可以移动，但不是C++11的意思（你不能使用第二个向量的分配内存作为第一个向量的扩展）：你很可能会通过复制省略来移动。 - Kyle_the_hacker