Estructura de datos basada en políticas de mapa en g ++

Hay algunas estructuras de datos que son compatibles con el compilador g ++ y no forman parte de la biblioteca estándar de C++. Uno de estos es: Estructura de datos basada en políticas , que se utiliza para alto rendimiento, flexibilidad, seguridad semántica y conformidad con los contenedores correspondientes en std. 
Esto también se puede usar como un mapa , para almacenar una clave y un valor (par) en un orden ordenado. 
Entonces, para usar esta estructura de datos, se deben agregar las siguientes líneas al código:
 

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
 
using namespace __gnu_pbds;

El siguiente es el código que muestra la estructura de datos basada en políticas como un mapa, puede agregar/eliminar pares de elementos, puede encontrar el número de pares menor que (x, y), k-ésimo par más pequeño, etc. en tiempo O (log N). La especialidad de este mapa es que tenemos acceso a los índices que tendría el par de elementos en una array 2D ordenada. Si el par no aparece en el mapa, obtenemos la posición que tendría el par en el mapa.
 

// Program showing a Policy Based Data Structure as a map
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
 
// A new data structure is defined
// Please refer https : // goo.gl/WVDL6g
typedef tree<pair<int, int>, null_type, less<pair<int, int> >,
             rb_tree_tag, tree_order_statistics_node_update>
    ordered_map;
 
// Driver code
int main()
{
    ordered_map om;
 
    om.insert({ 23, 20 });
    om.insert({ 23, 10 });
    om.insert({ 23, 30 });
    om.insert({ 12, 35 });
    om.insert({ 12, 22 });
 
    // Another method to insert pair
    // om.insert(make_pair(23, 20));
 
    // Print the contents of the map
    cout << "Contents of map:\n";
    cout << "KEY\tELEMENT\n";
    for (auto itr = om.begin(); itr != om.end(); ++itr) {
        cout << itr->first << "\t" << itr->second << "\n";
    }
 
    // value at 3rd index in sorted array.
    cout << "The value at 3rd index is "
         << "{" << om.find_by_order(3)->first << ", "
         << om.find_by_order(3)->second << "}\n";
 
    // Index of pair {23, 30}
    cout << "The index of pair {23, 30} is "
         << om.order_of_key({ 23, 30 }) << endl;
 
    // Pair {23, 40} is not in the map but it will show the
    // index number if it was there in sorted array
    cout << "The index of pair {23, 40} is "
         << om.order_of_key({ 23, 40 }) << endl;
 
    return 0;
}

Contents of map:
KEY    ELEMENT
12    22
12    35
23    10
23    20
23    30
The value at 3rd index is {23, 20}
The index of pair {23, 30} is 4
The index of pair {23, 40} is 5