Я объединил lower_bound и order_of_key в один метод в C++ ordered_set (__gnu_pbds::tree)

Revision ru1, by dmkz, 2022-12-28 18:43:16

Всем привет!

Я взял всем известный ordered_set в C++ (а точнее __gnu_pbds::tree<...> из GNU C++ Standard Template Library с реализованными Policy-Based Data Structures), унаследовался от него и добавил новые методы к наследнику:

  1. lower_bound_with_order -> возвращает итератор на минимальный >= элемент + его индекс в множестве (порядок);

  2. upper_bound_with_order -> возвращает итератор на минимальный > элемент + его индекс в множестве (порядок);

  3. count_less -> количество элементов, меньших заданного;

  4. count_less_equal -> количество элементов, меньших либо равных заданному;

  5. count_greater -> количество элементов, больших заданного;

  6. count_equal -> просто количество равных элементов.

Преимущество (1) и (2) в том, что это всё считается за один обход дерева (один логарифм). Если вызывать сначала lower_bound, а затем для него order_of_key, то будет два обхода дерева — два логарифма.

Исходный код
Результат запуска исходного кода

Забирайте себе, если нужно. На очереди допиливание для ordered_multiset. Пробую ordered_set с компаратором std::less_equal вместо std::less...

Tags data strutcure, set, ordered_set, c++, pbds, lower_bound, upper_bound

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 Первая редакция (опубликовано)