Всем привет!
Я взял всем известный ordered_set в C++ (а точнее __gnu_pbds::tree<...>
из GNU C++ Standard Template Library с реализованными Policy-Based Data Structures), унаследовался от него и добавил новые методы к наследнику:
lower_bound_with_order
-> возвращает итератор на минимальный>=
элемент + его индекс в множестве (порядок);upper_bound_with_order
-> возвращает итератор на минимальный>
элемент + его индекс в множестве (порядок);count_less
-> количество элементов, меньших заданного;count_less_equal
-> количество элементов, меньших либо равных заданному;count_greater
-> количество элементов, больших заданного;count_equal
-> просто количество равных элементов.
Преимущество (1) и (2) в том, что это всё считается за один обход дерева (один логарифм). Если вызывать сначала lower_bound
, а затем для него order_of_key
, то будет два обхода дерева — два логарифма.
Забирайте себе, если нужно. На очереди допиливание для ordered_multiset
. Пробую ordered_set
с компаратором std::less_equal
вместо std::less
...