C++多集，从分类矢量

Question

创建我已经整理数组：

vector<T*> arrs; 

我有一个多重

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

我有这样的：

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

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

Answer 1

如果阵列已经排序，那么你可以使用insert -variant与hint，并“告诉”插入操作开始在结束搜索（参见multiset::insert）：

iterator insert(iterator hint, const value_type& value) 

**复杂性** 如果插入仅发生在提示后的位置，则为摊销常数，否则为容器大小的对数。

因此，像下面的循环应该做的工作在有关线性复杂度（前提是arrs排序）：

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