El abecé de la plantilla vector<>
Última actualización del post: Octubre de 2020
Introducción
Como sabemos, la estructura estándar std::vector<> se considera el contenedor dinámico por defecto en el lenguaje C++. Ésta representa un array alojado en el free store, cuyo tamaño puede aumentar o disminuir a conveniencia durante el tiempo de ejecución de un programa. El hecho fundamental de que todos los elementos almacenados en el vector ocupen entradas contiguas en memoria virtual convierte a esta estructura en especialmente eficiente dado el modo de funcionamiento de los distintos niveles de memoria caché de nuestra computadora (véase este post anterior en relación a la localidad espacial y temporal de un programa), en contraste con el comportamiento típico de, por ejemplo, una lista (ver la figura inferior).
En este artículo discutiremos brevemente el funcionamiento del método principal de esta estructura, de signatura void vector<T>::push_back(T const& val), el cual introduce una copia de su argumento val al fondo del vector. Simplificaremos enormemente nuestra presentación omitiendo detalles finos de la implementación del contenedor, que incluirían el uso de técnicas avanzadas de alojamiento en memoria o la posibilidad de utilizar la semántica de movimiento como método para evitar copias innecesarias de objetos. Nuestra implementación resultará, por tanto, poco eficiente y de utilidad ciertamente limitada, pero de claro valor pedagógico.
En este artículo discutiremos brevemente el funcionamiento del método principal de esta estructura, de signatura void vector<T>::push_back(T const& val), el cual introduce una copia de su argumento val al fondo del vector. Simplificaremos enormemente nuestra presentación omitiendo detalles finos de la implementación del contenedor, que incluirían el uso de técnicas avanzadas de alojamiento en memoria o la posibilidad de utilizar la semántica de movimiento como método para evitar copias innecesarias de objetos. Nuestra implementación resultará, por tanto, poco eficiente y de utilidad ciertamente limitada, pero de claro valor pedagógico.
Primeros pasos
En la imagen inferior se muestra el estado típico de un vector en el free store en un instante determinado. La estructura tiene reservado un bloque contiguo en memoria donde introducir objetos de tipo T. En la figura inferior, por ejemplo, se dispone de una capacidad máxima de ocho entradas, de las cuales sólo las tres primeras están ocupadas, mientras que las cinco restantes se encuentran disponibles para inserciones adicionales. Una vez agotada la capacidad, el vector deberá reubicarse en otra localización, reservando un mayor espacio en memoria para poder admitir nuevos datos.
Las primeras funciones miembro de la interfaz pública de nuestro contenedor (que llamaremos Vector para distinguirlo del estándar) podrían tomar, en una primera aproximación, la forma siguiente:
template<typename T> // T debe ser un tipo default_initializable
class Vector {
T* v_, // inicio del espacio de capacidad reservada para el vector
* space_, // fin de la secuencia de elementos almacenados
* last_; // fin de la capacidad reservada para el vector
void bounds_check(std::size_t i) const { if (i >= size()) throw std::out_of_range{}; }
public:
Vector() // construye un vector vacío
: v_{new T[0]}, space_{v_}, last_{v_} { }
Vector(Vector<T> const& v)
: v_{new T[v.capacity()]}, space_{v_ + v.size()}, last_{v_ + v.capacity()}
{
try {
for (auto i = size_t{0}; i < v.size(); ++i)
v_[i] = v[i];
}
catch (...) {
delete[] v_;
throw;
}
}
auto& operator=(Vector<T> const& rhs)
{
auto tmp = Vector<T>{rhs};
std::swap(v_, tmp.v_);
std::swap(space_, tmp.space_);
std::swap(last_, tmp.last_);
return *this;
}
~Vector() { delete[] v_; } // destruye el array apuntado por v_
// funciones de capacidad_________________________________________
auto size() const -> std::size_t { return space_ - v_; }
auto capacity() const -> std::size_t { return last_ - v_; }
auto empty() const -> bool { return v_ == space_; }
// funciones de acceso____________________________________________
// sin bounds checking:
auto operator[](std::size_t i) -> T& { return v_[i]; }
auto operator[](std::size_t i) const -> T const& { return v_[i]; }
// con bounds checking:
auto at(std::size_t i) -> T& { bounds_check(i); return v_[i]; }
auto at(std::size_t i) const -> T const& { bounds_check(i); return v_[i]; }
auto begin() -> T* { return v_; }
auto begin() const -> T const* { return v_; }
auto end() -> T* { return space_; }
auto end() const -> T const* { return space_; }
// resto de la interfaz pública...
};
Notemos que el constructor por defecto de la plantilla crea un vector vacío asignando la misma dirección a los tres punteros v_, space_ y last_. El destructor realiza simplemente una operación delete[] sobre el array referenciado por v_, en un claro ejemplo de empleo de la técnica RAII. Sirviéndose de la aritmética de punteros tradicional, la función size() proporciona el número de elementos de tipo T almacenados en el vector. La función capacity() informa de la capacidad total que el vector tiene reservada en el momento de su invocación (es decir, el número total de elementos de tipo T que podría contener sin necesidad de realojarse). Por su parte, empty() retorna una variable booleana igual a true de ser size() nulo, y false en caso contrario.
Función push_back
Con el fin de insertar elementos al fondo del vector, implementaremos la función miembro pública push_back, de signatura void push_back(T const& val). Su modo de funcionamiento es el siguiente: si el vector dispone de al menos una entrada libre donde introducir al nuevo elemento (es decir, si los punteros space_ y last_ no referencian la misma dirección en memoria), realizaremos una copia del argumento val en la posición indicada por space_ e incrementaremos dicho puntero en una unidad. Por contra, si los punteros space_ y last_ coincidiesen, debemos contemplar dos escenarios independientes:
- Es la primera vez que realizamos una operación push_back (capacidad inicial nula). En tal caso, reservaremos espacio, no ya para un único elemento, sino para dos (el introducido con la operación push_back recién invocada y uno adicional en previsión de una más que probable inserción posterior).
- El vector contiene elementos, pero ha agotado su capacidad no-nula actual. En tal caso, reservaremos un nuevo bloque de memoria en el free store cuya capacidad doble el tamaño actual del vector. Procederemos entonces a copiar el contenido del array original en el nuevo e insertaremos, a continuación, una copia del argumento val. De finalizar este proceso de forma exitosa, destruiremos el array original y reasignaremos convenientemente los punteros v_, space_ y last_ para que referencien las direcciones apropiadas en el nuevo array.
template<typename T>
void Vector<T>::push_back(T const& val)
{
if (space_ == last_) { // capacidad agotada o primera vez que invocamos push_back
std::size_t cp = capacity(), // capacidad actual del vector
new_cp = (cp == 0)? 2 : 2*cp; // nueva capacidad
T* new_block = new T[new_cp]; // nuevo bloque de memoria
try {
for (auto i = std::size_t{}; i < cp; ++i)
new_block[i] = v_[i];
new_block[cp] = val;
}
catch (...) { // de lanzarse una excepción...
delete[] new_block; //... destruimos el nuevo array...
throw; // ...y relanzamos la excepción
}
// destruimos el array original y reasignamos los punteros:
delete[] v_;
v_ = new_block;
space_ = new_block + cp + 1;
last_ = new_block + new_cp;
}
else {
*space_ = val;
++space_;
}
}
Observemos que el bucle for que realiza la copia de los elementos del array original en su nuevo destino new_block, así como la inserción de la copia de val, se encuentran encerrados en un bloque try con el fin de que, de lanzarse una excepción por parte de una cualquiera de dichas copias, ésta sea capturada en el bloque catch con elipsis posterior. Se procede en ese caso a destruir el nuevo array new_block y a relanzar la excepción, interrumpiendo en ese punto la ejecución de la función push_back(). Dado que aún no se habría modificado el array original (su contenido aún no se habría destruido ni se habrían reasignado sus vectores v_, space_ y last_), la función push_back proporciona claramente una garantía fuerte ante excepciones (véase este post anterior para más detalles).
Ejemplo de uso
El siguiente código sencillo para C++20 demuestra el crecimiento en tiempo de ejecución del vector. El programa solicita al usuario la introducción por la terminal de tantas palabras (strings) como desee. Esta operación puede detenerse con la combinación especial de caracteres EOF (Ctrl+Z-Return en MS Windows, Ctrl+D en Linux). El vector de palabras es entonces ordenado lexicográficamente y mostrado en consola:
auto words = Vector<std::string>{}; // vector de palabras inicialmente vacío
auto mssg = []{ fmt::print("Insert a word (EOF to finish): "); return true; };
for (auto wrd = std::string{}; mssg() and std::getline(std::cin, wrd); /* no-op */)
words.push_back(wrd);
std::ranges::sort(words);
for (std::string const& wrd : words)
fmt::print("{}, ", wrd);
Referencias bibliográficas:
- Stroustrup B., 'The C++ Programming Language', Addison-Wesley, 4th Edition (2013).