kissu_pari_na's blog

Merging two sets in c++
By kissu_pari_na, history, 6 years ago, In English

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

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

According to this and this, this should be linear:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
	set<int> a {1, 3, 7, 10, 13, 20};
	set<int> b {2, 3, 5, 7, 11, 13, 15, 19};
	
	vector<int> v;
	merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(v));
	
	set<int> m(v.begin(), v.end());
	
	for(const auto &element : m) {
		cout << element << " ";
	}
	cout << endl;
	
	return 0;
}
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    You can get rid of set<int> m(v.begin(), v.end()); by using:

    set<int> m;
merge(a.begin(), a.end(), b.begin(), b.end(), inserter(m, m.end()));
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it. Thanks :)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 14   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry but can I ask what is the risk of using set<int> m(v.begin(), v.end()); ?

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -49 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply