Análisis de la complejidad temporal y espacial de los contenedores STL de C++

En este artículo, discutiremos la complejidad de tiempo y espacio de algunas clases STL de C++ .

Características de C++ STL :

• C++ tiene un tiempo de ejecución bajo en comparación con otros lenguajes de programación.
• Esto hace que STL en C++ sea ventajoso y poderoso.
• Lo que hace que STL sea poderoso es que contiene una gran variedad de clases que son implementaciones de algoritmos populares y estándar y clases predefinidas con funciones que las optimizan bien mientras se realiza una programación competitiva o se resuelven problemas.

Análisis de funciones en STL :

• Lo más importante que se requiere al usar STL es el análisis de STL.
• El análisis del problema no se puede hacer sin conocer el análisis de complejidad de la clase STL utilizada en el problema.
• Se requiere la implementación y el análisis de complejidad de STL para responder las preguntas de la entrevista.

A continuación se muestra el análisis de algunos Contenedores STL :

cola de prioridad :

Priority Queue se utiliza en muchos algoritmos populares. Priority Queue es la implementación de Max Heap de forma predeterminada. Priority Queue incluso optimiza algunas operaciones importantes.

Sintaxis:

cola_prioridad<tipo_datos> Q

Min Heap también se puede implementar mediante la siguiente sintaxis .
Sintaxis:

cola_prioridad<tipo_datos, vector<tipo_datos>, mayor<tipo_datos>> Q

La tabla que contiene la complejidad del tiempo y el espacio con diferentes funciones se muestra a continuación:

A continuación se muestra el programa C++ que ilustra la cola de prioridad:

// C++ program illustrating the
// priority queue
#include <bits/stdc++.h>
using namespace std;
 
// Function illustrating the
// priority queue
void priorityQueue()
{
    int Array[5] = { 1, 2, 3, 4, 5 };
    // Max heap
 
    int i;
    priority_queue<int> Q;
 
    for (i = 0; i < 5; i++) {
 
        // Pushes array elements to
        // priority queue and rearranges
        // to form max heap;
        Q.push(Array[i]);
    }
 
    // Maximum element in the priority
    // queue.
    cout << "The maximum element is "
         << Q.top() << endl;
 
    i = 1;
    while (Q.empty() != 1) {
        int peek = Q.top();
 
        cout << "The " << i++
             << " th max element is "
             << peek << endl;
 
        // Pops the maximum element
        // out of priority queue
        Q.pop();
    }
 
    cout << " Is priority queue "
         << "Q empty() ?" << endl
         << "check -->" << endl;
 
    // Checks whether priority
    // queue is empty
    if (Q.empty() == 1)
        cout << "The priority queue"
             << " is empty" << endl;
    else
        cout << "The priority queue"
             << " is not empty." << endl;
}
 
// Driver Code
int main()
{
    // Function Call
    priorityQueue();
 
    return 0;
}

The maximum element is 5
The 1 th max element is 5
The 2 th max element is 4
The 3 th max element is 3
The 4 th max element is 2
The 5 th max element is 1
 Is priority queue Q empty() ?
check -->
The priority queue is empty

mapa :

Es la famosa clase de STL que almacena los valores en el patrón de par clave-valor. 

• Mapea el valor usando el valor de la clave, y ninguna clave tendrá un valor diferente.
• Se puede modificar a multimapa para que funcione para las mismas claves con diferentes valores.
• El mapa se puede usar incluso para claves y valores de diferentes tipos de datos.

Sintaxis:

map<tipo_datos, tipo_datos> M

• El mapa <int, int> M es la implementación de árboles rojos y negros autoequilibrados .
• Unordered_map <int, int> M es la implementación de Hash Table que hace que
   la complejidad de las operaciones como insertar, eliminar y buscar en Theta(1) .
• El multimap<int, int> M es la implementación de Red-Black Trees , que son árboles autoequilibrados que hacen que el costo de las operaciones sea el mismo que el del mapa.
• Unordered_multimap <int, int> M se implementa igual que se implementa el mapa desordenado, que es la tabla Hash.
• La única diferencia es que realiza un seguimiento de una variable más que realiza un seguimiento del recuento de ocurrencias.
• Los pares se insertan en el mapa usando pair <int, int>(x, y) y se puede acceder a ellos usando map iterator.first y map iterator.second .
• El mapa por defecto se mantiene ordenado en base a claves y en el caso del mapa desordenado, puede estar en cualquier orden.

La tabla que contiene la complejidad del tiempo y el espacio con diferentes funciones se indica a continuación (n es el tamaño del mapa):

