据我所知,deque 背后的动机是提供一个具有高效 push_front
的随机访问容器。
与双端队列相比,vector 常被提及的优势包括更快的遍历和 at()
,但主要是它的 C 兼容性,因为它保证了连续的内存。 Deque 没有,因为它是内存块的集合,每个内存块都包含多个值。
我很困惑。为什么 deque 不像 vector 那样构建,而是在索引 0
之前保留内存以及在索引 size-1
之后保留内存?这将保证连续的内存,启用高效的 push_front
,甚至在取消引用迭代器时避免额外的间接访问。
为了尽量减少插入过程中的移位,要移位的包含值将取决于插入点。如果在 size()/2
之前的索引 n
处插入,则将值向左移动 n
。否则右移 n
之后的值。
我错过了什么如此重要以至于双端队列是值数组的集合而不是一个大数组?
最佳答案
According to Wikipedia ,您所描述的确实是一种可能的实现方式,至少在一般情况下是这样。
但是,C++ 标准强加的要求基本上禁止将此作为 std::deque
的实现; [deque.modifiers] 声明:
An insertion at either end of the deque ... has no effect on the validity of references to elements of the deque.
(感谢@BenjaminLindley!)
关于c++ - 为什么 std::deque 不是在索引 0 之前保留内存的 vector ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14793086/