Внутренние компоненты STL: реализация deque

Question

Я использую std :: deque для хранения большой коллекции элементов .
Я знаю, что deques реализован в виде списка векторов.Размер этих векторов не может быть установлен, но я хочу узнать, каков алгоритм выбора этого размера.

Answer 1

deque реализован как вектор векторов (список векторов будет препятствовать произвольному доступу с постоянным временем).Размер вторичных векторов зависит от реализации, общий алгоритм должен использовать постоянный размер в байтах.

Answer 2

Моя deque реализация, основанная на GNU, которая получена из версии HP / SGI, не является списком векторов; по крайней мере, std::list из std::vector с. Состояние комментариев

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