std :: deque什么时候需要重新分配？

Question

据我所知，std::deque它的元素存储在大块的块中（尽管它依赖于实现，但这是我在大多数资源中所读到的），而std::vector在大多数情况下，它只使用一个内存块。

因此，std::vector在插入过程中遇到重新分配是很合理的。但是，我无法说明需要重新分配的任何情况，std::deque因为当电流耗尽时，它只是从新的内存块重新开始。

有人能提供我一些情况std::deque需要重新分配的情况吗？

Answer 1

任何人都可以为我提供std :: deque需要重新分配的情况，因为对它执行了一些操作。

在典型情况下，永远不会。尽管deque未指定a的确切实现细节，但要保留迭代器/指针/引用无效*和算法要求，对于任何需要将现有内存块重新分配给更大或更小的存储块的情况，都会发现不实用。

[特别关注指针/引用无效，因为这可以告诉我们更多有关内存中必须进行的操作。迭代器可能会产生一些异常，使它们的有效性与[ deque] 的内存表示分离。

尝试使自己陷入实施者的困境。如果您曾试图重新分配内存块，那么如何实现诸如push_front，push_back和的功能，并且resize以不会使任何现有指向的指针无效的方式进行扩展deque？

而同样保持了类似的要求pop_front，并pop_back和收缩resize（仅无效的指针到被删除的元素），如果你是否曾经试图重新分配现有的内存块，以更小的尺寸？

陷阱部分以及您可能会发现重新分配的可能性最小的地方是插入到的中间deque。那是所有指向的指针deque都可以失效的地方，并且有可能重新分配deque's内容（可能，不一定是实际的）。仅在这种特殊情况下，作为deque实现者，我们才能使指向仍然存在的元素的指针无效，我们甚至可以自由地重新分配任何现有的内存块。但是这种情况不太可能发生，因为有效的insert实现通常只希望改组和移动元素，而不实际重新分配它们所驻留的内存块。

所有这些要求结合起来，将实现限制在Sutter所描述的那种类型，即使他有点草率地在理论部分上有所作为。这有点像C ++ 03代码经常被认为std::vector是连续的，即使未指定，也总是连续的，因为对于std::vector连续表示来说，算法和迭代器的要求几乎是唯一可行的选择。

因此，从理论上讲，有人可能会在符合这些要求的情况下以某种方式偷偷重新分配某个地方。但是实际上，这几乎是不可能的，而且绝对不切实际，因此很难找到这样的deque实现。

Answer 2

我想到的一件事是，当您在双端队列上进行插入并且插入需要进入的页面已满时会发生什么？cplusplus.com 介绍有关双端队列的插入功能

If the insertion happens at the beginning or the end of the sequence, all iterators 
related to this container are invalidated, but pointers and references remain valid, 
referring to the same elements they were referring to before the call. If the 
insertion happens anywhere else in the deque, all iterators, pointers and references 
related to this container are invalidated.

真正引起我注意的部分是，所有内容都无效了，因为插入位于中间，这对我来说听起来像是底层数据结构发生了一些事情。我不确定这是否是重新分配，但至少是移位复制插入。