Hi everyone!
I took an ordered_set in C++ (i.e. __gnu_pbds::tree<...>
from GNU C++ Standard Template Library with implemented Policy-Based Data Structures) and added 6 new methods to derived class:
lower_bound_with_order
-> iterator to minimal element such>=
than given key + its index in the set (its order);upper_bound_with_order
-> iterator to minimal element such>
than given key + its index in the set (its order);count_less
-> number of elements which are less than given element;count_less_equal
-> number of elements which are less or equal than given element;count_greater
-> number of elements which are greater than given element;count_equal
-> just a number of elements which are equal to given element.
Advantages of (1) and (2): it is implemented in a single traversal of a tree ($$$\log{N}$$$). If you will call lower_bound
firstly, and call order_of_key
secondly, then you will spend in two times more time for doing it ($$$\log{N} + \log{N}$$$) instead.
You can take it to your CP template, if you want. I will try to do same for a ordered_multiset
. I'm trying ordered_set
with a comparator std::less_equal
instead of std::less
...