标签: deque

跟进std :: deque的内存开销对heque的影响是什么？

Visual C++ deque使用以下方法根据容器元素类型管理块:

#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) */

这导致小元件的内存占用非常大.通过将第一行中的16更改为128,我能够大幅减少大型所需的占用空间deque<char>.在100m push_back(const char& mychar)调用后,Process Explorer Private Bytes从181MB减少到> 113MB .

• 任何人都能证明这些价值#define吗？
• 其他编译器如何处理deque块大小调整？
• 对于100m push_back调用 的简单测试,它们的占用空间(32位操作)是deque<char>什么？
• STL是否允许在编译时覆盖此块大小而不修改 <deque>代码？

我有一个deque对象,它包含大量数据.我想从队列的前面提取4096个元素(我将它用作一种FIFO).似乎应该有这样做的方式,而不必迭代超过4096个pop请求.

这是正确/有效/愚蠢的吗？

A = arange(100000)
B = deque()
C = [] # List will do 
B.extend(A) # Nice large deque

# extract 4096 elements
for i in xrange(4096):
   C.append(A.popleft())

deque.popleft()并且list.pop(0)似乎返回相同的结果.他们之间有什么性能差异和原因？

我已经读过,在a的末尾添加项目的时间复杂度std::vector是分摊的常量,并且在a的顶部和底部插入项目std::deque是常量.因为这两个容器都具有随机访问迭代器,因此访问任何索引处的元素是不变的.如果我有任何这些事实错误,请告诉我.我的问题是如果访问a中的元素std::vector或者std::deque是不变的那么为什么通过擦除O(n)去除元素的时间复杂度.这里的答案之一说明通过擦除元素是O(n).我知道擦除会删除起始迭代器和结束迭代器之间的元素,所以答案基本上意味着它O(n) 取决于两个迭代器之间的元素的数量,并且从任何索引中的vector/deque中删除单个元素将为零？

有什么理由说std::deque的pop_front(),并pop_back()没有noexcept在C++ 11或更高或者是只是忘记了吗？

关于deque中的迭代器失效,我有点困惑.(在这个问题的背景下)

以下是摘自 - The C++标准库:教程和参考,作者:Nicolai M. Josuttis

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

以下是SGI网站的摘录:

deque的迭代器失效的语义如下.Insert(包括push_front和push_back)使引用deque的所有迭代器无效.在双端队列中间擦除使所有引用双端队列的迭代器无效.只有当它指向已擦除的元素时,在双端队列的开头或结尾处擦除(包括 pop_front和pop_back)才会使迭代器无效.

恕我直言,deque是块的集合,第一个块在一个方向上生长,最后一个块在相反方向上生长.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front 不应该对deque迭代器产生任何影响(我同意Josuttis).

什么是正确的解释？标准对此有何看法？

到目前为止,我已经了解了如何std::deque在引擎盖下实现,并发现它类似于指向n字节数组的指针数组,其中数据实际存储在其中.所以现在我有几个与deques相关的问题.

描述我目前对其结构的了解的图片:

问题是:

1. 当push_front正在执行操作并且数据块0中没有可用空间时,在堆上分配新的数据块,并且将指向这个新分配的内存的指针插入到'Map'数组中,就像在普通数组中一样 - 在O(number_of_blocks)中)时间,是吗？

2. 如何对这种野兽进行排序？无法想象更好的事情然后将所有数据复制到数组中,对其进行排序,然后将其放回原处.但这种方法需要O(n)辅助内存......但是!std::sort提供类似的接口,用于排序std::vector和std::deque.如何实现不同数据结构的不同算法？使用模板专业化？如果是这样,为什么std::list不能使用std::sort？或者,也许,std::sort不关心这个容器的内部结构和只使用迭代器和方法,是在这两个相似的std::vector和std::deque(如operator[],size()等)？这个想法听起来很合理,并且回答"为什么不能std::sort排序std::list？" 变得明显.

3. 如何选择数据块的大小？你会说"它依赖于实现",但请详细说明解决方案背后的不同实现和动机.

需要澄清这里.谢谢.

我想在决定是否弹出之前检查队列前面的条件.如何在collect.deque的python中实现这一点？

list(my_deque)[0]

表现难看,表现不佳.

我遇到了以下崩溃:

由于未捕获的异常'NSInternalInconsistencyException'而终止应用程序,原因:'无法使类型的视图出列:具有标识符的UICollectionElementKindCellCell - 必须为标识符注册nib或类或在故事板中连接原型单元'

我在ViewDidLoad中有以下内容:

[self.collectionView registerClass:[UICollectionViewCell class] 
        forCellWithReuseIdentifier:@"Cell"];

崩溃的行在cellForItemAtIndexPath回调中:

UICollectionViewCell *cell = [collectionView 
    dequeueReusableCellWithReuseIdentifier:@"Cell" forIndexPath:indexPath];

我一直在寻找几个小时,但找不到任何解决方案.我已经尝试了子类化UICollectionViewCell,但得到了同样的错误.

使用断点,我确定在执行dequeueReusableCellWithReuseIdentifier回调之前正在执行registerClass行.

这是项目欧拉问题49的一个(略微混乱)尝试.

我应该直截了当地说这deque不是一个好选择!我的想法是缩小质数集来测试成员资格会导致循环加速.然而,当我意识到我应该使用a set(并且不用担心删除元素)时,我的速度提高了60倍.

from collections import deque
from itertools import permutations
from .sieve import sieve_of_erastothenes  # my own implementation of the Sieve of Erastothenes

primes = deque(prime for prime in sieve_of_erastothenes(10000) if prime > 1000 and prime != 1487)  # all four-digit primes except 1487
try:
    while True:
        prime = primes.popleft()  # decrease the length of primes each time to speed up membership test
        for inc in xrange(1,10000 + 1 - (2 * prime)):  # …