c++ - 通过索引访问 STL 双端队列是 O(1)？

Question

我读过可以在 STL 双端队列中通过位置索引访问元素在恒定时间内完成。据我所知，双端队列中的元素可能存储在几个不连续的位置，从而消除了通过指针算法进行的安全访问。例如:

abc->defghi->jkl->mnop

上述双端队列的元素由单个字符组成。一组中的字符集表明它分配在连续的内存中(例如 abc 位于单个内存块中，defhi 位于另一 block 内存中，等等)。谁能解释如何通过位置索引访问可以在恒定时间内完成，特别是如果要访问的元素在第二个 block 中？还是双端队列有指向 block 组的指针？

更新:或者是否有任何其他常见的双端队列实现？

Answer 1

我从 Wikipedia 找到了这个双端队列实现:

Storing contents in multiple smaller arrays, allocating additionalarrays at the beginning or end as needed. Indexing is implemented bykeeping a dynamic array containing pointers to each of the smallerarrays.

我想它回答了我的问题。