标签: deque

当我必须插入很少的元素时,哪种方式可以更快地排队和出列,是否数组比链表更好？

我需要插入一些元素,我必须从队列中删除并读取已删除的元素.如果是数组,我可能每次删除元素时都要修改索引.插入和删除也可能同时发生.

从下面的案例中哪个更好？

typedef struct{
    mylist list;
    struct mylistQ *next;
}mylistQ;

数组代码

 static mylist myListQ[QUEUESIZE+1];
int qLast = 0;

void enqueue_element(mylist qItem)
{
        myListQ[qLast] = qItem;
    qLast++;
}

mylist dequeue_element()
{
 retryq:
   if(qLast >0) {
    mylist qReturn = myListQ[0];  
    int i;
    for (i = 0; i < qLast - 1; i++){
        myListQ[i] = myListQ[i + 1];
    }
    qLast--; 
    return qReturn;
     }
   else {
    goto retryq;
    }
}

链接列表

 int qLast = 0;

mylistQ *headElement = NULL;   
mylistQ *tailElement = NULL; …

在linux上,std :: deque在程序退出之前不会释放内存.完整的代码如下.任何帮助将不胜感激!

#include <deque>
#include <vector>
#include <string>
#include <iostream>
#include <boost/shared_ptr.hpp>
#include <queue>
#include <list>
#include <cstdio>
#include <cstdlib>

typedef  boost::shared_ptr<std::vector<int> > VecPtr;
typedef  std::deque< VecPtr  > QueueType;

 char buf[1024];
 char line[1024];

 int main()
 {

  {

    int v=0;
    QueueType  deq;
    for(int i=0; i<30;++i)
    for(int j=0; j<1000;++j)
    for(int k=0;k<1000;++k)
    {
       VecPtr p( new std::vector<int>);
       deq.push_back(p);
    }

    std::cout<<"Done with increasing deq:deq size="<<deq.size()<<std::endl;
    sleep(20);

    std::cout<<"start decreasing deq size"<<std::endl;
    while(deq.size()>0)
    {
      deq.pop_front();
    }
    std::cout<<"done with decreasing deq size,deq size="<<deq.size()<<std::endl;
  }
  std::cin.getline(line,sizeof(line));
  return …

我有一个现有的算法,如果可能的话我需要稍微优化它.目前,此算法中的大量更改不是一种选择.算法与实例一起工作std::vector< std::vector<unsigned char> >.它看起来像这样:

typedef std::vector<unsigned char> internal_vector_t;
std::vector< internal_vector_t > internal_vectors; 

while (fetching lots of records) {
   internal_vector_t tmp;
   // reads 1Mb of chars in tmp...
   internal_vectors.push_back(tmp);
   // some more work
}

// use this internal_vectors

该算法internal_vectors使用push_back()在internal_vector_t的实例中插入了很多次.internal_vector_t的大多数实例的大小为1 Mb.由于internal_vectors未知的大小没有事先做过reserve().

我不理解的第一件事是当internal_vectors达到其当前容量时发生的事情,需要分配一个新块并将其当前内容复制到更大的内存块中.由于大多数块的大小都是1Mb,因此复制操作很长.我是否应该期望编译器(gcc 4.3,MS VC++ 2008)能够优化它以避免复制？

如果复制是不可避免的,会改变std::deque帮助吗？我认为std :: deque因为我仍然需要通过像internal_vectors [10]这样的索引来访问.像这样:

typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors; 
// the same while

据我所知std::deque,不需要重新定位曾经分配过.我是对的,std::deque在这种情况下会重新减少分配和复制push_backs吗？

任何在性能关键代码中使用过“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 的当前定义。我几乎拒绝这个解决方案，因为现在我使用这个混蛋的 …

我正在学习Python并且一直试图制作一个双端队列.但是,我输出不正确,我不知道为什么.我的代码如下:

p = [2, 1], [1, 1]
init_q= deque()

init_q.append(p)
for i in range(len(p)):
    for j in range(len(p[i])):
        temp = p[i][j]
        p[i][j] = 0
        init_q.append(p)
        p[i][j] = temp

while init_q:
    print init_q.pop()

在这段代码中,我接受一个列表,然后我想创建一个包含5个列表的队列,其中4个在不同的位置有一个0,我想要的结果是:

([2, 1], [1, 1])
([0, 1], [1, 1])
([2, 0], [1, 1])
([2, 1], [0, 1])
([2, 1], [1, 0])

但是,我得到的结果是:

([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])

我正在尝试使用链表在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) { …

在我的代码库上运行cppcheck并收到以下错误:

Dangerous iterator comparison using operator< on 'std::deque'.

但是deque的迭代器是一个随机访问迭代器,随机访问迭代器支持不等式运算符.什么给出了什么？

例:

#include <deque>

int main()
{
    std::deque<int> d;
    std::deque<int>::iterator di1 = d.begin();
    std::deque<int>::iterator di2 = d.end();

    if (di1 < di2)
    {
        // (error) Dangerous iterator comparison using operator< on 'std::deque'.
    }

    return 0;
}

编辑:此错误已通过cppcheck ticket#5926提交并修复.

嗨,我使用添加和提供添加我的元素在最后的步伐.两者都返回布尔值,两者都不会抛出除NPE之外的任何异常.

 public class ArrayDequeDemo {

  public static void main(String[] args) {


    // Create ArrayDeque elements.
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    deque.add(10);
    deque.offer(30);

   }
 }

两者都会通过返回布尔值在最后的位置添加元素.

JAVA实施

//For Add and Offer Both
   public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

这个关于某些数据结构的算法复杂性的wiki.python.org页面说明了collections.deque对象的以下内容:

deque(双端队列)在内部表示为双向链表.(好吧,一个数组列表而不是对象,以提高效率.)两端都可以访问,但即使看中间也很慢,中间增加或删除速度较慢.

两个问题:

1)是否可能添加到中间deque？我没有在API中看到任何方法.

2)为什么删除(或添加)比在中间查找要慢deque？它是一个双向链表,因此一旦找到要添加的对象,添加/删除应该是一个恒定时间操作.

我能编码std::max_element(std::begin(my_deque), std::end(my_deque))吗？

我问,因为我知道deque不能保证连续存储,所以我想知道当使用涉及迭代器的函数时它是否会正常运行std::max_element？

非常感谢你!