标签: deque

如果我们不断在容器的前面和后面添加,则应选择矢量Deques.但是,这是什么？不要vector的和deque的operator[]工作一样,还是没有？如果没有,哪一个更快？

我理解随机访问迭代器如何对连续容器起作用std::vector:迭代器只是维护一个指向当前元素的指针,并且任何加法/减法都应用于指针.

但是,我对于如何为非连续容器实现类似的功能感到困惑.我对如何std::deque:iterator工作的第一个猜测是,它维护了一个指向它包含的连续内存组的表的指针,但我不确定.

典型的标准库如何实现这一点？

Python类有六个要求,如下所示.只有粗体术语才能被视为要求.

1. 对于以下四个操作中的许多操作,接近O(1)性能.
2. 在将对象插入容器时维护已排序的顺序.
3. 能够查看对象中包含的最后值(最大值).
4. 允许双方弹出(获得最小或最大值).
5. 获取存储的对象的总大小或数量的能力.
6. 像Python的标准库中的代码一样成为现成的解决方案.

由于历史原因,这里留下了什么(帮助好奇并证明进行了研究).

在查看Python的标准库(特别是关于数据类型的部分)之后,我仍然没有找到满足碎片表要求要求的类.collections.deque接近所需,但它不支持保持其中包含的数据排序.它提供:

1. 在具有O(1)性能的双端队列的高效附加和弹出.
2. 双方都弹出对象中包含的数据.
3. 获取其中包含的对象的总大小或数量.

使用列表实现低效的解决方案将是微不足道的,但找到一个表现良好的类将更加可取.在不增加上限的增长内存模拟中,这样的类可以保留空(已删除)单元格的索引并保持碎片级别下降.该bisect模块可能有所帮助:

1. 在数组中插入新对象时,帮助按排序顺序保持数组.
2. 添加了用于保持列表作为对象排序的现成解决方案.
3. 允许执行array[-1]以查看数组中的最后一个值.

最终候选人未能完全满足要求并且看起来最不乐观的是heapq模块.虽然支持看似有效的插入并确保它array[0]是最小值,但数组并不总是处于完全排序状态.没有其他任何东西被发现有帮助.

有没有人知道Python中的类或数据结构是否接近这六个要求？

我总是被Python的collections.deque对象所吸引.它似乎就像一个列表,除了在开头添加/删除项比在列表中更快.

这让我想替换list用deque在我的代码不同的地方,我有我做左侧弹出一个列表.所以我的问题:有没有人标杆deque反对list在这样的情况下？

我deque::insert()从C++标准2003(第23.2.1.3章)中了解到如下复杂性:

在最坏的情况下,将单个元素插入到双端队列中需要时间在从插入点到双端队列开始的距离的最小值以及从插入点到双端队列结束的距离的线性.

我总是将stl deque的实现理解为内存块的集合.因此,插入仅影响与插入位置相同的存储块中的元素.我的问题是,标准是什么意思是"从插入点到双端队列开始的距离的最小值和从插入点到双端队列结束的距离的线性"？

我的理解是因为C++标准没有强制实施deque的某种实现.对于最坏的情况,复杂性通常是一般的.但是,在编译器的实际实现中,它与内存块中的元素数量成线性关系,这可能因不同的元素大小而异.

另一个猜测可能是,因为insert()将使所有迭代器无效,deque需要更新所有迭代器.因此它是线性的.

想知道为什么我的内存访问速度比我预期的慢一些,我终于想通了Visual C++实现deque确实有一个内置的额外间接层,破坏了我的内存局部性.

即它似乎持有一个数组T*,而不是一个数组T.

是否有另一个我可以使用VC++但没有这个"功能"的实现,或者是否有某种方式(虽然我认为不太可能)在这个实现中能够避免它？

我基本上都在寻找一个vector在前面也有O(1)推/弹的东西.
我想我可以自己实现它,但处理allocators等是一种痛苦,需要一段时间才能正确,所以我宁愿使用以前编写/测试的东西,如果可能的话.

我使用的push_front()和push_back()唯一的.因此,我不招致使用的其他任何费用insert()或remove().

我知道这两个容器O(1)都为这些功能提供了复杂性,deque与具有恒定时间的lists 相比,它具有分摊的恒定时间.

但我想知道哪个时间比另一个少,如果有的话.

几乎所有的编程语言都有一些使用动态数组的列表的实现，当它达到一定容量时会自动扩展。例如，Java 有ArrayList，C++ 有std::vector。

最近我了解了循环数组双端队列，它也是使用动态数组实现的。它们跟踪列表的起始索引，并使用模运算来访问元素。与数组列表一样，它们允许 O(1) 查找和 O(1) 在末尾插入，并且空间与 O(N) 成正比。但是，它们也允许在开头插入 O(1)。

（虽然 JavaArrayDeque实现了这种数据结构，但它不允许查找元素。C++std::deque似乎使用了不同的实现。）

如果这些数组双端队列具有与数组列表相同或更好的性能特征，那么为什么不总是将它们用作列表的默认实现呢？

我知道ArrayDeque在添加和删除简单列表时速度很快。我实际测试过，它的添加和删除比LinkedList更快。因为我知道它是作为数组实现的，那为什么不随机访问呢？

我在 Java src 中读取了 ArrayDeque.java 文件。但以我的英语能力我不太明白。我看过很多来自 Google 和 Stack Overflow 的文章，但没有得到我想要的答案。

总之，我想要的答案是：

1. 为什么 ArrayDeque 不是 Random Access？（我最好奇） 2. ArrayDeque 在什么情况下使用？3. ArrayDeque 是不是没有实现为Array？（是不是知道错了知识？）

非常感谢您的回复！

我在学习Python数据结构时一直在学习队列，并想问一个有关其使用的问题。

我想有两种方法从队列中追加/弹出。第一种方法是使用deque.append()和deque.popleft()。另一种方法是使用deque.appendleft()和deque.pop()。两者之间有性能差异吗？如果没有，根据您的经验，哪一种更常用？您是否出于其他原因推荐其中之一？

从我的角度来看，它们本质上做同样的事情，因为它们都实现先进先出。我们将非常感谢您的意见！