5.1.1.b Cuestiones adicionales

§1 Gestión de memoria

Como adelantábamos en la introducción, los contenedores son estructuras de datos que, a excepción de referencias ( 4.2.3), permiten albergar cualquier tipo de dato:  tipos fundamentales (enteros, carácter, etc. 2.2);  punteros, o tipos abstractos definidos por el usuario. También señalábamos que una de sus características más destacadas es que encapsulan la gestión del espacio de almacenamiento, de forma que el programador puede despreocuparse de los problemas relacionados con los operadores new y delete ( 4.9.20).

Nota: al tratar de los asignadores ( 5.1.5), veremos que la gestión de memoria propiamente dicha se ha desvinculado de los contenedores. En realidad, esta función se delega en unos objetos denominados asignadores ("Allocators") que son insertados en los contenedores de forma parecida a como los locales se insertan en los gestores de flujo (iostreams).

La gestión de memoria realizada por los contenedores comprende tanto la asignación y liberación de espacio para sus miembros, como para las claves que constituyen el sistema de índice de algunos tipos de contenedor ( 5.1.1e Asociaciones). En general los algoritmos de la STL están muy optimizados y el sistema de asignación de memoria intenta compaginar rapidez y eficacia. La primera exige asignar y desasignar espacio cada vez que se introduce o elimina un miembro del contenedor. La eficacia, e incluso la disminución de la fragmentación inherentes al manejo del montón ( 1.3.2), exige asignar y rehusar trozos de memoria lo más grandes posible cada vez. El abordaje a este problema se ha realizado de dos formas básicas: (a) Contenedores que no pueden alterar su tamaño, de forma que la asignación de espacio para sus elementos debe realizarse en el momento de su declaración. (b) Contenedores que pueden crecer y/o disminuir en consonancia con los elementos a albergar.

Refiriéndonos al caso (b), para balancear estas exigencias contrapuestas, algunas implementaciones utilizan el siguiente esquema de trabajo: inicialmente el sistema asigna al contenedor un trozo de memoria de tamaño adecuado para contener cierto número de elementos; espacio que es utilizando hasta que se agota. A partir de aquí, cada nueva demanda origina la asignación una zona de doble tamaño que la anterior. Por ejemplo, supongamos que para gestionar un vector de enteros, el compilador asigna inicialmente espacio para un máximo de 16 miembros.  Cuando se agotara, se realizaría una nueva asignación de espacio para 32 miembros, e inmediatamente se efectuaría una recolocación del contenido actual en el nuevo espacio y la liberación del primitivo. Si el nuevo contenedor quedara lleno de nuevo, la siguiente asignación sería capaz de 64 miembros y así sucesivamente [1].

Nota: el factor de aumento de tamaño puede ser cualquiera. Muchos compiladores utilizan un factor 1.5 cada vez que deben ampliar el espacio necesario.

Observe que cada nueva recolocación implica en realidad varios pasos:

• Asignación de memoria al estilo malloc() de la librería clásica en cantidad suficiente para el nuevo tamaño.
• Copia de los elementos actuales en la nueva localización. Los elementos son colocados en la nueva situación utilizando el constructor copia ( 4.11.2d4).
• Actualización de las estructuras internas del nuevo contenedor (sistema de índices).
• Eliminación de los elementos originales mediante invocación sucesiva de sus correspondientes destructores ( 4.11.2d2).
• Liberación de la memoria utilizada por las estructuras internas.
• Liberación de la zona original mediante una invocación al estilo free() de la librería clásica.

En general, al referirse al tamaño de un contenedor existen tres magnitudes distintas aunque relacionadas, cuyos valores pueden obtenerse mediante tres métodos:

• El número de elementos contenidos actualmente. size()
• El máximo número de elementos que pueden alcanzarse actualmente sin necesidad de una nueva recolocación. capacity()
• El máximo número de elementos que pueden alcanzarse en cualquier caso. max_size().