A continuación se muestra el programa C++ que ilustra el mapa:

// C++ program illustrating the map
 
#include <bits/stdc++.h>
using namespace std;
 
// Function illustrating the map
void Map()
{
    int i;
 
    // Declaring maps
    map<int, int> M;
    unordered_map<int, int> UM;
    multimap<int, int> MM;
    unordered_multimap<int, int> UMM;
 
    // Inserting  pairs of key
    // and value
    for (i = 101; i <= 105; i++) {
 
        // Inserted the Key and
        // value twice
        M.insert(
            pair<int, int>(i - 100, i));
        UM.insert(
            pair<int, int>(i - 100, i));
        M.insert(
            pair<int, int>(i - 100, i));
        UM.insert(
            pair<int, int>(i - 100, i));
    }
    for (i = 101; i <= 105; i++) {
 
        // Inserted the key and
        // value twice
        MM.insert(
            pair<int, int>(i - 100, i));
        UMM.insert(
            pair<int, int>(i - 100, i));
        MM.insert(
            pair<int, int>(i - 100, i));
        UMM.insert(
            pair<int, int>(i - 100, i));
    }
 
    // Iterators for accessing
    map<int, int>::iterator Mitr;
    unordered_map<int, int>::iterator UMitr;
    multimap<int, int>::iterator MMitr;
    unordered_multimap<int, int>::iterator UMMitr;
 
    // Output
    cout << "In map" << endl;
    cout << "Key"
         << " "
         << "Value" << endl;
 
    for (Mitr = M.begin();
         Mitr != M.end();
         Mitr++) {
        cout << Mitr->first << "   "
             << Mitr->second
             << endl;
    }
 
    // Unsorted and is unordered output
    cout << "In unordered_map" << endl;
    cout << "Key"
         << " "
         << "Value" << endl;
    for (UMitr = UM.begin();
         UMitr != UM.end();
         UMitr++) {
        cout << UMitr->first
             << "   "
             << UMitr->second
             << endl;
    }
 
    // Sorted output
    cout << "In multimap" << endl;
    cout << "Key"
         << " "
         << "Value" << endl;
    for (MMitr = MM.begin();
         MMitr != MM.end();
         MMitr++) {
        cout << MMitr->first
             << "   "
             << MMitr->second
             << endl;
    }
 
    // Unsorted and is unordered
    // output
    cout << "In unordered_multimap"
         << endl;
    cout << "Key"
         << " "
         << "Value" << endl;
 
    for (UMMitr = UMM.begin();
         UMMitr != UMM.end();
         UMMitr++) {
        cout << UMMitr->first
             << "   " << UMMitr->second
             << endl;
    }
 
    cout << "The erase() function"
         << " erases respective key:"
         << endl;
    M.erase(1);
 
    cout << "Key"
         << " "
         << "Value" << endl;
 
    for (Mitr = M.begin();
         Mitr != M.end(); Mitr++) {
        cout << Mitr->first
             << "   " << Mitr->second
             << endl;
    }
 
    cout << "The find() function"
         << " finds the respective key:"
         << endl;
    if (M.find(1) != M.end()) {
        cout << "Found!" << endl;
    }
    else {
        cout << "Not Found!" << endl;
    }
 
    cout << "The clear() function "
         << "clears the map:" << endl;
    M.clear();
 
    // Returns the size of the map
    cout << "Now the size is :"
         << M.size();
}
 
// Driver Code
int main()
{
    // Function Call
    Map();
 
    return 0;
}

In map
Key Value
1   101
2   102
3   103
4   104
5   105
In unordered_map
Key Value
5   105
4   104
3   103
1   101
2   102
In multimap
Key Value
1   101
1   101
2   102
2   102
3   103
3   103
4   104
4   104
5   105
5   105
In unoredered_multimap
Key Value
5   105
5   105
4   104
4   104
1   101
1   101
2   102
2   102
3   103
3   103
The erase() function erases respective key:
Key Value
2   102
3   103
4   104
5   105
The find() function finds the respective key:
Not Found!
The clear() function clears the map:
Now the size is :0

Explicación:

• m.begin(): apunta el iterador al elemento inicial.
• m.end(): apunta el iterador al elemento después del último que es teórico.

Conjunto :

• La primera propiedad útil del conjunto es que contiene solo elementos distintos, por supuesto, la variación multiconjunto puede incluso contener elementos repetidos.
• El conjunto contiene los elementos distintos de forma ordenada, mientras que el conjunto desordenado contiene elementos distintos en un orden desordenado y los mapas múltiples contienen elementos repetidos.

