c++ - std set insert and union efficient way -

c++ - std set insert and union efficient way -

i working on problem trying take union , trying simple benchmarking code see efficiency.

the code simple (inserting) few 1000000 elements set. maintain simple lets maintain set_union away discussion.

test code :

int main() { // setting int num = 40000000; auto = v.begin(); std::vector<int> a; a.reserve(num); (int =0;i < num ; ++i) { a.push_back(i); } // method 1 { std::set<int> v; (int i= 0 ; i< num ; ++i) { v.insert(a[i]); } } // method 2 { std::set<int> v; auto = v.begin(); (int i= 0 ; i< num ; ++i) { = v.insert(it,a[i]); } } // method 3 { std::set<int> v; auto = v.begin(); (int i= 0 ; i< num ; ++i) { = std::next(v.insert(it,a[i])); } } // method 4 { std::set<int> v; auto = v.begin(); (int i= 0 ; i< num ; ++i) { = v.insert(it,i); ++it; } } // method 5 : idiomatic { std::set<int> v; std::copy(a.begin(), a.end(), std::inserter(v,v.end())); } homecoming 0; }

method 1 : slowest (as expected) : ~38 sec method 2 : fastest (as expected) : ~8 sec method 3 : ~20 sec method 4 : ~20 sec method 5 : ~20 sec

the results create sense method 3 , 4 same , on digging mehtod 5 found std::inserter creates output iterator on assignment same thing (or translates same) method 3/4.

is intentional ? why can't algorithms written in way translate efficient insertion way ? method 2 gives exact accurate hint whereas 3,4,5 increment iterator set.end() (in case when inserting sorted range , std::next(insert(pos,new_max_element)) == set::end()) , give hint insertion.

this makes using stl algorithms inefficient if utilize std::inserter pass iterator such ordered containers. on side note : not understand how set_union can work in linear time if inserting operation set logarithmic. exmaple set_union(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(output_set, output_set.end()) . sorted vectors fine set ? can 1 set links or referrals complexity analysis ?

also great if can explain or give referrals complexity analysis proves inserting set right hint (for illustration next number smaller or larger current beingness inserted) gives algorithm amoritzed constant complexity instead of logn.

c++ algorithm set stl-algorithm stdset