Un Vector en C++ puede cambiar su tamaño cuando se agregan más elementos. También permite la eliminación de elementos.
A continuación se muestra una idea muy básica cuando la array se llena y el usuario desea agregar un elemento.
1) Cree una memoria de mayor tamaño en la memoria del montón (por ejemplo, una memoria de doble tamaño).
2) Copie los elementos de la memoria actual a la nueva memoria.
3) Ahora se agrega un nuevo elemento porque ahora hay más memoria disponible.
4) Eliminar la memoria antigua.
Sin embargo, la implementación real de la biblioteca puede ser más compleja. Si creamos una nueva array de doble tamaño cada vez que la array actual se llena (o está a punto de llenarse) y copiamos los elementos actuales a una nueva array de doble tamaño, obtenemos una complejidad de tiempo amortizada como O(1). Por lo tanto, una operación de inserción en particular puede ser costosa, pero la complejidad del tiempo general sigue siendo O(1). Consulte Análisis de algoritmo | Juego 5 (Introducción al análisis amortizado) como prueba. Entonces, la complejidad del tiempo de push_back() es O(1).
CPP
// CPP program to illustrate push_back()
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> myvector{ 1, 2, 3, 4, 5 };
myvector.push_back(6);
// Vector becomes 1, 2, 3, 4, 5, 6
for (auto x : myvector)
cout << x << " ";
}
Producción :
1 2 3 4 5 6
¿Cuál es la complejidad temporal de erase() en vector()?
Dado que borrar un elemento requiere mover otros elementos (para garantizar el acceso aleatorio), la complejidad del tiempo de borrado es O(n).
CPP
// CPP program to illustrate
// working of erase() function
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> myvector{ 1, 2, 3, 4, 5 };
auto it = myvector.begin();
myvector.erase(it);
// Printing the Vector
for (auto x : myvector)
cout << x << " ";
return 0;
}
Producción :
2 3 4 5