相关疑难解决方法(0)

CPython的deque被实现为64项的双向链表大小的"块"(阵列).除了链表两端的那些块外,这些块都是满的.在IIUC中,当pop/ popleft删除块中的最后一项时,块被释放; 当append/ appendleft尝试添加新项目并且相关块已满时,将分配它们.

我理解使用链接列表而不是链接项列表所列出的优点:

• 减少每个项目中prev和next的指针的内存成本
• 减少为malloc/ free添加/删除的每个项目执行/的运行时成本
• 通过将连续指针放在彼此旁边来改善缓存局部性

但是为什么不是首先使用单个动态大小的圆形数组而不是双链表呢？

AFAICT,圆形阵列将保留所有上述优点,并维持(atortized)成本pop*/ append*at O(1)(通过分配,就像在中list).此外,它还可以提高从当前O(n)到索引的索引查找成本O(1).循环数组也可以更简单地实现,因为它可以重用大部分list实现.

我可以在C++这样的语言中看到支持链表的论证,其中可以O(1)使用指针或迭代器从中间删除项目; 但是,python deque没有API来执行此操作.

跟进std :: deque的内存开销对heque的影响是什么？

Visual C++ deque使用以下方法根据容器元素类型管理块:

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 16 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

这导致小元件的内存占用非常大.通过将第一行中的16更改为128,我能够大幅减少大型所需的占用空间deque<char>.在100m push_back(const char& mychar)调用后,Process Explorer Private Bytes从181MB减少到> 113MB .

• 任何人都能证明这些价值#define吗？
• 其他编译器如何处理deque块大小调整？
• 对于100m push_back调用 的简单测试,它们的占用空间(32位操作)是deque<char>什么？
• STL是否允许在编译时覆盖此块大小而不修改 <deque>代码？

关于deque中的迭代器失效,我有点困惑.(在这个问题的背景下)

以下是摘自 - The C++标准库:教程和参考,作者:Nicolai M. Josuttis

除开头或结尾之外的任何元素的插入或删除都会 使引用双端队列元素的所有指针,引用和迭代器无效.

以下是SGI网站的摘录:

deque的迭代器失效的语义如下.Insert(包括push_front和push_back)使引用deque的所有迭代器无效.在双端队列中间擦除使所有引用双端队列的迭代器无效.只有当它指向已擦除的元素时,在双端队列的开头或结尾处擦除(包括 pop_front和pop_back)才会使迭代器无效.

恕我直言,deque是块的集合,第一个块在一个方向上生长,最后一个块在相反方向上生长.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front 不应该对deque迭代器产生任何影响(我同意Josuttis).

什么是正确的解释？标准对此有何看法？

我使用std :: deque来存储大量的项目.
我知道deques是作为矢量列表实现的.这些矢量的大小无法设置,但我喜欢选择该大小的算法.