由于我对内存有严格的要求,因此在从双端队列的开头删除一个范围后,我尝试使用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_frontpop_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/

10-15 06:28