templates/ordered-set.cpp
compilable
$cat templates/ordered-set
Ordered Set
Policy-based order-statistics tree — find k-th element and count elements less than x in O(log n).
#ordered-set#pbds#order-statistics#policy-based
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T, typename Cmp = less<T>>
using ordered_set = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void ms_erase(ordered_multiset<int>& s, int val) {
auto it = s.find_by_order(s.order_of_key(val));
if (it != s.end() && *it == val) s.erase(it);
}
int ms_count(ordered_multiset<int>& s, int val) {
return s.order_of_key(val + 1) - s.order_of_key(val);
}20 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)
Ordered Set (Policy-Based)
GNU __gnu_pbds::tree with order statistics. Extends std::set with:
find_by_order(k) — iterator to the -th element (0-indexed)order_of_key(x) — number of elements strictly less than Type Aliases
ordered_set — unique keys, ascending orderordered_multiset — duplicate keys allowed (uses less_equal)Multiset Quirks
With less_equal, the standard find() and erase() don't work correctly. The wrapper provides:
ms_erase(val) — erase one occurrencems_count(val) — count occurrencesorder_of_key(val) for rank