为什么 shrink_to_fit （如果请求被满足）导致重新分配？

Question

给定一个包含 v.size() == 3 和 v.capacity() == 5 的容器 v，我的理解是对 v.shrink_to_fit() 的调用可以是 满足，如果是，它会导致 v.capacity() 变成 3.

但是，这是以重新分配为代价的。

为什么？是否可以释放未使用的内存而不为剩余的内存重新分配一块内存？

可能这个问题的根源在于更原始的命令，如 new/delete 和 malloc/free 是如何工作的。

Answer 1

底层内存管理系统定义了什么是可能的，通常，它们不允许 return 部分分配的内存：如果你得到 n 字节，你要么 return n 字节，要么什么都没有。
返回最后的 m 字节（m < n），或者更糟的是，returning m 字节在 n 字节的中间，当然可以提供，但请考虑正确处理此问题所需的额外复杂性。
当然，可能有一些确实提供了它，但是你的 C++ 编译器和语言定义不一定知道 OS 中它下面的运行，所以他们必须接受需要重新分配的可能性。请注意，他们不保证需要它 - 他们只是期望它。

Answer 2

容器本身并不 allocate/deallocate 内存，而是它的分配器。

为了使（向量的）分配器能够解除分配内存，需要为其提供与指向它为向量数据分配的内存的指针完全相同的指针。

这里是矢量数据的开始，不是“不再使用”数据的开始。

基本上，我们在谈论这个分配器的 allocation/deallocation 方法：

pointer allocate( size_type n, const void * hint = 0 );
void deallocate( T* p, std::size_t n );

deallocate 的参数 T* p 将与从 allocate 返回的指针相同（== 向量数据的开头）。这是 vector 的实现将传递给 deallocate 的内容。

当然可以想象有一个自定义向量实现，它能够将 [data, data+size] 范围内的任何指针传递给分配器 deallocate 方法。人们可以构建这样一个分配器来处理它。但是所有其他分配器都需要符合这个 API，也是标准分配器。

那么像这样的东西就需要能够“工作”：

int* p = new int[100];
delete [] (p + 50);  // imagine making this work

这会增加额外的复杂性、性能和其他问题。

Answer 3

事实上，标准只是允许分配器实现在收缩时重新分配（如果需要的话）。我不知道它在 C++ 库实现中是否常见，但我记得一些数据库分配器使用不同的磁盘段池，一些用于较小的块，一些用于较大的块。基本原理是小块很多而大块很少，因此隔离有助于减少较大块池的碎片。如果这种情况发生在程序中，那么定义一个实现该规则的自定义分配器可能是有意义的。

事实上，标准说 shrink_to_fit 可以重新分配，只允许使用这样的自定义分配器。

为什么 shrink_to_fit （如果请求被满足）导致重新分配？

Why does shrink_to_fit (if the request is fulfilled) cause reallocation?

c++

memory-management

allocation