Estructuras de datos basadas en políticas en g ++

El compilador g++ también admite algunas estructuras de datos que no forman parte de la biblioteca estándar de C++. Estas estructuras se denominan estructuras de datos basadas en políticas. Estas estructuras de datos están diseñadas para alto rendimiento, flexibilidad, seguridad semántica y conformidad con los contenedores correspondientes en std.
Para usar estas estructuras, se deben agregar las siguientes líneas al código: 
 

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

Por ejemplo, el siguiente es un código que muestra una estructura de datos basada en políticas que es como un conjunto, puede agregar/eliminar elementos, puede encontrar la cantidad de elementos menor que x, el késimo elemento más pequeño, etc. en el tiempo O (inicio de sesión). También se puede indexar como una array. La especialidad de este conjunto es que tenemos acceso a los índices que tendrían los elementos en una array ordenada. Si el elemento no aparece en el conjunto, obtenemos la posición que tendría el elemento en el conjunto.
 

// 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;
}

Producción: 
 

The value at 3rd index ::6
The index of number 6::3
The index of number seven ::4

NOTA: Tanto las funciones order_of_key como find_by_order funcionan en tiempo logarítmico.

NOTA (PARA USUARIOS DE VENTANA) : Los usuarios de Windows pueden tener problemas para importar la biblioteca pbds. Para solucionarlo sigue los siguientes pasos:

         Paso 1: Vaya al directorio donde está instalado MinGW.

         Paso 2: Vaya a \lib\gcc\mingw32\8.2.0\include\c++\ext\pb_ds\detail\resize_policy

         Paso 3: cambie el nombre de «hash_standard_resize_policy_imp.hpp0000644» a «hash_standard_resize_policy_imp.hpp»

Para insertar múltiples copias del mismo elemento en el conjunto ordenado, reemplace la siguiente línea,

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

Con

typedef tree<int , null_type , less_equal<int> , rb_tree_tag , tree_order_statistics_node_update> multiconjunto ordenado

// 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_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
 
// Driver code
int main()
{
    ordered_multiset p;
    p.insert(5);
    p.insert(5);
    p.insert(5);
    p.insert(2);
    p.insert(2);
    p.insert(6);
    p.insert(4);
 
    for (int i = 0; i < (int)p.size(); i++) {
 
        cout << "The element present at the index " << i
             << " is ";
 
        // Print element present at the ith index
        cout << *p.find_by_order(i) << ' ';
        cout << '\n';
    }
 
    return 0;
}

The element present at the index 0 is 2 
The element present at the index 1 is 2 
The element present at the index 2 is 4 
The element present at the index 3 is 5 
The element present at the index 4 is 5 
The element present at the index 5 is 5 
The element present at the index 6 is 6