问题标签 [deque]

我是来自 C++/STL 的相对较新的 Java 程序员，我正在寻找具有这些特征的类（据我了解，C++ std::deque 具有）：

1. O(1) 在开头/结尾插入/删除的性能
2. 按索引查找的 O(1) 性能
3. 是可增长的集合（不需要固定大小的界限）

有与此等效的Java吗？我发现 Java 1.6 [ArrayDeque] 类具有插入/删除和可增长的特性，但似乎没有按索引查找，除非您调用不会为 O(1) 的 toArray()。

在访问复杂性、调整大小时重新分配等方面，我想要的是类似于 STL 向量的东西。我希望它支持任意索引范围，例如可以有索引从 -2 到 +7 或从 +5 到 + 的元素10. 我希望能够有效地 push_front。我也想要双向调整大小...

我知道我可以自己写这样的东西，但是如果有一个已经写好的库支持这个，请告诉我。

我需要一个队列，多个线程可以将内容放入其中，并且多个线程可以从中读取。

Python 至少有两个队列类，Queue.Queue和collections.deque，前者似乎在内部使用后者。两者都声称在文档中是线程安全的。

但是，队列文档还指出：

collections.deque 是无界队列的替代实现，具有不需要锁定的快速原子 append() 和 popleft() 操作。

我想我不太明白：这是否意味着双端队列毕竟不是完全线程安全的？

如果是这样，我可能无法完全理解这两个类之间的区别。我可以看到 Queue 添加了阻塞功能。另一方面，它失去了一些双端队列特性，比如对 in-operator 的支持。

直接访问内部双端队列对象是

x in Queue().deque

线程安全？

另外，当双端队列已经是线程安全的时，为什么队列要为其操作使用互斥锁？

正如标题所问。

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

我对双端队列中的迭代器失效感到有点困惑。（在这个问题的背景下）

以下是摘自 -- The C++ Standard Library: A Tutorial and Reference，作者 Nicolai M. Josuttis

除开头或结尾之外的任何元素的插入或删除 都会使引用双端队列元素的所有指针、引用和迭代器无效。

以下是SGI网站的摘录：

deque 的迭代器失效语义如下。Insert（包括push_frontand push_back）使所有引用双端队列的迭代器无效。在双端队列中间进行擦除会使所有引用该双端队列的迭代器无效。仅当迭代器指向被擦除的元素时，在双端队列（包括pop_frontand ）的开头或结尾进行 擦除才会使迭代器无效。pop_back

恕我直言，双端队列是块的集合，第一个块在一个方向上增长，最后一个块在相反方向上增长。

push_back, push_front不应该对双端队列迭代器产生任何影响（我同意 Josuttis 的观点）。

正确的解释是什么？标准对此有何评论？

我正在寻找 Java 解决方案，但任何一般性的答案也可以。

Vector/ArrayList 对于追加和检索是 O(1)，但对于 prepend 是 O(n)。

LinkedList（在 Java 中实现为双向链表）对于追加和前置是 O(1)，但对于检索是 O(n)。

对于上述所有内容，双端队列 (ArrayDeque) 为 O(1)，但无法检索任意索引处的元素。

在我看来，满足上述要求的数据结构内部有 2 个可增长列表（一个用于前置，一个用于附加），并且还存储一个偏移量以确定在检索期间从何处获取元素。

我正在使用 astd::deque来存储相当多的对象。如果我删除一堆这些对象，在我看来，它的内存使用量并没有减少，其方式与 std::vector 类似。

有没有办法减少它？我知道在向量中你必须使用“交换技巧”，我认为它也可以在这里工作，但我宁愿避免这样做，因为它需要复制容器中剩下的所有元素（因此要求你有足够的内存来存储每个对象两次）。我对双端队列的实现并不十分熟悉，但我对它的理解是，在没有大量副本的情况下可能实现这样的事情（而使用向量显然不是）。

我正在使用 VC++ (Dinkumware) STL，如果这有什么不同的话。

我必须在 a 上写一小段代码deque，但是如果有人可以帮助我使用其中一种方法（例如添加对象的方法），我不确定如何为这些方法编写代码到双端队列的来源），那么这会让我开始。我确信我可以管理其余的方法，只是目前我很困惑。

我有一个队列（来自Queue模块），我想获得对它的索引访问。（即，能够请求队列中的第 4 项，而无需将其从队列中删除。）

我看到一个队列在内部使用了一个双端队列，而双端队列具有索引访问。问题是，我怎样才能使用双端队列而不（1）弄乱队列，（2）破坏线程安全。

正如标题所暗示的，我的程序有问题，我使用 std::list 作为堆栈并迭代列表的所有元素。当列表变得非常大时，该程序花费的时间太长了。

有人对此有很好的解释吗？它是一些堆栈/缓存行为吗？

（通过将列表更改为 std::vector 和 std::deque 解决了这个问题（顺便说一句，这是一个了不起的数据结构），一切都突然变得更快了）

编辑：我不是傻瓜，我不会访问列表中间的元素。我对列表所做的唯一一件事就是在末尾/开头删除/添加元素并遍历列表的所有元素。而且我总是使用迭代器来迭代列表。