Ejemplo:

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

int main() {         // ================
vector<int> vInt;
for (int i=0; i < 100; i++) vInt.push_back(i);

cout << "Tamaño actual:   " << vInt.size()     << endl;
cout << "Capacidad actual: " << vInt.capacity() << endl;
cout << "Tamano maximo:   " << vInt.max_size() << endl;

return 0;
}

Salida:

Tamaño actual: 100
Capacidad actual: 256
Tamano maximo: 1073741823

Evidentemente, en todos los casos: size() <= capacity()

Es posible comprobar si un contenedor está vacío, comparando su tamaño actual size() con cero, aunque es más rápido utilizar el método empty(), que devuelve true si realmente size() == 0.

§2 Reserva de espacio

Como puede suponer, cada recolocación supone un proceso considerable, sobre todo en contenedores muy grandes. Para evitar sus inconvenientes si se conoce de antemano el tamaño máximo a utilizar, la STL ofrece la posibilidad de preasignar un espacio arbitrario. Para esto se dispone del método reserve(n), que garantiza la asignación de espacio inicial suficiente para alojar n miembros en el contenedor. Si el argumento n es mayor que la capacidad actual, se produce una recolocación y el nuevo argumento determina la nueva capacidad. Si es menor no se produce ninguna acción.

Ejemplo, para crear un vector de enteros capaz para al menos 1000 miembros:

vector <int> v;
v.reserve(1000);

En el siguiente ejemplo se muestran los resultados compilado con Borland C++ 5.5 para Win32; con MS Visual C++ 6.0 y con GNU gcc 2.95.3 para Linux:

// resultados con:         BC++   VC++   GNU   

vector<int> v;
cout << v.size();      // -> 0      0      0   
cout << v.capacity();  // -> 0      0      0
v.push_back(3);
cout << v.size();      // -> 1      1      1
cout << v.capacity();  // -> 256    1      1
v.reserve(100);

cout << v.size();      // -> 1      1      1
cout << v.capacity();  // -> 256    100    100

§3 Operaciones sobre contenedores

Los elementos de un contenedor son colocados en él utilizando el constructor copia ( 4.11.2d4), aunque algunas operaciones requieren la existencia de un constructor por defecto ( 4.11.2d1). A su vez, los algoritmos genéricos, como copy(), que copian a un contenedor, utilizan el operador de asignación.

Por ejemplo, cuando se duplica todo un contenedor de tipos T por invocación del constructor copia o por asignación, cada miembro es copiado en la nueva estructura utilizando el constructor copia o el operador de asignación. Tanto si una copia profunda o una copia somera, el resultado es controlado por el programador, que puede proporcionar el operador de asignación para el tipo T con cualquier significado que desee. Si se ha definido un destructor para el tipo T, este destructor es invocado cada vez que deba ser eliminado un elemento del contenedor. Cuando se destruye toda la colección, el destructor es invocado por cada elemento que permaneciera almacenado.

Debemos añadir algunas palabras acerca de los contenedores que almacenan colecciones de punteros. Estos conjuntos no son raros. Por ejemplo, una colección de punteros es el único medio de almacenar valores que pueden representar indistintamente instancias de una clase o instancias de una subclase. Puede encontrarse una de estas colecciones en el ejemplo de simulación manejada por eventos ( xxx).

En estos casos, el contenedor es solamente responsable de mantener los propios punteros, siendo responsabilidad del programador manejar la memoria de los valores referenciados por estos, lo que supone que los espacios de memoria son asignados correctamente; por lo general mediante el operador new; que no son desasignados mientras el contenedor albergue referencias a ellos, y que sean adecuadamente desasignados una vez que han sido eliminados del contenedor.

  Inicio.

---

[1]  Desde luego esta es solo una imagen didáctica. El tamaño real será mayor, ya que el contenedor, en cuanto estructura de datos, alberga alguna información adicional sobre sí mismo.