attempt's blog

Join two set in C++
By attempt, 11 years ago, In English

Hi all, I'm learning a very useful data struct int C++: set. I know set is a red-black tree so could we join two set into a new set with complexity O(log (number of elements)) in two set? And if we couldn't, what is the best algorithm to join two sets in C++? Thanks for helping.

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

Comments Comments (3)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I dont know is there a way to merge two set O(log N) , but if you have N sets and you will merge them one by one until only one set remainder , if u always add all elements from less size set to more size set overall complexity is O(N log^2 N) . Proof is here , this tree shows worst case because it is balanced : 


          8
      4       4
    2   2   2   2              // Secondly 4 sets...
   1 1 1 1 1 1 1 1             // Firstly there is 8 sets

There is about N log N nodes at this tree and for each node

there is average log N operations so complexity is O(N log^2 N)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

This adds elements of set2 to set1

set1.insert(set2.begin(), set2.end());

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

Sorry to disappoint, but I'm almost sure that there's no way to do this with STL sets or any other structure. You're basically merging sorted arrays, and the result can vary to any extremes depending on the contents of the arrays.

The best I know is the O(N) (sum of sizes) merging, where you keep 2 iterators looking at the smallest unprocessed element and always take the smaller one.

→ Reply