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 $$$\textbf{O( log2(N) )}$$$ for each operation.

Space complexity is less than double the space complexity of the general $$$\textbf{STL set}$$$ for reasonable cases ( N <= 10000000 ).

Some people use an ordered_set of pairs to count occurrences in $$$\textbf{" 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 in the set 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 <3 .