find_by_order() в C++

find_by_order() — это встроенная функция Ordered Set , которая представляет собой структуру данных на основе политик в C++. Структуры данных на основе политик не являются частью стандартной библиотеки шаблонов C++, но компилятор g++ поддерживает их.

Упорядоченный набор — это основанная на политике структура данных в g++, которая поддерживает уникальные элементы в отсортированном порядке. Он выполняет все операции, выполняемые Set в STL, со сложностью O(logN) .
Кроме того, следующие две операции также выполняются со сложностью O(logN) :

• order_of_key (K): Number of items strictly smaller than K.
• find_by_order(k): K^th element in a Set (counting from zero).

Функция find_by_order() принимает ключ, скажем, K , в качестве аргумента и возвращает итератор к K ^-му самому большому элементу в наборе.

Примеры:

Considering a Set S = {1, 5, 6, 17, 88}, 
s.find_by_order(0): Returns the 0^th largest element, i.e. the minimum element, i.e. 1.
s.find_by_order(2): Returns the 2^nd largest element, i.e. 6.

Note: If K >= N, where N is the size of the set, then the function returns either 0 or in some compilers, the iterator to the smallest element. 

Ниже представлена реализация функции find_by_order() на C++:

Временная сложность: O (n * log (n))
Вспомогательное пространство: O(n)