Multi Ordered Set Data Structure

Revision en6, by Tareq_Ali, 2021-02-26 02:49:03

Hello everyone

I would like to share with you an efficient trick we can use with ordered_set data structure to make it contain more than one occurrence for any value we want without any problem. But first, if you don't know this data structure, you can read about it here .

Now let's discuss that: First of all, for sure we need to set the comparison operator to $$$\textbf{" less_equal <data_type> "}$$$ to allow occurrences, after that insertion will work fine, but the function erase will do nothing ever. I noticed that using the comparison operator $$$\textbf{" less_equal <data_type> "}$$$ makes the two functions $$$\textbf{" s.lower_bound(value) , s.upper_bound(value) "}$$$ exchange their functions for any value, depending on that to erase one occurrence of some value from the set we can write $$$\textbf{" s.erase(s.upper_bound(value)) "}$$$, just that simple, it will work efficiently.

To see the important functions of this data structure you can read my code, I have tested the code and got accepted in many problems. for example, this is the problem, and this is my submission.

About time and space complexity: Time complexity is O( log2(N) ) for each operation. Space complexity is less than double the space complexity of the general (STL) set for reasonable cases ( N <= 10000000 ).

Some people use an ordered set of pairs to count occurrences in " p.second " and do the job, But this is faster to code and can do more tasks, Suppose you have an empty set and 2 types of queries: * inserting the element (x) into the set. * answering this query : what is the k_th element if we sort the elements in ascending order. Now if you use it this way you can answer the query in 1 line of code, and the pair trick can't solve it.

Finally, thank you for reading my first blog, I hope it will be benefit.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English Tareq_Ali 2021-02-26 03:17:41 1 Tiny change: 't this way you can a' -> 't this way, you can a' (published)
en12 English Tareq_Ali 2021-02-26 03:10:37 15
en11 English Tareq_Ali 2021-02-26 03:07:18 12
en10 English Tareq_Ali 2021-02-26 03:00:15 31
en9 English Tareq_Ali 2021-02-26 02:56:24 30
en8 English Tareq_Ali 2021-02-26 02:54:25 4
en7 English Tareq_Ali 2021-02-26 02:49:49 3 Tiny change: 'uss that: \nFirst of' -> 'uss that: \n\nFirst of'
en6 English Tareq_Ali 2021-02-26 02:49:03 3 Tiny change: 'cuss that:\n\nFirst of' -> 'cuss that: \nFirst of'
en5 English Tareq_Ali 2021-02-26 02:48:40 2 Tiny change: 'ss that:\nFirst of' -> 'ss that:\n\nFirst of'
en4 English Tareq_Ali 2021-02-26 02:47:10 52
en3 English Tareq_Ali 2021-02-26 02:42:07 24
en2 English Tareq_Ali 2021-02-26 02:37:12 60
en1 English Tareq_Ali 2021-02-26 02:29:00 2038 Initial revision (saved to drafts)