c++ - 如何在保持顺序的同时有效地将列表插入到已排序的 vector 中？

Question

我想将一个 STL 列表的内容插入到一个现有的 vector 中，以便该 vector 在插入后仍然排序。

以下是我试图高效执行的代码。虽然它会起作用，但我相信应该有更好的连接方法。

Vector V 在描述的合并操作之前确实有一些元素。

Size(V) > Size(L)

如果此信息有帮助的话。

void merge(std::list<int>& L, std::vector<int>& V) {
    for (auto& x : L) V.push_back(x);
    std::sort(V.begin(), V.end());
}

代码需要使用 C++14。

Answer 1

您可以使用 vector::insert 轻松地做到这一点，尽管我不认为该实现可以有效地获得两个双向迭代器的距离，因此您可能希望保留空间以避免不必要的 vector 大小调整。至少从 C++11 开始，list::size 似乎必须是常数时间，所以如果您至少使用该版本，您可以简单地预先保留足够的空间。否则，因为您知道 V 比 L 大，所以在 inserting 之前将 V 的容量加倍:

V.reserve(V.size() + L.size());
V.insert(V.end(), L.begin(), L.end());