STL通过索引访问deque是O（1）？ [英] STL deque accessing by index is O(1)?

问题描述

我读过，通过位置索引访问元素可以在STL deque中的恒定时间内完成。据我所知，deque中的元素可以存储在几个非连续的位置，消除通过指针运算的安全访问。例如：

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位于另一个存储器块中等）。任何人都可以解释如何通过位置索引访问可以在固定时间内完成，特别是如果要访问的元素在第二个块？或者deque有指向块组的指针吗？

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?

更新：或者是否有其他常见的deque方法？

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

推荐答案

我从维基百科找到这个装备执行方式：

I found this deque implementation from Wikipedia:

将内容存储在多个较小的数组中，根据需要在开头或结尾分配其他数组。通过保存包含指向每个较小数组的指针的动态数组来实现索引。

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通过索引访问deque是O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！