¿Cómo almacenar elementos duplicados en un conjunto ordenado en C++?

El conjunto ordenado contiene elementos ÚNICOS en orden ordenado al igual que el conjunto . Al tratar con un conjunto ordenado con elementos duplicados, se usa el tipo de datos pair<int, int> en lugar de int, donde el primer valor del par almacenará el elemento y el segundo valor almacenará los índices correspondientes. Al hacer esto, cada par en el conjunto ordenado será único y uno puede almacenar fácilmente los elementos duplicados de la array.

Operaciones:

1. order_of_key(): Acepta un elemento como parámetro y devuelve el número de elementos estrictamente menor que la clave. Al implementarlo, debemos pasar un par como parámetro cuyo primer valor debe ser el número para el que queremos el resultado y el segundo valor contendrá un valor negativo, por ejemplo, -1 porque los pares insertados en el conjunto ordenado tendrán el valor mayor que igual a 0, ya que denota los índices de la array.

2. find_by_order(): Acepta un índice como parámetro y devuelve un iterador al i- ^ésimo elemento (par) en orden ordenado. 

Ejemplo:

Supongamos que hay un par de conjuntos ordenados mySet = {4, 7, 2, 4, 5, 8, 4, 1, 3, 5}

Aquí,

• El par de conjuntos ordenados tiene elementos duplicados.
• Después de insertar todos los elementos en order_set_pair,
• mySet.order_of_key({5, -1}): Dará el número de elementos menos de 5, es decir, 6.
• mySet.find_by_order(8): Dará un iterador al octavo ^elemento en el conjunto ordenado, es decir, 7.

A continuación se muestra el programa C++ para implementar el enfoque anterior:

// C++ program to store duplicate 
// elements in ordered set
#include <bits/stdc++.h>
using namespace std;
  
// Header files to implement ordered set
// Common file
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
  
// namespace necessary for GNU based 
// policy based data structures
using namespace __gnu_pbds;
  
  
// Declaring ordered_set for pair<int,int>
typedef tree<pair<int,int>, null_type, 
        less<pair<int,int>>, rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set_pair;
  
// Driver code
int main()
{
      int arr[10] = {4, 7, 2, 4, 5, 
                   8, 4, 1, 3, 5};
      ordered_set_pair mySet;
    
      // Inserting elements to 
    // ordered_set_pair
      for(int i = 0; i < 10; i++)
    {
          mySet.insert({arr[i], i});
    }
  
    // count of elements less than 5
    cout << "Count of elements less than 5: " << 
             mySet.order_of_key({5, -1}) << endl;
  
    // Print 8th element in the ordered set
    // iterator to a pair
      auto itr = mySet.find_by_order(8); 
      cout << "The 8th element in the ordered set is: " << 
             (*itr).first << endl;
    return 0;
}

Count of elements less than 5: 6
The 8th element in the ordered set is: 7

Para consultas de rango como el número de elementos que se encuentran entre L y R inclusive, es decir, [L, R], uno puede encontrarlo usando:

mySet.order_of_key({R+1,-1}) – mySet.order_of_key({L,-1}) 

La complejidad del tiempo para ambas operaciones, es decir, find_by_order() y order_of_key() es O(log(n)) .