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); 
}