c++ - 为什么 push_back 或 push_front 使双端队列的迭代器无效？

Question

如标题所示。

我对双端队列的理解是它分配了“ block ”。我看不出分配更多空间如何使迭代器无效，如果有的话，人们会认为双端队列的迭代器比 vector 的保证更多，而不是更少。

Answer 1

C++ 标准没有指定如何实现双端队列。不需要通过分配一个新 block 并将其链接到以前的 block 来分配新空间，所需要的只是在每一端的插入均摊销常数时间。

因此，虽然很容易看到如何实现双端队列以提供您想要的保证 [*]，但这并不是唯一的方法。

[*] 迭代器有一个元素的引用，加上一个对它所在 block 的引用，这样当它们到达它们时，它们可以在 block 的末端继续前进/后退。另外，我假设对双端队列本身的引用，以便 operator+ 可以像随机访问迭代器所期望的那样是恒定时间的——遵循从 block 到 block 的链接链还不够好。