Ranks with a GNU ordered set
Count smaller keys and select a zero-based rank efficiently.
Sorted order does not imply efficient ranks
std::set keeps keys sorted, but walking to rank k costs O(k). GNU PBDS can maintain subtree information that supports order_of_key(x), the number of keys strictly below x, and find_by_order(k), an iterator to zero-based rank k.
With the red-black-tree configuration below, insert, erase by key, rank, and selection take O(log(n + 1)) for fixed-cost keys. A sorted vector is still a good static alternative: indexed selection is O(1), while insertions in the middle may shift O(n) elements.
Read the type alias as a configuration
OrderedSet is our chosen alias, not std::ordered_set. int is the key type; null_type means there is no separate mapped value; std::less<int> defines strict ascending order; rb_tree_tag selects a red-black tree; tree_order_statistics_node_update maintains rank metadata.
The comparator must be strict. std::less_equal is invalid as a duplicate workaround because a key would compare before itself. Ordinary integer keys here are unique, exactly as in a set.
// Complete GNU PBDS program in C++23 mode. No input.
#include <functional>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using OrderedSet = __gnu_pbds::tree<
int, __gnu_pbds::null_type, std::less<int>,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
int main() {
OrderedSet values;
for (int x : {7, 2, 9, 7}) values.insert(x);
std::cout << values.size() << '\n';
std::cout << values.order_of_key(7) << '\n';
auto it = values.find_by_order(1);
if (it != values.end()) std::cout << *it << '\n';
std::cout << (values.find_by_order(3) == values.end()) << '\n';
}Value in, count out; rank in, iterator out
order_of_key(8) counts values strictly smaller than 8, even if 8 is absent. It does not insert. find_by_order(2) asks for the third key in the current sorted state; it returns end() when the rank is at least the size.
For signed user ranks, reject k < 0 before converting to the unsigned rank type. For a one-based request, validate 1 ≤ k ≤ size and then use k − 1 exactly once. Always check a returned iterator before dereferencing when rank validity is not already guaranteed.
A GNU ordered set contains {2, 5, 8, 10}. What are order_of_key(8) and *find_by_order(2)?
Turn the idea into code
Predict every output of the complete program, then explain what find_by_order(3) means after duplicate insertion.
Give me a hint
List the distinct keys and their zero-based ranks first.
Show the explained solution
The output is 3, 1, 7, 1 on separate lines. The tree contains {2, 7, 9}; ranks are 0, 1, 2. Rank 3 is past the last key, so the comparison with end() is true.
Your notes
Mark complete when you can explain it yourself.