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

[apolukhin]

Перенос предложения: голоса +11, -0 Автор идеи: Тимофей Чернов

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;
}

[apolukhin]

yndx-antoshkka, 30 марта 2017, 11:51 А как вы видите это в стандарте? Новый контейнер? Какая алгоритмическая сложность должна быть у order_of_key?

Тимофей Чернов, 30 марта 2017, 11:58 yndx-antoshkka, Новый контейнер - в худшем случае, в лучшем - дополнение к текущим, но что делать с дополнительным расходом памяти на еще одно число (размер поддерева) в каждой вершине - не уверен. Сложность у обеих операций должна быть логарифмическая, делаются они так: order_of_key: ищем ключ, смотрим на размер левого поддерева find_by_order: смотрим на размер поддерева корня, спускаемся в соответствующее поддерево в зависимости от оставшегося размера

yndx-antoshkka, 30 марта 2017, 12:57 Боюсь что старый контейнер поменять нет возможности, это поломает бинарную совместимость в stdlibc++

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