标签: deque

我不得不从python 2.7改为2.6.
我一直在使用带有maxlen属性的双端队列,并且一直在检查maxlen是什么.显然你可以在python 2.6中使用maxlen,但在2.6 deques中没有maxlen属性.
在python 2.6中检查双端队列的maxlen是什么最干净的方法是什么？

在2.7中:

from collections import deque
d = deque(maxlen = 10)
print d.maxlen

在2.6中,可以使用deque并且maxlen正常工作,但是maxlen不是可以引用的属性.

干杯

我有一个现有的算法,如果可能的话我需要稍微优化它.目前,此算法中的大量更改不是一种选择.算法与实例一起工作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背后的动机是提供一个有效的随机访问容器push_front.

与deque相比,vector的常见优点包括更快的遍历at(),但主要是它的C兼容性,因为它保证了连续的内存.Deque没有,因为它是一大堆内存,每个都包含许多值.

我糊涂了.0除了索引之后保留的内存之外,为什么deque不是像向量一样构建,而是在索引之前保留内存size-1？这将保证连续内存,启用高效push_front,甚至在解除引用迭代器时避免额外的间接.

为了最小化插入期间的移位,要移位的包含值将取决于插入点.如果在索引n之前插入,则将size()/2值n向左移动.否则后移右值n.

我错过了什么是非常重要的,deque是一组价值数组而不是一个大数组？

我在Qt项目的几行代码上每1秒附加到Qvector.我注意到在STL deque中可以更好地在向量中添加一个新元素.什么是等效或类似的Qt方式？因为我在Qt库中找不到任何内容.

胡里奥

通过使用boost或其他方式？

我想创建一个函数,d从(并包括)索引iStart到索引0中获取deque的子集,转换为新的deque,但也将这些值设置d为0.我想到了这个:

std::deque<int> CreateSubset(std::deque<int>& d, int iStart )
{
   int iSubsetSize = iStart+1;
   std::deque<int> subset(iSubsetSize); // initialise a deque of a certain size.

   std::deque<int>::iterator it = d.begin();

   subset.assign (it, d.begin()+iStart+1);

   for(;it != d.begin()+iStart+2; it++)
   {
     *it = 0;
   }  
   return subset;
}

但它看起来很可怕 - 有更好的方法吗？

我正在阅读有关deques vs vectors的文章,并且遇到了它的维基百科条目,其中说deque使用动态数组的三种可能实现之一是:

从底层数组的中心分配deque内容,并在到达任一端时调整底层数组的大小.这种方法可能需要更频繁的调整并浪费更多空间,特别是当元件仅插入一端时.

我想知道是否有任何实际使用此中心分配策略的STL(或STL风格)实现？

我问,因为这个策略看起来很吸引人,因为它只涉及一个底层数组,因此消除了内存不连续性问题,这可能是与之deque相比时唯一的主要问题vector.如果我理解正确,这很可能是std::vector允许O(1)pop_front(摊销)或替代deque内存连续性保证的替代品.我认为这是以a的缓冲空间加倍为代价的std::vector,这不是我用例的主要问题.

此外,在这样的容器中间插入/删除是否需要std::vector平均一半的时间？

更新:

正如@Lightness Races in Orbit指出的那样,这样的实施将不会在现行标准下使用,因为没有人可以从STL的每份合同的优势中受益,并且每个人都会受到不利影响.关于缺点的另一个问题是:

是否可以实现一个新的 vector或deque类似的容器(比如说bivector),除了功能/运营商之外std::vector,

1)提供(摊销)恒定时间push_front()和pop_front()操作

2)增加大小后保证内存连续但不保证迭代器有效性？

我想在幕后有一个阵列,很多间接/性能问题deque就会消失.

我正在查看Python deque的文档,它看起来像构造函数deque([iterable[, maxlen]]).有没有办法用最大长度制作一个空的双端队列(也就是说,没有指定可迭代的)？

嗨,我在Robert Sedgewick的Algorithms第4版中遇到了一个问题.

出队排序.解释你如何对一副牌进行排序,限制是唯一允许的操作是查看前两张牌的值,交换前两张牌,以及将顶牌移动到牌组的底部.

我希望有人可以解释如何做到这一点,我真的迷失了.谢谢

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

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

两个问题:

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

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

我正在处理LeetCode（在这里）上的问题。解决问题后，我想到了：

class MovingAverage {
    std::deque<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push_back(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage[0];
            numsToAverage.pop_front();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

之后，我看到另一个解决方案与我的非常相似，但是使用了一个队列。出于好奇，我只将双双队列交换到队列中，然后从第18个百分位数（双队列）跳到第56个百分位数（队列）。这是队列代码：

class MovingAverage {
    std::queue<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize …