I have merged lower_bound and order_of_key into a single method in C++ ordered_set

Revision en1, by dmkz, 2022-12-28 19:02:30

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:

  1. lower_bound_with_order -> iterator to minimal element such >= than given key + its index in the set (its order);

  2. upper_bound_with_order -> iterator to minimal element such > than given key + its index in the set (its order);

  3. count_less -> number of elements which are less than given element;

  4. count_less_equal -> number of elements which are less or equal than given element;

  5. count_greater -> number of elements which are greater than given element;

  6. 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.

Source code
Result of testing

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...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian dmkz 2022-12-28 19:03:13 84
en1 English dmkz 2022-12-28 19:02:30 6742 Initial revision for English translation
ru1 Russian dmkz 2022-12-28 18:43:16 6723 Первая редакция (опубликовано)