Sintaxis:

establecer <tipo_de_datos> S

• Set ( set<int> s ) es la implementación de árboles de búsqueda binarios .
• El conjunto desordenado ( unordered_set<int> S) es la implementación de Hash Table .
• Multiset ( multiset<int> S ) es una implementación de árboles Red-Black.
• Unordered_multiset( unordered_multiset<int> S ) se implementa igual que el conjunto desordenado, pero usa una variable adicional que realiza un seguimiento del conteo.
• La complejidad se convierte en Theta(1) y O(n) cuando se usa <set> desordenado, la facilidad de acceso se vuelve más fácil debido a la implementación de la tabla hash .

La tabla que contiene la complejidad del tiempo y el espacio con diferentes funciones se indica a continuación (n es el tamaño del conjunto):

 A continuación se muestra el conjunto ilustrativo del programa C++:

// C++ program illustrating the set
#include <bits/stdc++.h>
using namespace std;
 
// Function illustrating the set
void Set()
{
    // Set declaration
    set<int> s;
    unordered_set<int> us;
    multiset<int> ms;
    unordered_multiset<int> ums;
    int i;
 
    for (i = 1; i <= 5; i++) {
 
        // Inserting elements
        s.insert(2 * i + 1);
        us.insert(2 * i + 1);
        ms.insert(2 * i + 1);
        ums.insert(2 * i + 1);
        s.insert(2 * i + 1);
        us.insert(2 * i + 1);
        ms.insert(2 * i + 1);
        ums.insert(2 * i + 1);
    }
 
    // Iterator to access values
    // in set
    set<int>::iterator sitr;
    unordered_set<int>::iterator uitr;
    multiset<int>::iterator mitr;
    unordered_multiset<int>::iterator umitr;
 
    cout << "The difference: "
         << endl;
    cout << "The output for set "
         << endl;
 
    for (sitr = s.begin();
         sitr != s.end(); sitr++) {
        cout << *sitr << " ";
    }
    cout << endl;
 
    cout << "The output for "
         << "unordered set " << endl;
 
    for (uitr = us.begin();
         uitr != us.end(); uitr++) {
        cout << *uitr << " ";
    }
    cout << endl;
 
    cout << "The output for "
         << "multiset " << endl;
 
    for (mitr = ms.begin();
         mitr != ms.end();
         mitr++) {
        cout << *mitr << " ";
    }
    cout << endl;
 
    cout << "The output for "
         << "unordered multiset "
         << endl;
 
    for (umitr = ums.begin();
         umitr != ums.end();
         umitr++) {
        cout << *umitr << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    // Function Call
    Set();
 
    return 0;
}

The difference: 
The output for set 
3 5 7 9 11 
The output for unordered set 
11 9 7 3 5 
The output for multiset 
3 3 5 5 7 7 9 9 11 11 
The output for unordered multiset 
11 11 9 9 3 3 5 5 7 7

pila :

Es una estructura de datos que sigue la regla Last In First Out (LIFO) , esta clase de STL también se
usa en muchos algoritmos durante sus implementaciones. 
Por ejemplo, muchas soluciones recursivas utilizan una pila del sistema para realizar un seguimiento de las llamadas pendientes de funciones recursivas; lo mismo puede implementarse utilizando la pila STL de forma iterativa.

Sintaxis:

pila<tipo_datos> A

• Se implementa utilizando la implementación de lista enlazada de una pila.

A continuación se muestra el programa C++ que ilustra la pila:

// C++ program illustrating the stack
#include <bits/stdc++.h>
using namespace std;
 
// Function illustrating stack
void Stack()
{
    stack<int> s;
    int i;
    for (i = 0; i <= 5; i++) {
        cout << "The pushed element"
             << " is " << i << endl;
        s.push(i);
    }
 
    // Points to top element of stack
    cout << "The top element of the"
         << " stack is: " << s.top()
         << endl;
 
    // Return size of stack
    cout << "The size of the stack"
         << " is: " << s.size()
         << endl;
 
    // Pops the elements of the
    // stack in the LIFO manner
    // Checks whether the stack
    // is empty or not
    while (s.empty() != 1) {
        cout << "The popped element"
             << " is " << s.top()
             << endl;
        s.pop();
    }
}
 
// Driver Code
int main()
{
    // Function Call
    Stack();
 
    return 0;
}

The pushed element is 0
The pushed element is 1
The pushed element is 2
The pushed element is 3
The pushed element is 4
The pushed element is 5
The top element of the stack is: 5
The size of the stack is: 6
The popped element is 5
The popped element is 4
The popped element is 3
The popped element is 2
The popped element is 1
The popped element is 0

cola :

Es una estructura de datos que sigue la regla First In First Out (FIFO) .

• La inclusión de la cola de clase STL de cola en el código reduce las llamadas a funciones para operaciones básicas.
• La cola se usa a menudo en recorridos BFS de árboles y gráficos y también en muchos algoritmos populares. 
• La cola en STL se implementa mediante una lista enlazada. 

Sintaxis:

cola<tipo_datos> Q

Tabla que contiene la complejidad del tiempo y el espacio con diferentes funciones que se detallan a continuación:

A continuación se muestra el programa C++ que ilustra la cola:

// C++ program illustrating the queue
#include <bits/stdc++.h>
using namespace std;
 
// Function illustrating queue
void Queue()
{
    queue<int> q;
    int i;
    for (i = 101; i <= 105; i++) {
 
        // Inserts into the queue
        // in the FIFO manner
        q.push(i);
 
        cout << "The first and last"
             << " elements of the queue "
             << "are " << q.front()
             << " " << q.back()
             << endl;
    }
 
    // Check whether the queue is
    // empty or not
    while (q.empty() != 1) {
 
        // Pops the first element
        // of the queue
        cout << "The Element popped"
             << " following FIFO is "
             << q.front() << endl;
        q.pop();
    }
}
 
// Driver Code
int main()
{
    // Function Call
    Queue();
 
    return 0;
}

The first and last elements of the queue are 101 101
The first and last elements of the queue are 101 102
The first and last elements of the queue are 101 103
The first and last elements of the queue are 101 104
The first and last elements of the queue are 101 105
The Element popped following FIFO is 101
The Element popped following FIFO is 102
The Element popped following FIFO is 103
The Element popped following FIFO is 104
The Element popped following FIFO is 105

Vector :

Vector es la implementación de arrays dinámicas y utiliza new para la asignación de memoria en el montón .
Sintaxis:

vector<int>A

 Los vectores bidimensionales también se pueden implementar usando la siguiente sintaxis:

Sintaxis:

vector<vector<int>> A

La tabla que contiene la complejidad del tiempo y el espacio con diferentes funciones se muestra a continuación:

A continuación se muestra el programa C++ que ilustra el vector:

// C++ program illustrating vector
 
#include <bits/stdc++.h>
using namespace std;
 
// Function displaying values
void display(vector<int> v)
{
    for (int i = 0;
         i < v.size(); i++) {
        cout << v[i] << " ";
    }
}
 
// Function illustrating vector
void Vector()
{
    int i;
    vector<int> v;
    for (i = 100; i < 106; i++) {
 
        // Inserts an element in vector
        v.push_back(i);
    }
 
    cout << "The vector after "
         << "push_back is :" << v.size()
         << endl;
    cout << "The vector now is :";
    display(v);
    cout << endl;
 
    // Deletes an element at the back
    v.pop_back();
    cout << "The vector after "
         << "pop_back is :" << v.size()
         << endl;
    cout << "The vector now is :";
    display(v);
    cout << endl;
 
    // Reverses the vector
    reverse(v.begin(), v.end());
    cout << "The vector after "
         << "reversing is :" << v.size()
         << endl;
 
    cout << "The vector now is :";
    display(v);
    cout << endl;
 
    // Sorts vector using Quick Sort
    sort(v.begin(), v.end());
    cout << "The vector after "
         << "sorting is :" << v.size()
         << endl;
 
    cout << "The vector now is :";
    display(v);
    cout << endl;
 
    // Erases ith position element
    v.erase(v.begin() + 2);
 
    cout << "The size of vector "
         << "after erasing at position "
            "3 is :"
         << v.size() << endl;
    cout << "The vector now is :";
    display(v);
    cout << endl;
 
    // Deletes the vector completely
    v.clear();
 
    cout << "The size of the vector"
         << " after clearing is :"
         << v.size() << endl;
    cout << "The vector now is :";
    display(v);
    cout << endl;
}
 
// Driver Code
int main()
{
    // Function Call
    Vector();
 
    return 0;
}

The vector after push_back is :6
The vector now is :100 101 102 103 104 105 
The vector after pop_back is :5
The vector now is :100 101 102 103 104 
The vector after reversing is :5
The vector now is :104 103 102 101 100 
The vector after sorting is :5
The vector now is :100 101 102 103 104 
The size of vector after erasing at position 3 is :4
The vector now is :100 101 103 104 
The size of the vector after clearing is :0
The vector now is :