Internes STL: implémentation deque

J’utilise un std :: deque pour stocker une grande collection d’éléments .
Je sais que deques est implémenté sous forme de liste de vecteurs. La taille de ces vecteurs ne peut pas être définie, mais je cherche quel est l’algorithme pour choisir cette taille.

    deque est implémenté comme un vecteur de vecteurs (une liste de vecteurs entraverait l’access aléatoire dans le temps constant). La taille des vecteurs secondaires dépend de la mise en œuvre. Un algorithme courant consiste à utiliser une taille constante en octets.

    Mon implémentation deque , celle de GNU qui est dérivée de la version HP / SGI, n’est pas une liste de vecteurs; du moins, pas une std::list of std::vector s. Les commentaires disent

     * 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 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".)