Блог пользователя attempt

Join two set in C++
Автор attempt, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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)

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

This adds elements of set2 to set1

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить