标签: deque

为什么通常不ArrayList实施双端,这将支持前面和后面的快速摊销？

使用后者而不是前者有不利之处吗？

(我不只是谈论Java - 我没有看到双端数组列表是任何其他语言的默认值,但Java只是一个很好的例子.)

*编辑:我最初称它们为"阵列deques",但这对我来说是一种误解; 我不是在谈论队列,而是双端阵列表.

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

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

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

我正在尝试输出字符串的旋转版本。我已经取了一个字符串，z="string"并从中创建了一个双端队列y=collections.deque(z) (deque(['S','t','r','i','n','g'])，并使用Rotate方法旋转了它。如何“转换”我旋转回双端字符串的双端队列对象？

As vector和dequeBoth都为push_back最后的元素提供了一个函数.

其中deque还提供了一个push_front在开头插入元素的功能,在这种情况下有点成本vector.

我的问题是,当我们通过使用实现相同的功能(push_back)时,为什么需要？ vectordequevector

我们知道std::deque::front()返回对deque的第一个元素的引用.我想知道这段代码是否总是安全的:

//deque of lambdas
deque<function<void(void)>> funs;

// then is some other place:
// take a lock
m.lock();
auto f = move(funs.front()); // move the first lambda in f
funs.pop_front(); // remove the element from deque //now the value is hold by f
m_.unlock(); // unlock the resorce
f(); //execute f

我已经尝试使用gcc-4.9这个代码并且有效,但我不知道我们是否可以认为这个代码是安全的!

任何在性能关键代码中使用过“deque”的人可能已经注意到（至少在 VS2010 附带的 STL 中）块大小是 16 字节。这是 VS2010 附带的头文件中的实际片段：

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 16 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

这不是新信息，请参阅关于 deque<T> 的额外间接寻址，了解有关此 decl 为何导致性能问题的更多详细信息。

我想在各种算法中使用双端队列，但如果我仅限于此实现，则不会。规避这个问题的最佳方法是什么？

1) 使用另一个不存在此问题的容器。如果是这样，有人可以给我指出一个没有 GNU 许可证限制的吗？

2) 创建一个新的容器类来解决此限制。这个新的容器类不会成为 std 命名空间的一部分。

3) 编辑“deque”头文件中的_DEQUESIZ 定义。IMO，我认为这是合法的，因为 _DEQUESIZ 的确切规范不是 STL 定义的双端队列概念的一部分。

4) 向双端队列（和关联的迭代器类）添加一个额外的模板参数，以允许在编译时指定块大小。该参数默认为 _DEQUESIZ 的当前定义。我几乎拒绝这个解决方案，因为现在我使用这个混蛋的 …

我正在尝试使用链表在java中实现双端队列。首先我想实现该方法addFirst()。这是我遇到的问题——当我添加几个字符串时，例如“一”、“二”和“三”，它插入正确，但是当迭代双端队列时，它只给出最后添加的对象，不是所有的对象。我有什么遗漏的吗？

public class Deque<Item> implements Iterable<Item> {
  private Node first;
  private Node last;
  private int N;

  public Iterator<Item> iterator() { return new DequeIterator(); }

  private class Node {
    private Item item;
    private Node next;
  }

  public Deque() {
    first = null;
    last = null;
    N = 0;
  }

  public boolean isEmpty() { return first == null || last == null; }
  public int size() { return N; }

  public void addFirst(Item item) {
  if (null == item) { …

我正在阅读这篇文章，它指出双端队列在顶部和底部提供有效的插入。然而，这篇文章在这里指出除后面之外的双端队列的时间复杂度是 O(n)。我认为如果双端队列具有有效的顶部和底部插入它将具有 O(1)，而向量仅在底部插入时应具有 O(1)。如果有人能澄清这一点，我将不胜感激

假设我std::vector<foo>现在知道向量末尾的插入是摊销常数。这意味着它可以是 O(1) 或 O(n) （因为它获取一个新的内存块，将旧的内容复制到新的内存块中）。我的问题是，当将项目复制到较新的内存块（据说更大）时，是否会再次调用对象的复制构造函数？（第一次调用复制构造函数是使用push_back），在我的情况下，在调整向量大小时会再次调用 foo 的复制构造函数吗？我知道使用 std::deque 不会调用复制构造函数，因为它将对象的地址存储在堆上并将它们维护在向量类型数据结构中。C++98 和 C++11 中的行为是否相同

我一直认为在C++标准模板库(STL)中,双端队列(deque)是一个带有圆形边界条件的大小可变数组(如矢量),这意味着有一个头指针i和一个尾指针j都指向某些数组的位置a[0..L-1].push_front是i--,push_back是j++,pop_front是i++,pop_back是j--.当指针i或j到达L或者-1,它再次出现在数组的另一端(0和L-1分别).如果数组大小耗尽(i==j插入新元素后的指针),则会将原始大小加倍的较大空间重新分配给a[]数据,并将数据复制到向量中.O(1)考虑到圆形边界条件,还有随机访问的时间.但有人告诉我,在STL双端队列中,实际上有一个指针阵列指向许多固定长度的数组段.它比圆形矢量复杂得多.不使用简单的圆形向量来实现双端队列的功能有什么好处？随机访问会变慢吗？