当插入顶部时，deque提供O（1）复杂度 [英] Does deque provide O(1) complexity when inserting on top

问题描述

我正在浏览此讯息，并指出该deque在顶部和底部提供有效的insetion。然而，这 post 这里指出，除了后面的deque的时间复杂度是O（n）。我会认为如果deque有效顶部和底部插入，它将有O（1），而一个向量应该有O（1）底部插入。如果有人可以澄清这一点，我将不胜感激。

解决方案

std :: deque 提供了以下复杂性：

<对deque的通用操作的复杂性（效率）如下：

• 随机访问 - O（1）


• 在结尾或开头插入或移除元素 - 摊销常数O（1）


• 插入或移除元素 - 线性O（n）

，与草稿C ++标准部分 23.3.3.1 类模板deque概述（强调我）：

deque是一个序列容器，像向量（23.3.6），支持随机存取迭代器。此外，它支持在开始或结束时的恒定时间插入和擦除操作;在中间插入和擦除取线性时间。也就是说， deque特别优化了在开始和结束时推送和弹出元素。与向量一样，存储管理会自动处理。

对于 std :: vector cppreference说：

复杂性）向量上的常用操作如下：

• 随机访问 - 常数O li>
  
• 在末尾插入或删除元素 - 摊销常量O（1）


• 插入或删除元素 - 23.3.6.1 类模板向量概述：

  
  

  向量是支持随机访问迭代器的序列容器。此外，它支持（摊销）常数时间插入和擦除操作结束; 在中间插入和擦除取线性时间。 [...]

  
  

  
  

  I was going over this post and it states that deque provides efficent insetion at the top and bottom.However this post here states that time complexity of deque other than the back is O(n).I would think that if a deque has efficent top and bottom insertion it would have O(1) while a vector should have O(1) at bottom insertion only. I would appreciate it if someone could clarify this

  解决方案

  The cppreference entry for std::deque gives the following complexity:

  The complexity (efficiency) of common operations on deques is as follows:

  • Random access - constant O(1)
  • Insertion or removal of elements at the end or beginning - amortized constant O(1)
  • Insertion or removal of elements - linear O(n)

  which is consistent with the draft C++ standard section 23.3.3.1 Class template deque overview which says (emphasis mine):

  A deque is a sequence container that, like a vector (23.3.6), supports random access iterators. In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. That is, a deque is especially optimized for pushing and popping elements at the beginning and end. As with vectors, storage management is handled automatically.

  For std::vector cppreference says:

  The complexity (efficiency) of common operations on vectors is as follows:

  • Random access - constant O(1)
  • Insertion or removal of elements at the end - amortized constant O(1)
  • Insertion or removal of elements - linear in distance to the end of the vector O(n)

  which is consistent with the draft standard section 23.3.6.1 Class template vector overview:

  A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency.[...]

  这篇关于当插入顶部时，deque提供O（1）复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！