PBDS Code Generator

GCC ships an order-statistics tree that most C++ programmers never touch, because using it means remembering two obscure headers, a five-argument template and a namespace nobody types twice. The PBDS Generator writes that boilerplate for you, wrapped in a struct with named methods.

What you get is a red-black tree supporting two operations an ordinary std::set cannot manage in logarithmic time: find_by_order(k) for the k-th smallest element, and order_of_key(x) for the count of elements strictly below x. Those two turn a rank query from an O(n) walk into an O(log n) lookup.

Four key types are offered, from int through pair<int,int> to string, along with an ascending or descending comparator and a tree variable name of your choosing. Code regenerates as you change any of them, entirely in the page.

What Each Option Changes in the Output

• Key type substitutes into the template parameter and into every wrapper signature, so the generated struct compiles as written with no further editing.
• Comparator switches between less and greater, which reverses the meaning of both order operations: with greater, find_by_order(0) returns the largest element.
• Allow duplicates is the substantial one. A PBDS tree is a set and cannot hold two equal keys, so ticking it rewrites the whole structure to store pair<T,int> with an incrementing counter as the tiebreaker.
• In duplicate mode, order_of_key queries with {val, INT_MIN} rather than INT_MAX. That distinction is the entire difference between counting elements strictly below val and counting those at or below it.
• The erase method in duplicate mode locates its target through order_of_key and find_by_order instead of erasing a constructed pair, because no stored element ever has the sentinel counter and a direct erase would silently remove nothing.

When You Need Something Else

• Policy-based data structures are a GCC extension. Clang without libstdc++ headers and MSVC will not compile this at all, so check what your judge runs before relying on it.
• They are noticeably slower than a plain std::set for pure insert and lookup work, roughly 2 to 3 times. Reach for one only when you genuinely need the rank operations.
• The duplicate workaround costs memory and a comparison on every operation. If your values fit a small range, a Fenwick tree over frequencies is faster and simpler.
• There is no built-in erase by rank, and the wrapper does not add one. Combining find_by_order with the iterator overload is the usual route.
• Nothing here is compiled or checked. The generator writes text, and correctness beyond the template shape is on you and your compiler.