C++
// C++ code
#include <iostream>
#include <utility>
using namespace std;
int main()
{
// Declaring the PAIR1 of int and char
// IF pair is not initialized then ,
// default value of int/double is 0 and
// for string/char it is NULL
pair<int, char> PAIR1;
cout << PAIR1.first << " ";
// NULL value therefore, not displayed
cout << PAIR1.second
<< endl;
// Initializing the pair during it's Declaration
pair<string, double> PAIR2("GeeksForGeeks", 1.23);
cout << PAIR2.first << " ";
cout << PAIR2.second << endl;
pair<string, double> PAIR3;
// Inserting Value in pair using make_pair function
PAIR3 = make_pair("GeeksForGeeks is Best", 4.56);
cout << PAIR3.first << " ";
cout << PAIR3.second << endl;
pair<int, int> PAIR4;
// Inserting Value in pair using {}(curly brackets)
PAIR4 = { 4, 8 };
cout << PAIR4.first << " ";
cout << PAIR4.second << endl;
return 0;
}
STL proporciona una variedad de estructuras de datos que son muy útiles en varios escenarios. Muchas estructuras de datos se basan en aplicaciones de la vida real. Es una biblioteca de clases contenedoras, algoritmos e iteradores. Es una biblioteca generalizada y, por lo tanto, sus componentes están parametrizados.
Las estructuras de datos más comunes utilizadas son:
Los contenedores o clases de contenedores almacenan objetos y datos. Hay en total siete clases de contenedores estándar de «primera clase» y tres clases de adaptadores de contenedores y solo siete archivos de encabezado que brindan acceso a estos contenedores o adaptadores de contenedores.
Nota: podemos incluir solo una biblioteca, es decir, #include <bits/stdc++.h> que incluye todas las bibliotecas STL , pero en ciertas competencias, incluir esta biblioteca puede hacer que el código sea lento. Para superar este problema, podemos agregar bibliotecas específicas para acceder a estructuras de datos particulares de STL . Además, al eliminar los elementos, se requiere tener cuidado si la estructura de datos está vacía o no. Llamar a la función de eliminación en una estructura de datos vacía genera un error. A continuación se muestran algunas estructuras de datos con su ilustración mostrada
- Vector : el principal problema al usar arrays era que teníamos que especificar el tamaño. Este inconveniente fue superado por los vectores. Los vectores funcionan internamente como arrays asignadas dinámicamente, que es la razón principal de cómo podemos agregar elementos sin especificar el tamaño del vector. Cuando el tamaño del vector se vuelve igual a la capacidad, la capacidad del vector aumenta y, por lo tanto, podemos agregar más elementos.
Archivo de cabecera:
#incluir <vector>
Sintaxis:
vector<tipo de datos> nombre_variable;
Función más común para vector:
- push_back(): Se usa para empujar el elemento al final del vector. Para un método más rápido, use emplace_back() .
- pop_back(): Se utiliza para eliminar el último elemento del vector.
- size() : Devuelve el tamaño del vector.
- clear() : Elimina todo el contenido del vector.
- erase() : Elimina el índice o los datos especificados.
- vacío() : Devuelve el valor booleano Verdadero si el vector está vacío, de lo contrario devuelve Falso.
- Iterador lower_bound (Iterator first, Iterator last, const val): lower_bound devuelve un iterador que apunta al primer elemento del rango [primero, último] que tiene un valor no inferior a ‘val’.
- Iterador upper_bound (Iterator first, Iterator last, const val): upper_bound devuelve un iterador que apunta al primer elemento del rango [first, last) que tiene un valor mayor que ‘val’.
C++
// C++ program to illustrate the
// function of vector in C++
#include <iostream>
// Header file for vector if
// <bits/stdc++.h> not included
#include <vector>
using namespace std;
// Function to print the vector
void print(vector<int> vec)
{
// vec.size() gives the size
// of the vector
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
cout << endl;
}
// Driver Code
int main()
{
// Defining a vector
vector<int> vec;
// Put all natural numbers
// from 1 to 10 in vector
for (int i = 1; i <= 10; i++) {
vec.push_back(i);
}
cout << "Initial vector: ";
// print the vector
print(vec);
// Size of vector
cout << "Vector size: " << vec.size() << "\n";
// Check of vector is empty
if (vec.empty() == false)
cout << "Is vector is"
<< " empty: False\n";
// Popping out 10 form the vector
vec.pop_back();
cout << "Vector after popping: ";
print(vec);
// Deleting the first element
// from the vector using erase()
vec.erase(vec.begin());
cout << "Vector after erase"
<< " first element: ";
print(vec);
// Clear the vector
vec.clear();
cout << "Vector after "
<< "clearing: None ";
print(vec);
// Check if vector is empty
if (vec.empty() == true)
cout << "Is vector is"
<< " empty: True\n";
}
Initial vector: 1 2 3 4 5 6 7 8 9 10 Vector size: 10 Is vector is empty: False Vector after popping: 1 2 3 4 5 6 7 8 9 Vector after erase first element: 2 3 4 5 6 7 8 9 Vector after clearing: None Is vector is empty: True
2. Pila : es la estructura de datos LIFO (último en entrar, primero en salir). Se puede implementar usando arrays, listas enlazadas y vectores. Algunos problemas como invertir un elemento o una string, verificar paréntesis, imprimir el siguiente elemento mayor, expresión de postfijo, etc., se pueden hacer usando la clase de pila en lugar de hacer que todas las funciones que podemos usar sean sus funciones incorporadas.
Archivo de cabecera:
#incluir <pila>
Sintaxis:
stack<tipo_datos> nombre_variable;
Función más común para la pila:
- push(): se utiliza para empujar el elemento en la parte superior de la pila.
- pop(): elimina el elemento superior de la pila pero no lo devuelve.
- top(): Devuelve el elemento superior de la pila.
- vacío(): devuelve un valor booleano, es decir, verdadero si la pila está vacía, de lo contrario devuelve falso.
- size(): Devuelve el tamaño de la pila.
C++
// C++ program to illustrate the
// function of stack in C++
#include <iostream>
// Header file for stack
#include <stack>
using namespace std;
// Function to print the stack
void print(stack<char> s)
{
// Loops runs till stack
// becomes empty
while (s.empty() == false) {
// Prints the top element
cout << s.top() << " ";
// Now pops the same top element
s.pop();
}
cout << "\n";
}
// Driver Code
int main()
{
// Given char array
char array[]
= { 'G', 'E', 'E', 'K',
'S', 'F', 'O', 'R', 'G',
'E', 'E', 'K', 'S' };
// Defining stack
stack<char> s;
// Check if stack is empty
if (s.empty() == true) {
cout << "Stack is currently Empty"
<< "\n";
}
else {
cout << "Stack is not empty"
<< "\n";
}
// Push elements in stack
for (int i = sizeof(array) / sizeof(array[0]) - 1;
i >= 0; i--) {
s.push(array[i]);
}
// Size of stack
cout << "Size of stack: "
<< s.size() << "\n";
// Content of stack
cout << "Stack initially: ";
print(s);
// Returning the top
// element of the stack
cout << "Top element: "
<< s.top() << "\n";
// Popping the top
// element in stack
s.pop();
cout << "Stack after 1"
<< "pop operation: ";
print(s);
// Now checking the top element
cout << "Top element after popping: "
<< s.top() << "\n";
// Size of stack
cout << "Size of stack"
<< "after popping: "
<< s.size() << "\n";
// Again checking if the
// stack is empty
if (s.empty() == true) {
cout << "Stack is currently Empty"
<< "\n";
}
else {
cout << "Stack is not empty"
<< "\n";
}
return 0;
}
Stack is currently Empty Size of stack: 13 Stack initially: G E E K S F O R G E E K S Top element: G Stack after 1pop operation: E E K S F O R G E E K S Top element after popping: E Size of stackafter popping: 12 Stack is not empty
3. Cola : es la estructura de datos Primero en entrar, primero en salir (FIFO). La razón por la que requerimos que las colas usen muchas aplicaciones prácticas de primero en entrar, primero en salir y cuando los datos no necesitan procesarse temprano. Por ejemplo, en una cola para comprar entradas para un espectáculo, el que entra primero en la cola, consigue la entrada primero. Se puede implementar usando arreglos, listas enlazadas y vectores como si fueran pilas. Algunas aplicaciones de la cola incluyen recorrido de orden de nivel en árboles y gráficos, en recursos compartidos, etc.
Archivo de encabezado:
#incluir <cola>
Sintaxis:
cola<Tipo de datos> variable_name;
Función más común para Queue:
- push(): se utiliza para empujar el elemento al final de la cola
- pop(): elimina el elemento frontal de la cola pero no lo devuelve.
- front(): Devuelve el elemento frontal de la cola, o el elemento que está primero en la línea.
- vacío(): devuelve un valor booleano, es decir, verdadero si la cola está vacía, de lo contrario devuelve falso
- back(): Devuelve el último elemento de la cola.
- size(): Devuelve el tamaño de la cola.
C++
// C++ program to illustrate the
// function of vector in C++
#include <iostream>
// Header file for queue
#include <queue>
using namespace std;
// Function to print the queue
void print(queue<char> q)
{
for (int i = 0; i < q.size(); i++) {
// Printing the front element
cout << q.front() << " ";
// Popping the front element
q.pop();
}
cout << "\n";
}
// Driver Code
int main()
{
// Given array
char array[]
= { 'G', 'E', 'E', 'K', 'S' };
// Defining queue
queue<char> q;
if (q.empty() == true) {
cout << "Queue is empty\n";
}
for (int i = 0; i < 5; i++) {
q.push(array[i]);
}
cout << "Queue Initially: ";
print(q);
// Front element
cout << "Front element: "
<< q.front() << "\n";
// Back element
cout << "Back Element: "
<< q.back() << "\n";
// Size of queue
cout << "Size of queue: "
<< q.size() << "\n";
// Empty
if (q.empty() == false) {
cout << "Queue is not empty\n";
}
return 0;
}
Queue is empty Queue Initially: G E E Front element: G Back Element: S Size of queue: 5 Queue is not empty
4.Cola de prioridad : esta estructura de datos es similar a las colas, pero el orden de prioridad se decide por una prioridad establecida por el usuario. Las funciones principales incluyen obtener el elemento de máxima prioridad, insertar, eliminar el elemento de máxima prioridad o disminuir la prioridad. Se utiliza la estructura de datos Heaps y no BST, como en BST, crear árboles es costoso que heaps, y la complejidad de los heaps es mejor. Además, los montones proporcionan la propiedad Árbol binario completo y Orden de montón que satisfacen todas las propiedades de Priority Queue. Priority Queue tiene 2 variaciones, Min Heap y Max Heap.
Problemas complejos como encontrar k elementos más grandes o más pequeños, fusionar k arrays no ordenadas, el algoritmo de ruta más corta de Dijkstra, el código Huffman para compresión, el algoritmo de Prim, etc. se pueden implementar fácilmente.
Archivo de cabecera:
#incluir <cola>
Sintaxis:
Cola de prioridad mínima: cola_prioridad<Tipo de datos> nombre_variable;
Cola de prioridad máxima: cola_prioridad <Tipo de datos, vector, mayor> nombre_variable;
Función más común para la cola de prioridad:
- push(): se utiliza para empujar el elemento en la cola
- pop(): elimina el elemento de mayor prioridad de la cola pero no lo devuelve. Elimina el elemento con prioridad máxima en el montón máximo; de lo contrario, elimina el elemento mínimo
- size(): Devuelve el tamaño de la cola.
- vacío(): devuelve un valor booleano, es decir, verdadero si la cola está vacía, de lo contrario devuelve falso.
- top() : Devuelve el elemento superior de la cola. En la cola de prioridad máxima, devuelve el valor máximo, mientras que en la cola de prioridad mínima, devuelve el valor mínimo.
C++
// C++ program to illustrate the
// function of priority queue in C++
#include <iostream>
// Header file for priority
// queue, both MIN and MAX
#include <queue>
using namespace std;
// Function to print the
// min priority queue
void print_min(
priority_queue<int, vector<int>, greater<int> > q)
{
while (q.empty() == false)
{
// Print the front
// element(MINIMUM)
cout << q.top() << " ";
// Pop the minimum
q.pop();
}
cout << "\n";
}
// Function to print the
// min priority queue
void print_max(priority_queue<int> q)
{
while (q.empty() == false)
{
// Print the front
// element(MAXIMUM)
cout << q.top() << " ";
// Pop the maximum
q.pop();
}
cout << "\n";
}
// Driver Code
int main()
{
// MIN priority queue
priority_queue<int> max_pq;
// MAX priority_queue
priority_queue<int, vector<int>, greater<int> > min_pq;
// Is queue empty
if (min_pq.empty() == true)
cout << "MIN priority "
<< "queue is empty\n";
if (max_pq.empty() == true)
cout << "MAX priority"
<< " queue is empty\n";
cout << "\n";
for (int i = 1; i <= 10; i++)
{
min_pq.push(i);
max_pq.push(i);
}
cout << "MIN priority queue: ";
print_min(min_pq);
cout << "MAX priority queue: ";
print_max(max_pq);
cout << "\n";
// Size
cout << "Size of min pq: " << min_pq.size() << "\n";
cout << "Size of max pq: " << max_pq.size() << "\n";
cout << "\n";
// Top element
cout << "Top of min pq: " << min_pq.top() << "\n";
cout << "Top of max pq: " << max_pq.top() << "\n";
cout << "\n";
// Pop the front element
min_pq.pop();
max_pq.pop();
// Queus after popping
cout << "MIN priority "
<< "queue after pop: ";
print_min(min_pq);
cout << "MAX priority "
<< "queue after pop: ";
print_max(max_pq);
cout << "\n";
// Size after popping
cout << "Size of min pq: " << min_pq.size() << "\n";
cout << "Size of max pq: " << max_pq.size() << "\n";
cout << "\n";
// Is queue empty
if (min_pq.empty() == false)
cout << "MIN priority "
<< " queue is not empty\n";
if (max_pq.empty() == false)
cout << "MAX priority queue"
<< " is not empty\n";
}
MIN priority queue is empty MAX priority queue is empty MIN priority queue: 1 2 3 4 5 6 7 8 9 10 MAX priority queue: 10 9 8 7 6 5 4 3 2 1 Size of min pq: 10 Size of max pq: 10 Top of min pq: 1 Top of max pq: 10 MIN priority queue after pop: 2 3 4 5 6 7 8 9 10 MAX priority queue after pop: 9 8 7 6 5 4 3 2 1 Size of min pq: 9 Size of max pq: 9 MIN priority queue is not empty MAX priority queue is not empty
4.Conjunto : Los conjuntos son contenedores asociativos en los que cada elemento es único. Los elementos no se pueden modificar una vez insertados en el conjunto. Un conjunto ignora los valores duplicados y todos los elementos se almacenan ordenados. Esta estructura de datos es especialmente útil cuando es necesario ordenar los elementos entrantes y no es necesario modificarlos.
Los conjuntos pueden almacenar elementos en dos órdenes, en orden creciente o en orden decreciente.
Archivo de cabecera:
#incluir <conjunto>
Sintaxis:
Orden creciente: set<Tipo de datos> variable_name;
Orden decreciente :set<Tipo de datos, mayor<Tipo de datos> > variable_name;
Función más común para Set:
- insert(): Esta función se utiliza para insertar un nuevo elemento en el Conjunto.
- begin() : esta función devuelve un iterador al primer elemento del conjunto.
- end(): Devuelve un iterador al elemento teórico que sigue al último elemento del conjunto.
- size(): Devuelve el tamaño total del conjunto.
- find(): Devuelve un iterador al elemento buscado si está presente. Si no, da un iterador hasta el final.
- count(): Devuelve el recuento de ocurrencias en un conjunto. 1 si está presente, de lo contrario 0.
- vacío(): devuelve un valor booleano, es decir, verdadero si está vacío, de lo contrario, es falso.
5. Lista : las listas almacenan datos de manera no contigua. Los elementos de la lista se pueden dispersar en los diferentes fragmentos de memoria. El acceso a cualquier índice en particular se vuelve costoso ya que se debe realizar el recorrido desde el índice conocido a ese índice en particular, por lo tanto es más lento que el vector. Las listas de tamaño cero también son válidas.
Archivo de cabecera:
#incluir <lista>
Sintaxis:
list<Tipo de datos> variable_name;
Función más común para la lista:
- push_front(elemento) : Inserta un nuevo elemento ‘elemento’ al principio de la lista.
- push_back(element) : Inserta un nuevo elemento ‘elemento’ al final de la lista.
- pop_front() : Elimina el primer elemento de la lista.
- pop_back() : Elimina el último elemento de la lista.
- front() : Devuelve el valor del primer elemento de la lista.
- back() : Devuelve el valor del último elemento de la lista.
- vacío(): devuelve un valor booleano, es decir, verdadero si está vacío, de lo contrario, es falso.
6. Mapas desordenados : suponga que tiene una caja de lápices y algunos bolígrafos. Pones algunos bolígrafos en la caja, que serían aleatorios y no ordenados a diferencia de los mapas ordenados, pero puedes acceder a cualquier bolígrafo y trabajar con él. Lo mismo ocurre con los mapas desordenados, los elementos se almacenan aleatoriamente pero puedes acceder a cualquier orden en cualquier momento. La principal diferencia entre los mapas ordenados y los mapas desordenados es la forma en que el compilador los almacena. Tiene dos argumentos, el primero se llama KEY y el otro se llama Value . Los mapas de teclas para el valor y siempre es único.
Archivo de cabecera:
#include <mapa_desordenado>
Sintaxis:
unordered_map<Tipo de datos> nombre de la variable;
Función más común para el mapa desordenado:
- count(): Devuelve valores booleanos, es decir, 1 si la clave existe, de lo contrario es falso.
- erase(key) : Devuelve la clave pasada.
- clear() : Elimina todo el mapa.
- size() : Devuelve el tamaño del mapa.
7.Mapas ordenados: suponga que tiene un estante nuevo en su habitación y algunos libros. Usted organiza los libros uno tras otro, pero después de organizar cualquier cantidad de libros, puede acceder a los libros ordenados en cualquier orden y mantener el libro en el mismo lugar cuando lo haya leído. Este es un ejemplo de un mapa. Rellena los valores uno tras otro en orden y el orden se mantiene siempre, pero puede acceder a cualquier elemento en cualquier momento. Esta estructura de datos también se implementa mediante arrays dinámicas. Al igual que los mapas desordenados, tiene dos argumentos, el primero se llama KEY y el otro se llama Value . Los mapas de teclas para el valor y siempre es único.
Archivo de cabecera:
#include <mapa_ordenado>
Sintaxis:
order_map<Tipo de datos> nombre de la variable;
Función más común para el mapa ordenado:
- count() : Devuelve valores booleanos, es decir, 1 si la clave existe, de lo contrario es falso.
- erase(key): Devuelve la clave pasada.
- clear() : Elimina todo el mapa.
- size() : Devuelve el tamaño del mapa .
Otros STL útiles son:
1.) Par: el contenedor de pares es un contenedor simple definido en el encabezado <utilidad> que consta de dos elementos de datos u objetos. Se hace referencia al primer elemento como ‘primero’ y al segundo elemento como ‘segundo’ y el orden es fijo (primero, segundo). Par se utiliza para combinar dos valores que pueden ser de tipo diferente. Pair proporciona una forma de almacenar dos objetos heterogéneos como una sola unidad. El par se puede asignar, copiar y comparar. La array de objetos asignados en un mapa o hash_map es de tipo ‘par’ por defecto en el que todos los ‘primeros’ elementos son claves únicas asociadas con sus ‘segundos’ objetos de valor. Para acceder a los elementos, usamos el nombre de la variable seguido del operador de punto seguido de la palabra clave primero o segundo.
Archivo de cabecera :
#include <utility>
Sintaxis:
pair (data_type1, data_type2) Pair_name;
Función más común para Pair:
- make_pair() : esta función de plantilla permite crear un par de valores sin escribir los tipos explícitamente.
A continuación se muestra el código para implementar la función anterior: –
C++
// C++ code
#include <iostream>
#include <utility>
using namespace std;
int main()
{
// Declaring the PAIR1 of int and char
// IF pair is not initialized then ,
// default value of int/double is 0
// and for string/char it is NULL
pair<int, char> PAIR1;
cout << PAIR1.first << " ";
// NULL value therefore, not displayed
cout << PAIR1.second
<< endl;
// Initializing the pair during it's Declaration
pair<string, double> PAIR2("GeeksForGeeks", 1.23);
cout << PAIR2.first << " ";
cout << PAIR2.second << endl;
pair<string, double> PAIR3;
// Inserting Value in pair using make_pair function
PAIR3 = make_pair("GeeksForGeeks is Best", 4.56);
cout << PAIR3.first << " ";
cout << PAIR3.second << endl;
pair<int, int> PAIR4;
// Inserting Value in pair using {}(curly brackets)
PAIR4 = { 4, 8 };
cout << PAIR4.first << " ";
cout << PAIR4.second << endl;
return 0;
}
Si tiene una array de pares y usa la función de ordenación incorporada, entonces, de manera predeterminada, ordena la array según el primer valor (es decir, obj.first) de la array de cada elemento. Para ordenar en orden descendente, pase la función de acuerdo con que desea ordenar la array.
A continuación, el código mostrará cómo ordenar la array de pares: –
C++
// C++ Code
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
bool ascending_secondValue(pair<int, int> a,
pair<int, int> b)
{
return a.second < b.second;
}
bool descending_firstValue(pair<int, int> a,
pair<int, int> b)
{
return a.first > b.first;
}
bool descending_secondValue(pair<int, int> a,
pair<int, int> b)
{
return a.second > b.second;
}
// Driver Code
int main()
{
pair<int, int> PAIR1[5];
PAIR1[0] = make_pair(1, 3);
PAIR1[1] = make_pair(13, 4);
PAIR1[2] = make_pair(5, 12);
PAIR1[3] = make_pair(7, 9);
// Using {} to insert element instead
// of make_pair you can use any
PAIR1[4]
= { 11, 2 };
cout << "Sorting array in Ascending "
"order on the basis of First value - "
<< endl;
sort(PAIR1, PAIR1 + 5);
for (int i = 0; i < 5; i++) {
cout << PAIR1[i].first << " " << PAIR1[i].second
<< endl;
}
pair<int, int> PAIR2[5];
PAIR2[0] = make_pair(1, 3);
PAIR2[1] = make_pair(13, 4);
PAIR2[2] = make_pair(5, 12);
PAIR2[3] = make_pair(7, 9);
PAIR2[4] = make_pair(11, 2);
cout << "Sorting array in Ascending "
" order on the basis of Second value - "
<< endl;
sort(PAIR2, PAIR2 + 5, ascending_secondValue);
for (int i = 0; i < 5; i++)
{
cout << PAIR2[i].first
<< " " << PAIR2[i].second
<< endl;
}
pair<int, int> PAIR3[5];
PAIR3[0] = make_pair(1, 3);
PAIR3[1] = make_pair(13, 4);
PAIR3[2] = make_pair(5, 12);
PAIR3[3] = make_pair(7, 9);
PAIR3[4] = make_pair(11, 2);
cout << "Sorting array in Descending order on the "
"basis of First value - "
<< endl;
sort(PAIR3, PAIR3 + 5, descending_firstValue);
for (int i = 0; i < 5; i++) {
cout << PAIR3[i].first << " "
<< PAIR3[i].second
<< endl;
}
pair<int, int> PAIR4[5];
PAIR4[0] = make_pair(1, 3);
PAIR4[1] = make_pair(13, 4);
PAIR4[2] = make_pair(5, 12);
PAIR4[3] = make_pair(7, 9);
PAIR4[4] = make_pair(11, 2);
cout << "Sorting array in Descending order on the "
"basis of Second value - "
<< endl;
sort(PAIR4, PAIR4 + 5, descending_secondValue);
for (int i = 0; i < 5; i++) {
cout << PAIR4[i].first << " "
<< PAIR4[i].second
<< endl;
}
return 0;
}
Conjunto ordenado: 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).
- order_of_key (k) : Número de elementos estrictamente menores que k .
- find_by_order(k) : K-ésimo elemento en un conjunto (contando desde cero).
Archivo de encabezado y espacio de nombres: –
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds;
La estructura necesaria requerida para la implementación del conjunto ordenado es:
tree < int , null_type , less , rb_tree_tag , tree_order_statistics_node_update >
Puedes leer sobre ellos en detalle aquí .
Las funciones adicionales en el conjunto ordenado además del conjunto son:
- find_by_order(k): Vuelve a un iterador al k-ésimo elemento (contando desde cero) en el conjunto en tiempo O(log n). Para encontrar el primer elemento k debe ser cero.
Supongamos que tenemos un conjunto s: {1, 5, 6, 17, 88}, entonces:
*(s.find_by_order(2)) : 3er elemento en el conjunto, es decir, 6
*(s.find_by_order(4)) : 5º elemento en el conjunto, es decir, 88
2. order_of_key(k) : Vuelve al número de elementos que son estrictamente más pequeños que nuestro elemento k en tiempo O(log n).
Supongamos que tenemos un conjunto s: {1, 5, 6, 17, 88}, entonces:
s.order_of_key(6) : El recuento de elementos estrictamente menores que 6 es 2.
s.order_of_key(25) : El recuento de elementos estrictamente menores que 25 es 4.
NOTE : ordered_set is used here as a macro given to
tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update>.
Therefore it can be given any name as macro other than ordered_set
but generally in the world of competitive programming it is commonly referred as ordered set
as it is a set with additional operations.
C++
// C++ program
#include <iostream>
using namespace std;
// Header files, namespaces,
// macros as defined above
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// ordered_set is just macro you can give any
// other name also
#define ordered_set \
tree<int, null_type, less<int>, rb_tree_tag, \
tree_order_statistics_node_update>
// Driver program to test above functions
int main()
{
// Ordered set declared with name o_set
ordered_set o_set;
// insert function to insert in
// ordered set same as SET STL
o_set.insert(5);
o_set.insert(1);
o_set.insert(2);
// Finding the second smallest element
// in the set using * because
// find_by_order returns an iterator
cout << *(o_set.find_by_order(1)) << endl;
// Finding the number of elements
// strictly less than k=4
cout << o_set.order_of_key(4) << endl;
// Finding the count of elements less
// than or equal to 4 i.e. strictly less
// than 5 if integers are present
cout << o_set.order_of_key(5) << endl;
// Deleting 2 from the set if it exists
if (o_set.find(2) != o_set.end()) {
o_set.erase(o_set.find(2));
}
// Now after deleting 2 from the set
// Finding the second smallest element in the set
cout << *(o_set.find_by_order(1)) << endl;
// Finding the number of
// elements strictly less than k=4
cout << o_set.order_of_key(4) << endl;
return 0;
}
2 2 2 5 1
Publicación traducida automáticamente
Artículo escrito por 2001guljain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA