### kissu_pari_na's blog

By kissu_pari_na, history, 3 years ago,

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 :)

• +30

 » 3 years ago, # |   +37 According to this and this, this should be linear: #include using namespace std; const int INF = 1e9; int main() { set a {1, 3, 7, 10, 13, 20}; set b {2, 3, 5, 7, 11, 13, 15, 19}; vector v; merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(v)); set m(v.begin(), v.end()); for(const auto &element : m) { cout << element << " "; } cout << endl; return 0; } 
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 You can get rid of set m(v.begin(), v.end()); by using: set m; merge(a.begin(), a.end(), b.begin(), b.end(), inserter(m, m.end())); 
•  » » » 3 years ago, # ^ |   0 Got it. Thanks :)
•  » » » 3 years ago, # ^ | ← Rev. 14 →   +3 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 could be 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: iter = container->insert(iter, value); ++iter; 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.
•  » » » » 3 years ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   0 Sorry but can I ask what is the risk of using set m(v.begin(), v.end()); ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 It's really very helpful. It is almost linear in time complexity if I am not wrong! Again thanks fofao_funk :)
 » 2 years ago, # | ← Rev. 3 →   -49 I guess this can be done in O(n) ...plz correct me if I m wrong (assuming both set size to be n)
 » 16 months ago, # |   -21 Why does "merge" is more recommended(Source: https://www.techiedelight.com/merge-two-sets-set_union-merge-cpp/)I have a list of set and I am using "insert" like so... it1->insert(it2->begin(), it2->end()); myList.erase(it2--); Is there any reason to change the code to use "merge"?
 » 16 months ago, # |   +3 Why don't you use FHQ_Treap?It is a kind of Treap which can split and merge two BST in $O(logn)$
•  » » 11 months ago, # ^ |   0 Can you please give me any link to learn this?