- stl 的basic_string 中的_S_create 函数使用这三个变量来计算实际分配的大小。有谁知道为什么?
_S_create 的接口是
_Rep* _S_create(size_type __capacity, size_type __old_capacity, const _Alloc& __alloc)
为什么需要 __old_capacity 参数?
PS。这是gnu stl。
实际代码很好地解释了它是如何使用_PageSize
and的_malloc_header_size
,如果您只是懒得阅读评论(而且不阅读评论是相当可耻的,毕竟有人可能花更多的时间来写这些评论而不是我写这个答案):
// The standard places no restriction on allocating more memory
// than is strictly needed within this layer at the moment or as
// requested by an explicit application call to reserve().
// Many malloc implementations perform quite poorly when an
// application attempts to allocate memory in a stepwise fashion
// growing each allocation size by only 1 char. Additionally,
// it makes little sense to allocate less linear memory than the
// natural blocking size of the malloc implementation.
// Unfortunately, we would need a somewhat low-level calculation
// with tuned parameters to get this perfect for any particular
// malloc implementation. Fortunately, generalizations about
// common features seen among implementations seems to suffice.
// __pagesize need not match the actual VM page size for good
// results in practice, thus we pick a common value on the low
// side. __malloc_header_size is an estimate of the amount of
// overhead per memory allocation (in practice seen N * sizeof
// (void*) where N is 0, 2 or 4). According to folklore,
// picking this value on the high side is better than
// low-balling it (especially when this algorithm is used with
// malloc implementations that allocate memory blocks rounded up
// to a size which is a power of 2).
Sebastian 做对了(尽管它的写法略有不同):
// The below implements an exponential growth policy, necessary to
// meet amortized linear time requirements of the library: see
// http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
// It's active for allocations requiring an amount of memory above
// system pagesize. This is consistent with the requirements of the
// standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
__capacity = 2 * __old_capacity;
在__pagesize
这里使用,将其四舍五入...
const size_type __adj_size = __size + __malloc_header_size;
if (__adj_size > __pagesize && __capacity > __old_capacity)
{
const size_type __extra = __pagesize - __adj_size % __pagesize;
__capacity += __extra / sizeof(_CharT);
// Never allocate a string bigger than _S_max_size.
if (__capacity > _S_max_size)
__capacity = _S_max_size;
__size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
}
我的实现没有_subpagesize
,但我希望这是一个类似的舍入。
在不查看 libstdc++ 或询问任何有明确信息的人的情况下,一种可能的实现是
size_type __actual_capacity = max(__capacity, 2 * __old_capacity);
// do other stuff to create a _Rep.
这确保了几何增长,同时也保证了至少与绝对需要一样多的内存。