Contenedor vector de C++

En C++,vectores uno de los contenedores STL más utilizados.

vectorEn esencia es unarray dinámico con expansión automática, en comparación con los arrays tradicionales, vector no requiere gestionar la memoria manualmente y puede expandirse automáticamente según la cantidad de elementos.

Debido a que vector tiene:

  • Almacenamiento en memoria contigua
  • Acceso aleatorio rápido
  • Ecosistema STL completo
  • Amigable con la caché (Cache Friendly)

Por lo tanto, en el desarrollo moderno de C++, la mayoría de los escenarios de almacenamiento de datos secuenciales priorizan el uso de vector.

Características principales de vector

  • Tamaño dinámico:vector puede expandirse y reducirse automáticamente.
  • Memoria contigua:Los elementos se almacenan de forma contigua en la memoria, lo que permite una eficiencia de acceso muy alta.
  • Acceso aleatorio:Permite acceder rápidamente a los elementos mediante índice, con una complejidad temporal de O(1).
  • Gestión automática de memoria:No es necesario usar malloc/free manualmente.
  • Compatibilidad con iteradores:Se puede usar convenientemente con los algoritmos de STL.

¿Por qué vector es muy rápido?

Los elementos de vector están dispuestos de forma contigua en la memoria:

[1][2][3][4][5]

Esta disposición es muy amigable con la caché de la CPU.

Cuando la CPU lee el primer elemento, suele precargar también los datos posteriores en la caché, por lo que recorrer un vector suele ser muy rápido.

Esta es también la razón por la que en muchos casos:

vector 比 list 更快

aunque list tenga una complejidad de eliminación teóricamente menor.

Usar vector

Antes de usar vector, es necesario incluir el archivo de cabecera:

#include <vector>

Crear un vector

Crear un vector vacío:

std::vector<int>vec;

Especificar el tamaño inicial:

std::vector<int>vec(5);

El código anterior crea 5 elementos con valor predeterminado 0.

Especificar el valor inicial:

std::vector<int>vec(5, 10);

Resultado de la creación:

[10, 10, 10, 10, 10]

Usar lista de inicialización:

std::vector<int>vec = {1, 2, 3, 4};

Añadir elementos

Usarpush_back()para añadir un elemento al final:

vec.push_back(100);

La complejidad temporal promedio de añadir un elemento al final de vector es:

O(1)

Acceder a elementos

Acceder usando índice:

int x = vec[0];

Usarat()： 

int y = vec.at(1);

Diferencia:

  • []No verifica límites, es más rápido.
  • at()Sí verifica límites, es más seguro.

Obtener el tamaño

vec.size();

Devuelve el número actual de elementos.

Diferencia entre size y capacity

Este es uno de los conceptos más importantes de vector.

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

La salida puede ser:

2
4
  • size：Número actual de elementos.
  • capacity：Capacidad de memoria actualmente asignada.

capacity normalmente es mayor o igual que size.

Esto se debe a que vector reserva más espacio por adelantado para reducir expansiones frecuentes.

Mecanismo de expansión de vector

Cuando el espacio de vector es insuficiente, ocurre una expansión:

  1. Solicitar más memoria
  2. Copiar los elementos antiguos
  3. Liberar la memoria antigua

Este proceso tiene un costo elevado.

Por ejemplo:

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

Pueden ocurrir múltiples reasignaciones de memoria.

reserve(): preasignar espacio

Para evitar expansiones frecuentes, se puede asignar memoria por adelantado:

std::vector<int>vec;

vec.reserve(1000000);

Esto permite reducir:

  • Reasignación de memoria
  • Copia de elementos
  • Pérdida de rendimiento

Esta es una técnica de optimización muy importante en el desarrollo de ingeniería.

Recorrer un vector

Usando índice

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

Usando iteradores

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Bucle for basado en rango

for (int element : vec) {
    std::cout << element << " ";
}

Eliminar elementos

Eliminar el tercer elemento:

vec.erase(vec.begin() + 2);

Nota:

Cuando vector elimina un elemento en el medio, los elementos posteriores se desplazan hacia adelante.

Por ejemplo:

1 2 3 4 5

删除 2 后：

1 3 4 5

donde:

3 4 5

todos deben moverse de posición.

Por lo tanto:

erase() 的时间复杂度为 O(n)

Escenarios en los que vector no es adecuado

  • Inserciones frecuentes al inicio
  • Eliminaciones frecuentes en el medio
  • Expansión frecuente con objetos muy grandes

Por ejemplo:

vec.insert(vec.begin(), 100);

Esta es una operación lenta.

Invalidación de iteradores

Después de la expansión de vector, las direcciones de memoria originales pueden invalidarse.

Por ejemplo:

std::vector<int>vec = {1, 2, 3};

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

Aquíitpuede haberse invalidado.

Porque push_back() puede provocar una reasignación de memoria.

Es uno de los errores más comunes de vector.

Advertencias sobre clear()

vec.clear();

clear() solo vacía los elementos:

  • size pasa a ser 0
  • capacity puede conservarse

Es decir:

clear() 不一定释放内存

Si se desea liberar la memoria:

std::vector<int>().swap(vec);

o:

vec.shrink_to_fit();

push_back y emplace_back

En el C++ moderno se recomienda usar:

emplace_back()

Por ejemplo:

vec.push_back(Person("Tom", 20));

puede generar objetos temporales.

Mientras que:

vec.emplace_back("Tom", 20);

construye el objeto directamente en el interior de vector.

Normalmente es más eficiente.

Diferencias entre vector y array

Característica Array vector
Tamaño fijo Sí no
Expansión automática no Sí
Memoria contigua Sí Sí
Acceso aleatorio Rápido Rápido
Compatibilidad con STL Escasa Completa
Acceso seguro Ninguno at()

Complejidad de las operaciones comunes de vector

Operación Complejidad temporal
Acceso aleatorio O(1)
push_back O(1) promedio
Eliminación al final O(1)
Inserción al inicio O(n)
Eliminación en el medio O(n)
clear O(n)

Ejemplo: gestión de calificaciones de estudiantes

Ejemplo


#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int>scores = {85, 90, 78, 92};
    scores.push_back(88);
    std::cout << "Todas las calificaciones: ";
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;
    int total = std::accumulate(scores.begin(), scores.end(), 0);
    double average = total * 1.0 / scores.size();
    std::cout << "Calificación promedio: " << average << std::endl;
    scores.erase(scores.begin() + 2);
    std::cout << "Calificaciones después de eliminar: ";
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;

    return 0;
}

El resultado de salida es el siguiente:

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88

Resumen

vector es una de las estructuras de datos más importantes y utilizadas en el C++ moderno.

Sus ventajas principales:

  • Expansión dinámica
  • Memoria contigua
  • Acceso aleatorio rápido
  • Amigable con la caché
  • Ecosistema STL completo

Pero también hay que tener en cuenta:

  • Costo de rendimiento de la expansión
  • Baja eficiencia en la eliminación en el medio
  • Problema de invalidación de iteradores

Para la gran mayoría de escenarios de almacenamiento secuencial:

vector 通常都是默认首选容器
Otras extensiones