Я использую std:: deque для хранения большой коллекции элементов.
Я знаю, что deques реализуется как список векторов. Размер этих векторов не может быть установлен, но я блуждаю по алгоритму выбора этого размера.
Внутренние элементы STL: реализация deque
Ответ 1
deque реализуется как вектор векторов (список векторов будет препятствовать постоянному случайному доступу во времени). Размер вторичных векторов зависит от реализации, общий алгоритм - использовать постоянный размер в байтах.
Ответ 2
Моя реализация deque
, одна из GNU, которая получена из версии HP/SGI, не является списком векторов; по крайней мере, не std::list
of std::vector
s. В комментариях указано
* 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 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 usage of "node".)