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

abc-> defghi-> jkl-> MNOP

Элементы вышеупомянутой deque состоят из одного символа. Набор символов в одной группе указывает, что он размещен в смежной памяти (например, abc находится в одном блоке памяти, defhi находится в другом блоке памяти и т. Д.). Может ли кто-нибудь объяснить, как доступ по индексу позиции может осуществляться в постоянное время, особенно если элемент, к которому осуществляется доступ, находится во втором блоке? Или в деке есть указатель на группу блоков?

Обновление: или есть другая распространенная реализация для deque?