由于我对内存有严格的要求,因此在从双端队列的开头删除一个范围后,我尝试使用deque::shrink_to_fit
。但是,它不起作用,我只看到libstdc++使用带有副本的swap技巧实现了shrink_to_fit
。这实际上意味着,除了获得更好的内存使用率之外,我暂时获得2倍的使用率,并因此获得了OOM版本。
我认为这限制了shrink_to_fit
的可用性,并且我想知道标准中是否有/可以保证?我在草稿副本(N3035)中进行了查找,但只看到“这是不具有约束力的请求...”。我意识到为什么它是非绑定(bind)的,以及为什么它不能用于vector
,但是从我对deque
实现的了解中,应该可以提供一些内存保证(并且在libc++中,看起来确实可以做到这一点)以更智能的方式)。是否存在与特定实现相关的保证?
最佳答案
shrink_to_fit
的libstdc++和libc++实现都符合我的要求。但是它们有很大不同,主要是因为两个实现遵循不同的类不变式。
首先,对于不知道的人,std::deque
是一个指针数组(通常为T*
,但是自定义分配器可以将其推广为固定大小的T
数组)。指针数组可被视为循环缓冲区,或可将其数据的起始位置从缓冲区的起始位置移开的缓冲区。
这个答案将只集中在双端队列的固定长度数组上。
libstdc++
libstdc++实现具有不变性,即deque
中永远不会有空数组。如果pop_front
或pop_back
创建一个空数组,则在擦除过程中将释放该数组。这种设计减少了deque::shrink_to_fit
实际可以实现的功能,因为deque
始终处于或非常接近最小内存占用量。
仅当libstdc++ shrink_to_fit
可以证明自己可以消除数组时,它才执行 copy-and-swap 。例如,一个deque
可能包含1010个值,这些值由三个容量为1000个值的固定长度数组支持。 deque
中的第一个元素可能在第一个数组中的位置995处开始。因此,大多数(但不是全部)第一和第三数组为空。复制/交换将分配两个新数组,将1010元素复制/移动到这两个数组中,然后取消分配旧的3个数组。
libc++
libc++实现遵循略有不同的设计,旨在加快FIFO queues的速度。当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
是做什么的。但它也将实现一个数组数组。
可以看到,尽管所有实现都在相同的数据结构上运行(以符合复杂性和无效性要求),但仍有一些重要的设计决策要由实现来决定,并且每个实现都在努力提供其实现的内容。认为最适合其客户。
关于c++ - deque::shrink_to_fit内存保证,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23980527/