deque::shrink_to_fit内存保证

Question

我试图使用deque::shrink_to_fit后，删除范围从开始的deque，因为我有严格的内存要求。但是，它没有起作用，我只是看到libstdc++使用带有副本的交换技巧实现了shrink_to_fit。这实际上意味着，我没有更好地使用内存，而是得到了一段时间的2倍的使用，并因此获得了OOM-ed。

我认为这限制了shrink_to_fit的可用性，我想知道在标准中是否有任何保证？我在草稿副本(N3035)中查找了它，只看到了“这是一个非绑定请求.”。我知道为什么它是不绑定的，也知道为什么不能在vector上实现它，但是根据我对deque实现的了解，应该可以提供一些内存保证(看看libc++，它似乎以一种更聪明的方式来实现)。是否有任何保证，因为它们与具体的执行有关？

Answer 1

libstdc++和libc++的shrink_to_fit实现看起来都符合我的要求。但是它们非常不同，很大程度上是因为这两种实现遵循不同的类不变量。

首先，对于那些不知道的人，std::deque是一个指针数组(通常是T*，但自定义分配器可以将其推广到固定大小的T数组)。指针数组可以被看作是循环缓冲区，也可以看作是一个缓冲区，它可以将其数据的开始从缓冲区的开始处移开。

这个答案将集中在deque的固定长度数组上。

libstdc++

libstdc++实现具有一个不变量，即deque中从来没有空数组。如果pop_front或pop_back创建一个空数组，则该数组在擦除期间被取消分配。这种设计减少了deque::shrink_to_fit实际可以实现的目标，因为deque总是处于或非常接近最小内存占用的水平。

只有当libstdc++ shrink_to_fit能够向自己证明它可以通过这样做消除数组时，它才会执行副本&交换。例如，一个deque可以保存由三个固定长度数组支持的1010个值，每个数组的容量为1000。deque中的第一个元素可能从第一个数组的位置995开始。因此，第一个和第三个数组的大部分(但不是全部)都是空的。复制/交换将分配两个新数组，将1010元素复制/移动到这两个数组中，然后释放旧的3个数组。

libc++

libc++实现遵循一个稍微不同的设计，目的是加快FIFO队列的速度。当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是做什么的。但它也将实现一个数组数组。

可以看到，虽然所有实现都在相同的数据结构上运行(为了符合复杂和无效的需求)，仍然有一些重要的设计决策留给实现，每个实现都努力交付它认为对客户最好的东西。