按索引访问的 STL 双端队列是 O(1)? [英] STL deque accessing by index is O(1)?

问题描述

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

I've read that accessing elements by position index can be done in constant time in a STL deque. As far as I know, elements in a deque may be stored in several non-contiguous locations, eliminating safe access through pointer arithmetic. For example:

abc->defghi->jkl->mnop

abc->defghi->jkl->mnop

上述双端队列的元素由单个字符组成.一组中的字符集表示它被分配在连续的内存中(例如 abc 在单个内存块中，defhi 位于另一个内存块中，等等).任何人都可以解释如何在恒定时间内按位置索引进行访问，特别是如果要访问的元素在第二个块中?或者双端队列是否有指向块组的指针?

The elements of the deque above consists of a single character. The set of characters in one group indicate it is allocated in contiguous memory (e.g. abc is in a single block of memory, defhi is located in another block of memory, etc.). Can anyone explain how accessing by position index can be done in constant time, especially if the element to be accessed is in the second block? Or does a deque have a pointer to the group of blocks?

更新:或者双端队列还有其他常见的实现吗?

Update: Or is there any other common implementation for a deque?

推荐答案

我从 维基百科:

将内容存储在多个较小的数组中，分配额外的根据需要将数组放在开头或结尾.索引是由保持一个包含指向每个较小指针的动态数组数组.

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

我想它回答了我的问题.

I guess it answers my question.

这篇关于按索引访问的 STL 双端队列是 O(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！