vector
La clase vector almacena todos los datos de forma secuencial. Esta mecánica hace que cada vez que se llene tenga que hacerse un realloc a una región más grande... con la penalización de rendimiento que conlleva copiar regiones grandes de memoria. Como toda la información está contenida en una única región de memoria, para gestionar los datos únicamente hacen falta tres variables:
- Un puntero que apunte al inicio de la región de memoria
- Un entero que indique el número máximo de elementos
- Un entero que indique la cantidad de posiciones ocupadas
Asumiendo que un entero y un puntero son 4 bytes, almacenar 1 millón de elementos de 4 bytes ocuparía: 1.000.000 * 4 + 3 * 4 = 4.000.012 bytes
list
La clase lista implementa una lista doblemente enlazada. En este caso añadir nuevos elementos supone un coste más o menos estable y constante de tiempo ya que no implica reallocs. La penalización de este contenedor la encontramos al acceder a un elemento aleatorio, ya que obliga a recorrer diferentes nodos para dar con el elemento en cuestión... en listas largas la penalización aumenta.
Una lista doblemente enlazada necesita dos punteros por cada elemento de la lista... uno apuntando al elemento anterior y otro al siguiente. Además necesitamos un puntero al primer nodo de la lista. Para almacenar un millón de elementos tenemos que: 3 * 4 * 1.000.000 + 4 = 12.000.004 bytes
¿De dónde sale ese 3? puntero al elemento anterior + puntero al elemento siguiente + el dato a almacenar = 3 * 4 bytes
Estos cálculos son a grandes rasgos, pero sirven para hacerse una idea de los requisitos de memoria.
¿Soluciones?
Lo más óptimo sería usar
std::vector pero reservando la memoria previamente. De esta forma evitamos reallocs y nos aseguramos de disponer de la memoria necesaria para ejecutar nuestro algoritmo.
Para que el vector reserve memoria hay que llamar al método
reserve(). Este método fuerza al vector a reservar memoria para almacenar, al menos la cantidad de elementos que le indiquemos.
Si no tenemos a priori ninguna certeza ni aproximación sobre cuáles van a ser los recursos de la aplicación puedes tener un problema. Piensa que al hacer reallocs el sistema operativo tiene que ser capaz de encontrar regiones de memoria cada vez más grandes...y eso puede ser un problema debido a que la memoria tiende a fragmentarse... usar listas enlazadas no es la solución debido a su mayor consumo de recursos.
Tienes una alternativa y es implementar un contenedor que gestione bloques de memoria... estaría a medio camino entre los dos contenedores de los que hablamos... la clase en cuestión reservaría la memoria en bloques de X elementos... cuando el bloque se llene reserva uno nuevo. Este diseño podría adaptarse mejor a los requisitos de tu aplicación... pero te tocaría implementarlo de 0 salvo que encuentres una implementación ya hecha.
Un saludo.