双端队列如何具有摊销常数时间复杂度
How does deque have an amortized constant Time Complexity
我从接受的答案中读到 here std::deque 具有以下特征
1- Random access - constant O(1)
2- Insertion or removal of elements at the end or beginning - amortized constant O(1)
3- Insertion or removal of elements - linear O(n)
我的问题是关于第 2 点的。双端队列如何在末尾或开头插入分摊常量？
我知道 std::vector 最后插入的时间复杂度为分摊常数。这是因为向量是连续的并且是一个动态数组。因此，当它最后用完 push_back 的内存时，它会分配一个全新的内存块，将现有项目从旧位置复制到新位置，然后从旧位置删除项目。我理解的这个操作是摊销常数。这如何应用于双端队列？双端队列顶部和底部的插入如何摊销常数。我的印象是它应该是常数 O(1)。我知道双端队列是由内存块组成的。
双端队列的通常实现基本上是指向固定大小节点的指针向量。
分配固定大小的节点显然具有恒定的复杂性，因此这很容易处理——您只需将分配单个节点的成本分摊到该节点中的项目数量上，以获得每个项目的恒定复杂性。
指针向量部分（稍微）更有趣。当我们分配足够多的固定大小节点使指针向量已满时，我们需要增加向量的大小。像std::vector一样，我们需要将它的内容复制到新分配的向量中，所以它的增长必须遵循几何级数（而不是算术级数）。这意味着我们有更多的指针要复制，我们进行复制的频率越来越低，因此用于复制指针的总时间保持不变。
附带说明："vector" 部分通常被视为循环缓冲区，因此如果您将双端队列用作队列，则不会不断地向一端添加并从另一端删除在重新分配向量时——它只是意味着移动头指针和尾指针，这些指针在给定时间跟踪哪些指针是 "active"。
（亵渎）答案位于 containers.requirements.general、23.2.1/2：
All of the complexity requirements in this Clause are stated solely in
terms of the number of operations on the contained objects.
因此，重新分配指针数组不在标准的复杂性保证范围内，并且可能需要任意长的时间。如前所述，它可能会在任何 "sane" 实现中为每个 push_front()/push_back() 调用（或等效修饰符）添加摊销常数开销。不过，我不建议在 RT 关键代码中使用 deque。通常，在 RT 场景中，您不希望有无限制的队列或堆栈（在 C++ 中默认使用 deque 作为底层容器），内存分配都不会失败，因此您很可能使用预分配的环形缓冲区（例如 Boost 的 circular_buffer）。
我从接受的答案中读到 here std::deque 具有以下特征
1- Random access - constant O(1)
2- Insertion or removal of elements at the end or beginning - amortized constant O(1)
3- Insertion or removal of elements - linear O(n)
我的问题是关于第 2 点的。双端队列如何在末尾或开头插入分摊常量？
我知道 std::vector 最后插入的时间复杂度为分摊常数。这是因为向量是连续的并且是一个动态数组。因此，当它最后用完 push_back 的内存时，它会分配一个全新的内存块，将现有项目从旧位置复制到新位置，然后从旧位置删除项目。我理解的这个操作是摊销常数。这如何应用于双端队列？双端队列顶部和底部的插入如何摊销常数。我的印象是它应该是常数 O(1)。我知道双端队列是由内存块组成的。
双端队列的通常实现基本上是指向固定大小节点的指针向量。
分配固定大小的节点显然具有恒定的复杂性，因此这很容易处理——您只需将分配单个节点的成本分摊到该节点中的项目数量上，以获得每个项目的恒定复杂性。
指针向量部分（稍微）更有趣。当我们分配足够多的固定大小节点使指针向量已满时，我们需要增加向量的大小。像std::vector一样，我们需要将它的内容复制到新分配的向量中，所以它的增长必须遵循几何级数（而不是算术级数）。这意味着我们有更多的指针要复制，我们进行复制的频率越来越低，因此用于复制指针的总时间保持不变。
附带说明："vector" 部分通常被视为循环缓冲区，因此如果您将双端队列用作队列，则不会不断地向一端添加并从另一端删除在重新分配向量时——它只是意味着移动头指针和尾指针，这些指针在给定时间跟踪哪些指针是 "active"。
（亵渎）答案位于 containers.requirements.general、23.2.1/2：
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
因此，重新分配指针数组不在标准的复杂性保证范围内，并且可能需要任意长的时间。如前所述，它可能会在任何 "sane" 实现中为每个 push_front()/push_back() 调用（或等效修饰符）添加摊销常数开销。不过，我不建议在 RT 关键代码中使用 deque。通常，在 RT 场景中，您不希望有无限制的队列或堆栈（在 C++ 中默认使用 deque 作为底层容器），内存分配都不会失败，因此您很可能使用预分配的环形缓冲区（例如 Boost 的 circular_buffer）。