Policy based Ds

The g++ compiler also supports some data structures that are not part of the C++ standard library. Such structures are called policy-based data structures.
These data structures are designed for high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std.

To use these structures, the following lines must be added to the code:

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

Example

// Program showing a policy-based data structure. 
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#include <iostream> 
using namespace __gnu_pbds; 
using namespace std; 
  
// a new data structure defined. Please refer below 
// GNU link : https://goo.gl/WVDL6g 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    ordered_set; 
  
// Driver code 
int main() 
{ 
    ordered_set p; 
    p.insert(5); 
    p.insert(2); 
    p.insert(6); 
    p.insert(4); 
  
    // value at 3rd index in sorted array. 
    cout << "The value at 3rd index ::" 
         << *p.find_by_order(3) << endl; 
  
    // index of number 6 
    cout << "The index of number 6::" 
         << p.order_of_key(6) << endl; 
  
    // number 7 not in the set but it will show the  
    // index number if it was there in sorted array. 
    cout << "The index of number seven ::"
         << p.order_of_key(7) << endl; 
  
    return 0; 
}
// The value at 3rd index ::6
// The index of number 6::3
// The index of number seven ::4

NOTE: Both the functions order_of_key and find_by_order work in logarithmic time.

Try the following example in the editor below.

You are given an ordered_set X, answer the queries asked in the comment in the editor below.