Exploring the C++ PBDS ordered_set in some detail

28 Oct, 2026

Exploring the C++ PB_DS ordered_set

AI disclaimer
This blog is 100% written by me, not AI.

Approx. reading time: 7 minutes

I'm in my final year of college and the job search season is here. Which means, it's time to brush up on my competitive programming skills. Fun.

Now, in doing this, there's a handy data structure which I learnt about, the ordered_set (as GFG puts it¹), which is a data structure just like a normal std::set but it also stores a metadata tag which allows it to answer queries of the sort Find the jth smallest element and How many elements are smaller than this element efficiently (in O(log n) time).

The example program put forth by GFG is as follows:

#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>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    cout << s.order_of_key(25) << "\n";  // Outputs: 2 (because 10 and 20 < 25)
    return 0;
}

I was struggling a little to remember the various lines that I had to write to get this working. Remembering them is necessary because most OAs are on Hackerrank where switching tabs isn't allowed, so looking up the alias definition isn't possible. Furthermore, it doesn't even allow us to inspect the header files, so trying to work it out on the spot is out of the question too :/².

Hence, I thought a little exploration was in order. Maybe once I understood the code in depth, I'd have an easier time remembering it. And who knows, along the way I might come across some interesting data structures.

The header files

Immediately, I discovered that #include <ext/pb_ds/tree_policy.hpp> is unnecessary; the program still compiles without it. We only need to remember:

1. #include <ext/pb_ds/assoc_container.hpp>
2. using __gnu_pbds;.

The type alias

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

The tree class is defined in assoc_container.hpp as

  /**
   *  A tree-based container.
   *
   *  @tparam Key 	 	Key type.
   *  @tparam Mapped 	 	Map type.
   *  @tparam Cmp_Fn	 	Comparison functor.
   *  @tparam Tag 	 	Instantiating data structure type,
   *                            see container_tag.
   *  @tparam Node_Update 	Updates tree internal-nodes,
   *                            restores invariants when invalidated.
   *                     XXX See design::tree-based-containers::node invariants.
   *  @tparam _Alloc 	 	Allocator type.
   *
   *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
   *
   *  Base is basic_branch.
   */
  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
	   typename Tag = rb_tree_tag,
	   template<typename Node_CItr, typename Node_Itr,
		    typename Cmp_Fn_, typename _Alloc_>
	   class Node_Update = null_node_update,
	   typename _Alloc = std::allocator<char> >
  class tree : public PB_DS_TREE_BASE

This has a lot to unpack, let's take it step by step.

The first parameter: T

T is the template parameter, which we set Key type to (i.e. the type of the element stored in the set). If you want to store int in the set, then set T to int, otherwise if you want to have something like std::pair<int,int> in the set, set T to std::pair<int,int> and so on and so forth.

The second parameter: null_type

null_type is the Map type. Put null_type when you want to use the tree as a set, otherwise put any other type in it, and it will act as the value type for the map (map being Key -> Value where Key type is T (aforementioned) and Value type is the Map type).³

The third parameter: less<T>

less<T> is the Cmp_Fn (the comparator). This is basically how the set will be ordered. If the comparator is less, the set will have the smallest element at the beginning and the largest element at the end. This is important to remember if you're ever doing for (auto v : set) or for(auto it = set.begin(), it != set.end(), ++it) etc.

As an aside, you can use less_equal as the comparator too, although I prefer less since it imposes a strict total order , whereas less_equal imposes a weak order. This order is important because the way two elements are determined to be equal are if !cmp(a,b) && !cmp(b,a) where cmp is the supplied comparator function. With less_equal as the comparator, since a <= b or b <= a for all a, b , a and b will never be found equal by the code. So, if you have a set of ints with less_equal as the comparator and 1,2,3 as elements in it, set.find(2) will return set.end(), even though 2 is in the set.

Also, if you do need a multiset, you could have pair<T, int> as the type where T is whatever you wanted originally and int is there to provide a unique identifier (a simple counter will suffice for example). You get what is basically a multiset this way with none of the hassle and debugging headaches.

The fourth parameter: rb_tree_tag

rb_tree_tag is the Tag parameter.Tag defines the underlying structure of the tree. We need rb_tree_tag since we use a red black tree for O(log n) insertions, lookups and deletions. The GCC documentation page suggests two other tags which we can use: splay_tree_tag and ov_tree_tag.
A splay_tree_tag is used to implement a Splay tree, which is a binary search tree but it reorders nodes around to make the most frequently accessed nodes quick to access again. It has amortized O(log n) insertions, lookups and deletions, but the height can be O(n) which means it has worst-case complexity of O(n) for all the 3 operations. It's not usable for our purposes :/. It is useful if your algorithm benefits from having more frequent lookups be closer to the root, and can handle the occasional O(n) insertion/deletion.
An ov_tree_tag is used to implement an ordered-vector tree. I didn't find any information about it on the internet apart from this Stack Overflow post, which itself linked to a Java implementation⁴, along with some of the most quintessential SO behaviour I've ever seen. The Java implementation of the ordered vector tree is describing an ordered vector (shocking, I know), along with a great example program determining the effects of the original Star Wars movie on the careers of its stars⁵.

Now this is Java and we haven't got a source for C++ to confirm yet. So, at this point, having found little to none information on the Internet, I decided to just read the header files. Finding the right header files to look at was a matter of running a simple grep command for ov_tree_tag⁶.

And after doing some poking around, I came upon this piece of code in the ov_tree_map_.hpp file.

This validated the theory of the ov_tree being functionally equivalent to an ordered vector (i.e. a vector having the elements in an increasing/decreasing/what have you⁷ manner), because the lower_bound function is simply a binary search. This isn't really useful for us either because insertion/deletion is O(n). It is useful when you want random access into the container.

The fifth parameter: tree_order_statistics_node_update

This is an important one (it's the one that enables us to answer the aforementioned queries efficiently). It implements an algorithm where every node has some metadata attached to it which counts the number of nodes present in the subtree of that particular node. We can see this if we do a grep for tree_order_statistics_node_update

Here, looking into the order_statistics_imp.hpp file we see the following

This will result in each node's metadata being the number of nodes in the subtree of that node. It's useful because now you know exactly how many nodes are before a particular node in a set in O(log n) time, which is what we started off with and why we needed ordered_sets. I tried looking for other interesting node_update variants by doing a grep for classes and structs which ended in node_update.

Sadly there's no other interesting tree node update variants.

The sixth parameter: std::allocator<char>

There's a sixth parameter here, which doesn't show up in our code. It defines the _Alloc class and is set to the default value, which is std::allocator<char>. Reading the documentation for std::allocator, we can see that it's the default allocator used by the STL. It can be rebound to allocate any type that it's supplied. Its job is to manage the memory of the data structure. So, for example, it allocates more memory if the container runs out of available memory and manages the pointers etc.

Thanks for reading. If you spot any errors or want to get in touch, please email me at singhigeet1729 [AT] Google mail. I get way too much spam I don’t care about and far too few emails from people like you that I’d actually like to hear from, so please feel free to rectify that.