order_of_key и find_by_order для set/map/multiset/multimap

Тимофей Чернов
Тимофей Чернов

Сейчас в map/set и подобных структурах данных, основанных на сбалансированных деревьях, есть функции lower_bound и upper_bound, выполняющие поиск за O(logN). Однако, функций нахождения количества элементов заданного и ей обратной - нет, поэтому приходится писать тяжеловесные структуры данных вроде деревьев отрезков или собственных сбалансированных деревьев, тогда как для добавления этой функциональности в уже существующие структуры нужно всего лишь хранить размер поддерева.

Функция find_by_order, кстати говоря, является аналогом nth_element. 

Стоит отметить, что данная функциональность реализована в GCC, выглядит это так:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include <iostream>

template<typename T>
using ordered_set = __gnu_pbds::tree<
  T,
  __gnu_pbds::null_type,
  std::less<T>,
  __gnu_pbds::rb_tree_tag,
  __gnu_pbds::tree_order_statistics_node_update>;

int main() {
  ordered_set<int> s;
  s.insert(1);
  s.insert(3);
  s.insert(5);
  s.insert(7);
  s.insert(9);

  // prints 2 - number of elements strictly less than 5
  std::cout << s.order_of_key(5) << std::endl;
  
  // prints 9 - 4'th element in sorted order
  std::cout << *s.find_by_order(4) << std::endl;
}
9
рейтинг
3 комментария
yndx-antoshkka
А как вы видите это в стандарте? Новый контейнер? Какая алгоритмическая сложность должна быть у order_of_key?
yndx-antoshkka
Тимофей Чернов
yndx-antoshkka,
Новый контейнер - в худшем случае, в лучшем - дополнение к текущим, но что делать с дополнительным расходом памяти на еще одно число (размер поддерева) в каждой вершине - не уверен.
Сложность у обеих операций должна быть логарифмическая, делаются они так:
order_of_key: ищем ключ, смотрим на размер левого поддерева
find_by_order: смотрим на размер поддерева корня, спускаемся в соответствующее поддерево в зависимости от оставшегося размера
Тимофей Чернов
yndx-antoshkka
Боюсь что старый контейнер поменять нет возможности, это поломает бинарную совместимость в stdlibc++

Создать новый контейнер - это очень тяжёлая работа и должны быть серьёзные аргументы в целесообразности такого действия. Если готовы идти до конца, то для начала обсудите идею на std-proposals форуме (он есть в полезных ссылках на этом сайте).
yndx-antoshkka
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).