Search code examples
c++setmultiset

C++ multiset create from sorted vector

I have sorted array: 

vector<T*> arrs;

I have a multiset 

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

I have this:

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

I need convert vector to set fast(linear complexity). Can i do this with use std or boost functions?

Solution

  • If your array is already sorted, then you could use the insert-variant with a hint and "tell" the insert operation to start the search at the end (cf. 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.

    Hence, something like the following loop should do the job in about linear complexity (provided that arrs is sorted):

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