为什么 push_back 或 push_front 使双端队列的迭代器无效? [英] Why does push_back or push_front invalidate a deque's iterators?

问题描述

如标题所示.

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

My understanding of a deque was that it allocated "blocks". I don't see how allocating more space invalidates iterators, and if anything, one would think that a deque's iterators would have more guarantees than a vector's, not less.

推荐答案

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

The C++ standard doesn't specify how deque is implemented. It isn't required to allocate new space by allocating a new chunk and chaining it on to the previous ones, all that's required is that insertion at each end be amortized constant time.

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

So, while it's easy to see how to implement deque such that it gives the guarantee you want[*], that's not the only way to do it.

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

[*] Iterators have a reference to an element, plus a reference to the block it's in so that they can continue forward/back off the ends of the block when they reach them. Plus I suppose a reference to the deque itself, so that operator+ can be constant-time as expected for random-access iterators -- following a chain of links from block to block isn't good enough.

这篇关于为什么 push_back 或 push_front 使双端队列的迭代器无效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！