Is there any solution that will merge two sets in n=( size_of_se1 + size_of_set2 ) times in c++? If I iterate through both the sets and take the smaller value and insert it in another set, this way I can merge two sets but it will take close to n*logn time as set insert operation takes logn time. Also I can let the set1 unchanged and insert all the elements of set2 in set1 or vice versa but it will also take size_of_set2*log(size_of_set1) or size_of_set1*log(size_of_set2) time. I am searching for a solution if it is actually possible to merge two sets in linear time. I googled it and spend some time to find out any solution regarding to it but failed :( Can anyone help me with your valuable opinion? thanks in advance :)

According to this and this, this should be linear:

You can get rid of

`set<int> m(v.begin(), v.end());`

by using:Got it. Thanks :)

Is this guaranteed to be linear time, though? (Edit: I believe the answer is "probably not linear-time, but it's super tricky". See next paragraph.) fofao_funk's solution is clearly linear time, as inserting N elements into a vector and constructing a set from an ordered vector (see section 23.4.6.2 of the C++11 standard, or section 26.4.6.2 of the C++17 standard) are both linear-time operations.

I previously thought yours

couldbe implementation-dependent, as suggested by the fact that using`set::insert`

to insert a sorted range is not guaranteed to to take linear time. However, the standard says`set::insert(p, t)`

takes "amortized constant time if t is inserted right before p" (technically this says nothing about duplicate elements, but let's ignore that), so that strongly suggests your solution is guaranteed to be linear time. However, the plot thickens! Here's what the`inserter`

does:If it just did a bunch of

`container->insert(container.end(), value)`

operations, that would be amortized constant time per the standard. It does not do that, though: It inserts at`m.end()`

, then takes the iterator to just-added element and advances it (thus making it point to`m.end()`

again). This last iterator-advancing operation is probably not guaranteed to be amortized constant time.I just run the code and check the runtime. But is there any constant time factor, I am not sure? When I ran the code it shows slightly higher time complexity than linear. If I think logically surely it is linear.

It's really very helpful. It is almost linear in time complexity if I am not wrong! Again thanks fofao_funk :)

I guess this can be done in O(n) ...plz correct me if I m wrong (assuming both set size to be n)

Why does "merge" is more recommended(Source: https://www.techiedelight.com/merge-two-sets-set_union-merge-cpp/)

I have a

`list`

of`set<char>`

and I am using "insert" like so...Is there any reason to change the code to use "merge"?

Why don't you use FHQ_Treap?It is a kind of Treap which can split and merge two BST in $$$O(logn)$$$