order_of_key() en C++

order_of_key() es una función integrada de Ordered Set, que es una estructura de datos basada en políticas en C++. Las estructuras de datos basadas en políticas no forman parte de la biblioteca estándar de C++, pero el compilador g++ las admite.

El conjunto ordenado es una estructura de datos basada en políticas en g ++ que mantiene los elementos únicos en orden. Realiza todas las operaciones realizadas por la estructura de datos establecida en STL en complejidad log(n) y realiza dos operaciones adicionales también en complejidad log(n).

Dos operaciones importantes que podemos realizar en estas estructuras de datos:

• order_of_key: el número de elementos en un conjunto que son estrictamente más pequeños que k
• find_by_order: Devuelve un iterador al i-ésimo elemento más grande

La función order_of_key() acepta una clave y devuelve el número de elementos en el conjunto ordenado que son estrictamente menores que la clave que se le pasó como parámetro.

Por ejemplo,

Supongamos que tenemos un conjunto s: {1, 5, 6, 17, 88}, entonces:
s.order_of_key(6): el recuento de elementos estrictamente menor que 6 es 2.
s.order_of_key(25): recuento de elementos estrictamente menor que 25 es 4.

Comparación con lower_bound() y distance()

• En C++ tenemos std::distance que toma dos iteradores y calcula la distancia entre ellos. es decir, el número de elementos entre ellos. Puede ser una alternativa para find_by_order pero su complejidad de tiempo es O(n) para un conjunto ordenado.
• lower_bound también es una opción y lleva log(n) cantidad de tiempo. Devuelve un iterador al primer elemento que no es menor que k. Pero dado que devuelve un iterador, nunca podemos saber el índice o la cantidad de elementos que son menores que k.

  Para vectores y estructuras de datos lineales, se puede realizar:

  index = lower_bound(k) – myvector.begin() ;

  Pero dado que set es una estructura de datos basada en árbol, no podemos realizar esta operación.

El siguiente programa ilustra la implementación de order_of_key():

// CPP program to illustrate order_of_key()
// for policy based data structures
  
#include <iostream> 
using namespace std; 
  
// Important header files  
#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; 
  
// Declaring ordered_set
typedef tree<int, null_type, less<int>, rb_tree_tag, 
            tree_order_statistics_node_update> 
    ordered_set; 
  
  
// Driver code 
int main() 
{ 
    ordered_set mySet;
      
    // Inserting elements to ordered_set
    mySet.insert(5); 
    mySet.insert(2); 
    mySet.insert(6); 
    mySet.insert(4); 
  
    // count of elements less than 6 
    cout << "Count of elements less than 6::"
        << mySet.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 << "Count of elements less than 7 ::"
        << mySet.order_of_key(7) << endl; 
  
    return 0; 
} 

Count of elements less than 6::3
Count of elements less than 7 ::4