Ordered Set and GNU C++ PBDS

Hello everyone, in this C++ tutorial, we will be discussing Ordered Set and GNU C++ PBDS. PBDS stands for Policy-Based Data Structures. Policy-based data structures are not part of the standard C++ library. These data structures are supported by g++ compilers. The Ordered Set is a Policy-based data structure. It can perform all the set data structures operation in STL with two additional operations in log(n) complexity. These two operations are:

order_of_key(k): This returns the number of elements strictly smaller than k.
find_by_order(i): This returns an iterator to the i-th element where i starts from zero.

Both of these functions take O(logn) time. We will see the working of these two with an example program in this tutorial.

In order to use PBDS, we have to include the following in our code.

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>

We also need to add the following namespace in our code.

using namespace __gnu_pbds;

Let’s see the C++ program that demonstrated the ordered_set data structure.

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>  
#include <iostream> 
using namespace std; 
using namespace __gnu_pbds; 

typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;


int main() 
{ 
  ordered_set ord_set; 

  ord_set.insert(2); 
  ord_set.insert(4); 
  ord_set.insert(6);
  ord_set.insert(8);
  
  cout << "size of the ordered_set is:\n";
  cout << ord_set.size() << endl;
  
    cout << "Number of values less than 4 are:\n";
  cout << ord_set.order_of_key(4) << endl; 
    
    cout << "Number of values less than 7 are:\n";
  cout << ord_set.order_of_key(7) << endl; 
  
    cout << "Value at index 1:\n";
  cout << *(ord_set.find_by_order(1)) << endl; 
    
    cout << "Value at index 3:\n";
    cout << *(ord_set.find_by_order(3)) << endl; 

  return 0; 
} 

Output:

size of the ordered_set is:
4
Number of values less than 4 are:
1
Number of values less than 7 are:
3
Value at index 1:
4
Value at index 3:
8

Instead of ordered_set, we can use any name in the above program for this data structure but since it is an extended version of set data structure, it is generally used and known as ordered_set in competitive programming.

Also read: Difference between GCC and G++ in C++