c++ - STL internals: implementación de deque

Question

Estoy usando un std :: deque para almacenar una gran colección de artículos .
Sé que Deques se implementa como una lista de vectores. El tamaño de esos vectores no puede establecerse pero deduzco cuál es el algoritmo para elegir ese tamaño.

Answer 1

Mi implementación deque , la de GNU, que se deriva de la versión HP / SGI, no es una lista de vectores; al menos, no una std::list de std::vector s. Los comentarios indican

* In previous HP/SGI versions of deque, there was an extra template
* parameter so users could control the node size. This extension turned
* out to violate the C++ standard (it can be detected using template
* template parameters), and it was removed.
*
* Here''s how a deque<Tp> manages memory. Each deque has 4 members:
*
* - Tp** _M_map
* - size_t _M_map_size
* - iterator _M_start, _M_finish
*
* map_size is at least 8. %map is an array of map_size
* pointers-to-"nodes". (The name %map has nothing to do with the
* std::map class, and "nodes" should not be confused with
* std::list''s usage of "node".)

Answer 2

deque se implementa como un vector de vectores (una lista de vectores impediría el acceso aleatorio de tiempo constante). El tamaño de los vectores secundarios depende de la implementación, un algoritmo común es usar un tamaño constante en bytes.