C++ multiset 从排序向量创建

Question

我已经排序数组：

vector<T*> arrs;

我有一个多重集

multiset<T*, sp_t_less<T>> tr;

我有这个：

tr.erase();
tr.insert(arrs.begin(), arrs.end());

我需要转换矢量以快速设置（线性复杂度）。我可以使用 std 或 boost 函数来做到这一点吗？

Answer 1

如果您的数组已经排序，那么您可以使用带有 hint 和 "tell" 插入操作的 insert 变体在末尾开始搜索（参见multiset::insert):

iterator insert( iterator hint, const value_type& value )

** Complexity ** Amortized constant if the insertion happens in the position just after the hint, logarithmic in the size of the container otherwise.

因此，像下面这样的循环应该可以解决线性复杂度的问题（假设 arrs 已排序）：

for (auto t : arrs) {
  tr.insert(tr.end(), t);   
}

C++ multiset create from sorted vector