🧱 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ónCostoNotas
v[i] (acceso)O(1)requiere 0 ≤ i < size(); fuera del rango es comportamiento indefinido
push_backO(1) amortizadopuede realocar cuando se llena
pop_backO(1)requiere un vector no vacío
insert / erase en el medioO(n)hay que correr todo lo de atrás
size / emptyO(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.

🔗 Relacionados