Estoy trabajando en un algoritmo de clasificación externo que usastd::queue y debe restringir cuidadosamente su uso de memoria. He notado que durante la fase de fusión (que usa variosstd::queues de longitud fija), mi uso de memoria aumenta a aproximadamente 2.5X de lo que esperaba. Ya questd::queue por defecto utilizastd::deque como su contenedor subyacente, ejecuté algunas pruebas enstd::deque para determinar su sobrecarga de memoria. Estos son los resultados, que se ejecutan en VC ++ 9, en modo de lanzamiento, con un proceso de 64 bits:

Al agregar 100,000,000chars a unstd::deque, el uso de memoria crece a 252,216K. Tenga en cuenta que 100Mchars (1 byte) debería ocupar 97,656K, por lo que esta es una sobrecarga de 154,560K.

Repetí la prueba condoubles (8 bytes) y la memoria de sierra creció a 1,976,676K, mientras que 100Mdouble¡s debería ocupar 781,250K, para una sobrecarga de 1,195,426K!

Ahora entiendo questd::deque normalmente se implementa como una lista vinculada de "fragmentos". Si esto es cierto, ¿por qué la sobrecarga es proporcional al tamaño del elemento (porque, por supuesto, el tamaño del puntero debe fijarse en 8 bytes)? ¿Y por qué es tan peligroso?

¿Alguien puede arrojar algo de luz sobre por quéstd::deque usa tanta memoria peligrosa? Estoy pensando que debería cambiar mistd::queue contenedores subyacentes parastd::vector ya que no hay gastos generales (dado que el tamaño apropiado esreserveed). Estoy pensando en los beneficios destd::deque están en gran parte anulados por el hecho de que tiene una sobrecarga tan grande (que resulta en errores de caché, fallas de página, etc.) y que el costo de la copiastd::vector los elementos pueden ser menores, dado que el uso general de la memoria es mucho menor. ¿Es solo una mala implementación destd::deque por Microsoft?