如何在保持顺序的同时有效地将列表插入到已排序的向量中？

Question

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

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

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

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

Answer 2

假设您的矢量已经排序并且将保持排序，这：

void merge(std::list<int> const& L, std::vector<int>& V) {
  auto old_end = V.size();
  V.insert( V.end(), L.begin(), L.end() );
  std::sort( V.begin()+old_end, V.end() );
  std::inplace_merge( V.begin(), V.begin()+old_end, V.end() );
}

可能是相对最优的。（注意 inplace_merge 可能会分配，所以这可能不像人们希望的那样最佳）

.insert 保证保留 space 并且最多只重新分配一次。

接下来，我们只对列表中的元素进行排序，然后我们进行就地合并，将其与向量前面的先前排序的元素合并。

我还把 list 变成了 const&，因为我们没有修改它。

如何在保持顺序的同时有效地将列表插入到已排序的向量中？

How do I efficiently insert a list into a sorted vector while maintaining order?

c++

concatenation

stl-algorithm