deque::shrink_to_fit因为我有严格的内存要求,所以我试图在从deque开头删除一个范围后使用.但是,它没有用,我只是看到libstdc ++实现了shrink_to_fit使用交换技巧和副本.这实际上意味着,而不是更好的内存使用,我得到2倍的使用一段时间,并因此而得到OOM-ed.
我认为这限制了可用性,shrink_to_fit我想知道标准中是否有/可以保证？我在草稿副本(N3035)中查了一下,只看到"这是一个非约束性请求......".我知道为什么它是非绑定的,也是为什么它不能完成vector,但从我对deque实现的了解,它应该可以提供一些内存保证(并且看看libc ++,它似乎做到了更聪明的方式).是否有保证,因为它们与具体实施有关？
libstdc ++和libc ++实现shrink_to_fit看起来都符合我的要求.但它们非常不同,主要是因为这两个实现遵循不同的类不变量.
首先,对于那些不知道的人来说,std::deque是一个指针数组(通常T*,但是一个自定义分配器可以推广)到固定大小的数组T.指针数组可以被视为循环缓冲区,或者可以作为缓冲区,可以将其数据的开头从缓冲区的开头滑开.
这个答案将集中在deque的固定长度数组上.
的libstdc ++
libstdc ++实现有一个不变量,即从来没有空数组deque.如果a pop_front或pop_back创建一个空数组,则在擦除期间释放该数组.这种设计减少了deque::shrink_to_fit实际可以实现的功能,因为deque它始终处于或非常接近最小内存占用.
只有libstdc ++ shrink_to_fit可以证明它可以通过这样做来消除数组,它才会执行复制和交换.例如,a deque可以保存由三个固定长度数组支持的1010个值,每个数组的容量为1000个值.dequemight中的第一个元素从第一个数组中的第995位开始.因此,第一和第三阵列中的大多数(但不是全部)都是空的.复制/交换将分配两个新阵列,将1010个元素复制/移动到这两个阵列中,然后解除分配旧的3个阵列.
的libc ++
libc ++实现遵循略微不同的设计,旨在加速FIFO队列.当a pop_front(或pop_back)清空数组时,除非前面(或后面)已有空数组,否则不会释放该数组.即libstdc ++不变量是整个过程中从不存在空数组时deque,libc ++不变量是在前面和后面可以有零个或一个空数组deque.这样做的理由是,如果一个push_back(或push_front)需要一个新数组,它首先在另一端寻找一个空数组,deque并从那里开始,然后再分配一个新数组.给定具有近似恒定大小的FIFO队列,该设计将达到使得pop_front/ push_back序列永远不会分配新阵列的状态.相反,阵列从前面deque到后面再循环(反之亦然).
如果存在,libc ++ shrink_to_fit将丢弃其两端的空数组deque.相比之下,libstdc ++不需要这样做,因为空数组永远不存在.libc ++ shrink_to_fit不会通过复制/交换操作将值"移位"到更接近块的开头,从而进一步减少内存占用.
结果是libc ++ shrink_to_fit永远不会使引用无效,而libstdc ++ shrink_to_fit经常会这样做.请注意,规范shrink_to_fit旨在允许引用无效,尽管现在我看,我认为它错误地没有(它必须为vector::shrink_to_fit,并且措辞deque来自措辞vector).
这两种实现也shrink_to_fit将是底层缓冲区T*,尽管这具有相对较小的影响,因为缓冲区的内存占用量T*通常远小于阵列的内存占用量.每个libc ++数组通常占用4096个字节(1页),而每个libstdc ++数组通常占用512个字节.
我不知道VC++的deque作用.但它也将实现一组数组.
可以看出,虽然所有实现都在相同的数据结构上运行(为了符合复杂性和无效要求),仍然有一些重要的设计决策留给实现,每个实现都努力提供它认为最适合其客户.