El contenedor vector

Introducción

La forma de trabajar con vectores en C++ que hemos visto es una herencia del Lenguaje C. Muchas características del C no son deseables, pero se mantienen por retrocompatibilidad.

Entre otros, algunos inconvenientes de un vector al estilo C:

  • No conoce su propio tamaño.

  • No dispone de herramientas para avisar si durante la ejecución de un programa se accede fuera de los límites del vector.

    Es responsabilidad del programador no acceder a un elemento fuera de los límites del vector.

    En los ejemplos de funciones, hemos visto que necesitamos añadir un parámetro con el tamaño para que la función se ejecute correctamente.

  • El tamaño es fijo. No podemos variarlo durante la ejecución.

    Tenemos que optar por dar un tamaño suficiente de antemano (como en el ejemplo del cálculo de la edad media de los alumnos). Esto supone, en general, un desperdicio de recursos de memoria.

Nota

En C podemos trabajar con vectores de tamaño variable utilizando punteros mediante asignación dinámica de memoria. ¡Es una alternativa compleja y fuente común de errores! No lo estudiamos en este curso.

Definición

Un vector es una clase genérica que permite almacenar una colección de objetos del mismo tipo.

Al igual que con los vectores estilo C:

  • podemos acceder a los elementos del contenedor vector usando un índice y el operador de indexación [].

  • los elementos ocupan posiciones contiguas en memoria

Para usar el contenedor vector debemos añadir a nuestro programa la cabecera #include <vector>.

Dado que es una clase genérica, debemos indicar en nuestro programa el tipo de dato de los elementos de la colección. Esto lo hacemos usando la siguiente sintaxis:

std::vector<T> identificador;

donde T, es la plantilla que indica el tipo de dato.

Por ejemplo:

std::vector<int> v;           // Vector de enteros
std::vector<string> cadenas;  // Vector de cadenas

Obsérvese que vector pertenece al espacio de nombres std, por lo que si deseamos evitar el especificador de ámbito std:: deberemos utilizar previamente, por ejemplo, using namespace std;.

Inicialización

  • Vector v vacío

    vector<T> v;

  • Vector v inicializado con los valores x, y y z.

    vector<T> v{x, y, z};     // Preferible
vector<T> v = {x, y, z};  // Equivalente

  • Vector v de n valores inicializados a val

    vector<T> v(n, val)

  • Vector v de n valores inicializados a un valor por defecto. Para tipos de datos T comunes el valor por defecto es 0.

    vector<T> v(n)

  • Vector v inicializado con los elementos del vector w

    vector<T> v(w);    // Preferible
vector<T> v = w;   // Equivalente

Tamaño: size()

Para poder almacenar los elementos de una colección de objetos de forma dinámica en tiempo de ejecución, los contenedores de la STL deben gestionar su tamaño y capacidad.

Al igual que otros contenedores, para conocer el tamaño, vector dispone de la función miembro size(), que devuelve el número de elementos que contiene. Su prototipo es:

size_type size();

Para usar una función miembro asociada a una clase se utiliza el operador ., cuya sintaxis es la siguiente:

identificador.funcion_miembro(parametros)

Veamos en acción las diferentes alternativas de inicialización y a la función miembro size():

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  // v1 es un vector de 5 elementos enteros con valor 0
  vector<int> v1(5);
  cout << "Número de elementos de v1: " << v1.size() << endl;
  // v2 es un vector de 1 elemento entero con valor 5
  vector<int> v2{5};
  cout << "Número de elementos de v2: " << v2.size() << endl;
  // v3 es un vector de 5 elementos enteros inicializados a 1
  vector<int> v3(5, 1);
  cout << "Elementos de v3:\n";
  for (int i = 0 ; i != v3.size(); ++i)
    cout << v3[i] << endl;
  // v4 es un vector de 2 elementos enteros con valores 5 y 1
  vector<int> v4{5, 1};
  cout << "Elementos de v4:\n";
  for (int i = 0 ; i < v4.size(); ++i)
    cout << v4[i] << endl;
  // v5 es un vector incializado con los valores de v4
  vector<int> v5(v4);
  cout << "Elementos de v5:\n";
  for (int i = 0 ; i < v5.size(); ++i)
    cout << v5[i] << endl;
}

Edita, compila y ejecuta el código

Nota

En los bucles se ha utilizado en las condiciones las variantes != y <. Ambas opciones son habituales encontrarlas en la bibliografía y, como pasa con otros temas, existe controversia acerca de cual es preferible.

El tipo de dato size_t

Cada contenedor de la STL permite conocer su tamaño utilizando un tipo de dato adecuado a sus características. Para trabajar de forma genérica, todos ellos utilizan un alias (typedef) llamado size_type.

Para el método size() de la clase vector, el alias size_type es un tipo de dato entero sin signo llamado size_t.

El tipo size_t permite almacenar el tamaño en bytes del mayor objeto creable en memoria en el sistema donde se está ejecutando el programa.

Si el programa anterior se compila con la opción de avisos habilitados, como está por defecto en el compilador asociado a Code::Blocks, se generarán mensajes del tipo:

warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type'

El aviso nos informa de que estamos comparando en la expresión i < v.size() dos variables enteras de distinto tipo:

  • una con signo, i,

  • otra sin signo, el valor devuelto por v.size().

En general, en el contexto de la asignatura, podemos obviar el aviso, pero una alternativa más elegante es usar para el contador el tipo de dato entero sin signo size_t.

Por ejemplo:

for (size_t i = 0 ; i < v5.size(); ++i)

La función empty()

Si lo único que se desea es saber si el vector tiene o no elementos, la función miembro empty() devuelve true cuando está vacío.

Su prototipo es:

bool empty();

Aunque las líneas de código

if (v.size() == 0)

y

if (v.empty())

son equivalentes, es preferible usar empty() por dos razones:

  • código más autoexplicativo

  • para ciertos tipos de contenedores es más eficiente

Añadir un elemento al final del vector: push_back()

Uno de los inconvenientes de los vectores al estilo C es que debemos elegir de antemano el tamaño del vector al crear el programa.

El contenedor vector permite variar los elementos de forma dinámica, es decir, en tiempo de ejecución, a través de algunas de sus funciones miembro. Entre éstas destaca la función push_back(), cuyo prototipo es:

void push_back(const T&);

La función push_back() permite añadir al final de la colección un nuevo dato.

El argumento const T& nos indica que:

  • esta función recibe una referencia del valor de tipo T que queremos añadir al contenedor

  • al ser const, garantiza que no modificará su valor

La razón del diseño para pasar una referencia y no utilizar un paso por valor es evidente: si el contenedor va a almacenar objetos de gran tamaño en memoria, nos ahorramos la copia, con las ventajas en tiempo de ejecución y ahorro de memoria asociadas.

Ejemplo: añadir a un vector vacío los 10 primeros enteros

En el siguiente ejemplo, se añaden progresivamente los enteros del 0 al 9 a un vector inicialmente vacío:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  vector<int> v; //vector vací­o de enteros

  for (int i = 0; i < 10; ++i)
    v.push_back(i);  // Añade de forma progresiva el valor i

  for (size_t i = 0; i < v.size(); ++i)
    cout << v[i] << " ";  //Acceso a los elementos como en C
  cout << endl;
}

Edita, compila y ejecuta el código

Ejemplo: cálculo de la media de las edades de alumnos

Retomamos el programa que calcula la media de las edades de los alumnos, visto en el apartado de de vectores estilo C. Ahora, con vector no es necesario prefijar un tamaño máximo para el vector de alumnos. En cada ejecución del programa, el vector tendrá el tamaño justo y necesario.

#include <iostream>
#include <vector>
using namespace std;
int main() // Calcula la edad media de una clase de alumnos
{
  int num_alumnos;
  do
  {
    cout << "Introduzca el número de alumnos: ";
    cin >> num_alumnos;
    if (num_alumnos < 1)
      cout << "\n\nERROR: el número de alumnos debe ser positivo.\n\n";
  }while (num_alumnos < 1);
  vector<int> edad;
  for (int i = 0; i < num_alumnos; ++i)
  {
    int valor;
    cout << "\nIntroduce la edad del alumno " << i+1 << ": ";
    cin >> valor;
    edad.push_back(valor);
  }
  double media = 0.;
  for (size_t i = 0; i < edad.size(); ++i)
    media += edad[i];
  media /= num_alumnos;
  cout << "La edad media es " << media << endl;
}

Edita, compila y ejecuta el código

La capacidad: capacity()

La clase vector diferencia claramente entre el tamaño de la colección, es decir, cuantos elementos están almacenados en el vector y su capacidad. La capacidad de un vector hace referencia al número máximo de elementos que podría albergar en un instante de ejecución dado. El tamaño del tipo de dato de vector multiplicado por su capacidad determina la reserva de memoria que se habrá solicitado al Sistema Operativo.

El símil con un tonel de vino aplica. El tonel puede tener una capacidad de, por ejemplo, 125 litros. Sin embargo, puede que en un instante dado solo tenga almacenados 37 litros. La función miembro size() devolvería en este caso el valor 37.

La capacidad puede obtenerse a través de la función miembro capacity(), cuyo prototipo es:

size_type capacity();

Gestión dinámica de la capacidad

Cuando invocamos a la función push_back() (entre otras) puede ocurrir:

  • La capacidad es mayor que el tamaño

    En este caso, basta añadir en memoria el nuevo objeto tras el último.

  • La capacidad es igual al tamaño

    ¡No queda espacio reservado en memoria para el nuevo objeto!

Nótese que en el segundo escenario se debe:

  1. solicitar al Sistema Operativo una nueva zona de memoria con mayor capacidad

  2. copiar el vector actual en esa nueva área de memoria

  3. copiar en la nueva zona de memoria el nuevo valor tras el último

  4. liberar el bloque de memoria antigua, para que otros objetos puedan utilizarla

Es importante destacar que toda esta operativa se gestiona de forma transparente al programador.

Cómo se gestiona el aumento de capacidad depende de la implementación del compilador y, por supuesto, el programador tampoco tiene que preocuparse de esta labor. Una estrategia típica es duplicar la capacidad cada vez que se llena el vector.

El siguiente ejemplo visualiza para unos pocos elementos como va variando la capacidad cada vez que se llena el vector. Nótese que inicialmente, cuando el vector está vacío, la capacidad es nula, es decir, no se ha solicitado aún al Sistema Operativo reserva de memoria para ningún elemento.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  vector<int> valores;
  cout << "SIZE CAPACITY\n";
  cout << valores.size() << " " << valores.capacity() << endl;

  for (int i = 0; i < 17; ++i)
  {
    if (valores.size() == valores.capacity())
      cout << "Aumento de la capacidad!\n";
    valores.push_back(i);
    cout << valores.size() << " " << valores.capacity() << endl;
  }
}

Edita, compila y ejecuta el código

Acceso a los elementos de un objeto vector

Además del operador de indexación [size_t indice], para acceder individualmente a los elementos, puede utilizarse la función miembro at(size_t indice), cuyo prototipo es:

T& at(size_t)
// o
const T& at(size_t)

Ejemplo:

for (size_t i = 0; i < edad.size(); ++i)
  media += edad.at(i);

La ventaja de usar at() en lugar del operador [] es que, en caso de acceso a una posición inexistente, el programa lanzará una excepción.

La desventaja es que es una alternativa más lenta, pues supone verificar en cada acceso a un elemento del vector si este existe, es decir, si el índice es inferior a size(). En programas con gran carga computacional, como un procesamiento de imágenes, esto puede ser inasumible. Además, si el algoritmo está bien construido, el lanzamiento de una excepción es una situación que no debería suceder en este contexto. Por ello, suele ser una alternativa utilizada en fase de desarrollo de un programa. Cuando está suficientemente verificado el código, se construye la versión rápida con el operador de indexación [].

Veamos en el siguiente ejemplo las dos alternativas de acceso en un escenario donde se sobrepasa el límite del vector. Este ejemplo reproduce un error habitual, que usa en la condición del bucle for el operador <= en lugar del operador <.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  const int num_elementos = 10;
  vector<double> v(num_elementos);

  for (int i = 0; i <= num_elementos; ++i)
  {
    v[i] = i;
    cout << v[i] << endl;
  }

  for (int i = 0; i <= num_elementos; ++i)
  {
    v.at(i) = i;
    cout << v[i] << endl;
  }
}

Edita, compila y ejecuta el código

Muy probablemente, el primer bucle se ejecutará sin aparente error. Sin embargo, para el segundo bucle aparecerá un mensaje similar a:

terminate called after throwing an instance of 'std::out_of_range' what():  vector::_M_range_check: __n (which is 10) >= this->size() (which is 10)

Acceso al primer y último elemento

En muchos algoritmos, como los que usan pilas y colas, es necesario el acceso al primer y al último elemento de un contenedor.

En el caso del contenedor vector:

  • back(), devuelve una referencia al último elemento

  • front(), devuelve una referencia al primer elemento

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
  vector<int> v{0, 1, 2, 3, 4, 5};
  cout << v.front() << " " << v.back() << endl;  // Salida 0 y 5
}

Edita, compila y ejecuta el código

Eliminar el último elemento del vector: pop_back()

La función miembro pop_back(), cuya signatura es:

void pop_back();

permite eliminar el último elemento de un vector.

Por tanto, es la función miembro dual de push_back(). Nótese que, desde el punto de vista algorítmico, estas dos funciones permiten manejar un vector como si de una pila se tratase: «último en entrar, primero en salir».

El siguiente ejemplo vacía un vector usando iteradamente pop_back() a la vez que rellena otro usando push_back(), obteniendo los elementos en orden inverso.

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
  vector<int> v{0, 1, 2, 3, 4, 5};
  vector<int> w;

  while (!v.empty())
  {
    w.push_back(v.back());
    v.pop_back();
  }

  for (size_t i = 0; i < w.size(); ++i)
    cout << w[i] << " ";
  cout << endl;
}

Edita, compila y ejecuta el código

Debe tenerse en cuenta que por razones de eficiencia pop_back() no verifica si el vector está vacío. Si se invoca pop_back() en un vector vacío los resultados son impredecibles.

Véase la salida de este programa que no tiene cuidado en el uso de pop_back().

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
  vector<int> v{1};

  v.pop_back();
  cout << "Tam: " << v.size() << endl;
  v.pop_back();
  cout << "Tam: " << v.size() << endl;
  for (size_t i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
}

Edita, compila y ejecuta el código

Nótese que cada vez que se invoca a pop_back() se decrementa en uno el tamaño del vector. Cuando el tamaño es 0, utilizar pop_back() decrementa en 1 ese valor que, al corresponder a una variable sin signo size_t, genera el mayor valor posible sin signo almacenable.

Otras formas de modificar el contenido de vector

Tanto push_back() como pop_back() tienen un tiempo teórico asociado de ejecución constante. Sin embargo, si lo que deseamos es insertar o eliminar un elemento situado en una posición intermedia, la complejidad computacional varía en función de la posición, pues en ambos casos necesitamos desplazar todos los elementos desde esa posición hasta el último elemento para dejar el hueco para el nuevo elemento (si insertamos) o para cubrirlo (si eliminamos).

Algunas funciones miembro adicionales que permiten alterar el contenido son las siguientes:

  • clear(), borra todos los elementos del contenedor. La capacidad no varía.

  • insert(), permite añadir elementos intermedios.

  • erase(), permite borrar elementos intermedios.

  • resize(), redimensiona el tamaño del vector, alterando tanto la capacidad, si esta aumenta, como el tamaño. Permite inicializar a un determinado valor los valores nuevos añadidos al redimensionar.

Se irán estudiando algunas de estas funciones miembro a lo largo de los siguientes apartados.