c++ - deque::shrink_to_fit内存保证

Question

由于我对内存有严格的要求，因此在从双端队列的开头删除一个范围后，我尝试使用deque::shrink_to_fit。但是，它不起作用，我只看到libstdc++使用带有副本的swap技巧实现了shrink_to_fit。这实际上意味着，除了获得更好的内存使用率之外，我暂时获得2倍的使用率，并因此获得了OOM版本。

我认为这限制了shrink_to_fit的可用性，并且我想知道标准中是否有/可以保证？我在草稿副本(N3035)中进行了查找，但只看到“这是不具有约束力的请求...”。我意识到为什么它是非绑定(bind)的，以及为什么它不能用于vector，但是从我对deque实现的了解中，应该可以提供一些内存保证(并且在libc++中，看起来确实可以做到这一点)以更智能的方式)。是否存在与特定实现相关的保证？

Answer 1

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是做什么的。但它也将实现一个数组数组。

可以看到，尽管所有实现都在相同的数据结构上运行(以符合复杂性和无效性要求)，但仍有一些重要的设计决策要由实现来决定，并且每个实现都在努力提供其实现的内容。认为最适合其客户。