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

问题描述

正如标题所示。

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

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 ++标准没有规定如何实现deque。不需要通过分配新的空间并将其链接到先前的空间来分配新的空间，所需要的只是每端的插入是按照常数摊销。

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.

所以，虽然很容易看到如何实现deque以便它提供你想要的保证[*]，但这不是唯一的方法。

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.

[ *]迭代器具有对元素的引用，以及对其所在块的引用，以便它们在到达时可以继续向前/向后移出块的末尾。另外我假设对deque本身的引用，以便 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使deque的迭代器无效？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！