Policy Based Data Structure

Published in

Nybles

4 min readSep 16, 2021

Here we are going to talk about a data structure that will undoubtedly strengthen your armory of code, the ‘Policy Based Data Structure’ or more affectionately, PBDS.

Apart from the customary introduction and implementation, this article offers guidance for you to tinker with different flavors of PBDS as well. Let us dive in… *inhales

What are Policy based data structures?

Policy based data structures in C++ are somewhat similar to sets. They provide a few extra, but considerably powerful operations which grant a programmer the virtues of high-performance, semantic safety and flexibility as compared to the standard data structures of C++ standard library.

Headers for Policy based data structures

A word of caution

You might get the following error while importing the PBDS header’s file

fatal error: ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp: No such file or directory

For Windows

To fix this go to directory C:\MinGW\lib\gcc\mingw32\8.2.0\include\c++\ext\pb_ds\detail\resize_policy

There you will find a file that looks somewhat like, “hash_standard_resize_policy_imp.hpp0000644”.

Rename it to “hash_standard_resize_policy_imp.hpp” and you’re all set to go.

Extra Operations

So what is it that gives PBDS an edge over sets?

There are two extra operations in Policy Based Data Structures, apart from those in the standard library. Each of these operations has a time complexity of O(log2(n)). They are listed below:

* order_of_key(k): Returns the number of elements strictly smaller than k.
* find_by_order(k): Returns the address of the element at kth index in the set while using zero-based indexing, i.e the first element is at index zero.

Ordered set

Ordered sets can be seen as extended versions of sets in Policy Based Data Structure.

For the Data Structure to accept distinct entries

Template to be used:

Elucidating the extra operations offered by PBDS:

Let ‘a’ be an ordered_set in which the elements 2, 4, 3, 7, and 5 are inserted.

Then elements in ordered_set ‘a’ would be stored in the following order:

2, 3, 4, 5, 7

find_by_order: Here, find_by_order(x) will return the address of (x+1)th element in the ordered_set a. For example, find_by_order(3) will return the address of ‘5’ as the 4-th element(using 1 based indexing) present in the set is 5.
order_of_key: Here, order_of_key(x) will return the number of elements strictly less than x. For example, order_of_key(10) will return 5, as all entries in the set are less than 10.

That seems to be enough food for our gray matter, but

So moving ahead,

For the Data Structure to accept duplicate entries as well

We shall define a multi-set. The template to be used for it is

Implementation

Implementing a Data Structure that accepts Pairs as entries

For this implementation, we’ll use T = pair <int, int>. In other words, it is an ordered_set of pairs.

Here is the implementation of an ordered set with distinct elements using pairs:

Here is the implementation of an ordered set with duplicate elements using pairs.

Customizing the name of the data structure

Just replace the name of “Name_given_to_structure” in the Template with the name you want to give to it.

For example if you want to name your data structure “Ansh”, then the template should look like:

template <class T> using Ansh = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template <class T> using Ansh = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

Questions

Inversion - Codeforces

codeforces.com

Count Primes - LeetCode

leetcode.com

Further Resources

Ordered Set and GNU C++ PBDS - GeeksforGeeks

www.geeksforgeeks.org