🧱 vector (arreglo dinámico)
Estructura de datos · Viene en la librería estándar (STL) · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 03 de la Ruta de Aprendizaje.
Qué hace
Un arreglo que crece y se achica solo. Es el contenedor por defecto en competencia: guarda los elementos en memoria contigua, así que acceder por índice es instantáneo y recorrerlo es rapidísimo.
Operaciones y costo
| Operación | Costo | Notas |
|---|---|---|
| v[i] (acceso) | O(1) | requiere 0 ≤ i < size(); fuera del rango es comportamiento indefinido |
| push_back | O(1) amortizado | puede realocar cuando se llena |
| pop_back | O(1) | requiere un vector no vacío |
| insert / erase en el medio | O(n) | hay que correr todo lo de atrás |
| size / empty | O(1) | |
| sort(v.begin(), v.end()) | O(n log n) |
Por dentro
Los elementos están contiguos en memoria. size() cuenta elementos existentes; capacity() cuenta cuántos caben antes de necesitar otro bloque. Al crecer puede mover o copiar los elementos a un bloque mayor; el factor de crecimiento depende de la implementación, no se exige duplicarlo. Por eso push_back es O(1) amortizado, aunque una inserción concreta pueda costar O(n).
Cuándo usarla
Siempre que necesites una lista con acceso por posición — que es casi siempre. Si insertas o borras por ambos extremos, mira deque; si necesitas mantener orden con inserciones intercaladas, set.
Cómo se usa (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n); // n enteros, todos en 0
for (int i = 0; i < n; i++) cin >> v[i];
v.push_back(42); // crece por el final
cout << v.size() << " " << v.back() << "\n";
v.pop_back();
vector<vector<int>> matriz(3, vector<int>(4, 0)); // 3x4 llena de ceros
sort(v.begin(), v.end());
for (int x : v) cout << x << " ";
cout << "\n";
}
⚠️ Notas
Ejemplo de tamaño y capacidad. Un vector vacío tiene tamaño 0; tras reserve(5) conserva tamaño 0 y tiene capacidad de al menos 5. push_back(7) crea el primer elemento: tamaño 1, v[0]=7. resize(3) agrega dos ceros: {7,0,0}. Solo entonces existen los índices 0, 1 y 2. reserve permite planificar inserciones, no usar índices que aún no existen.
Contrato. front, back y pop_back requieren al menos un elemento. v[i] fuera de rango tiene comportamiento indefinido: puede fallar, corromper datos o parecer funcionar. v.at(i) comprueba el rango y lanza una excepción si no existe. Una realocación invalida iteradores, referencias y punteros a los elementos.
Memoria. Con int de 4 bytes, un millón de elementos ocupa unos 4 MB; mil millones, unos 4 GB. Cuenta la capacidad reservada y las demás estructuras, no solo size(). En el programa, con entrada 3 y 9 2 9, la primera línea es 4 42 y la segunda contiene 2 9 9: ordenar conserva las repeticiones.