c++ std::vector 分割成两个

Question

有没有一种简单且运行时高效的方法，可以将 C++ 中的 std::vector<> 分半并拆分为两个其他向量？

因为现在我正在这样做：

std::vector<> v1, v2;
for(int i = 0; i < vector.size(); i++)
{
    if(i < vector.size()/2) v1.push_back(vector[i]);
    else v2.push_back(vector[i]);
}

这个操作的时间复杂度是O(n)，而且我经常需要执行它。那么有没有更好的方法呢？

- user1855952

---

只需使用迭代器引用不同的半部分，而不实际拆分它们。 - GManNickG

如果您需要经常这样做，也许使用不同的容器会更适合您的算法？ - didierc

如果您需要经常这样做，那么您是否面临着设计问题？ - billz

可能是将向量分成两个较小数组的最佳方法？的重复。 - jww

Answer 1

如果你确实需要两个向量，而且不能使用GMan评论中的建议：

// where v1 is your original vector
std::vector<T> v2(
    std::make_move_iterator(v1.begin() + v1.size()/2),
    std::make_move_iterator(v1.end()));
v1.erase(v1.begin() + v1.size()/2, v1.end());

虽然时间复杂度仍为O(n)，但你已经达到了最优解。

如果您需要将原始向量保留分开：

std::vector<T> v2(v1.begin(), v1.begin() + v1.size()/2),
               v3(v1.begin() + v1.size()/2, v1.end());

- Benjamin Lindley

---

为什么在两个调用中的第二个参数中都需要v1.end()？ - user1855952

它指定了您想要复制或擦除的范围的末尾，无论情况如何。 - Benjamin Lindley

你可以使用 std::make_move_iterator(v1.begin()) 和 std::make_move_iterator(v1.end()) 来填充 v2，从而改进这个程序。 - Jonathan Wakely

@JonathanWakely：做得好。完成了。 - Benjamin Lindley