std::vector内存申请增长率

admin管理员组

文章数量:1612060

(Owed by: 春夜喜雨 http://blog.csdn/chunyexiyu)
注：代码参考使用的windows下c++11的vector实现

vector中的数组长度是如何增长的，倍增方式吗？
初始vector内部带有空间吗，还是初始空间大小为0呢？
从vector模板库实现中找一找，可以找到相关的线索。

在vector的定义中，可以看到：
当push_back/emplace_back调用后，进入内部的处理中；
可以看到，当空间用尽时，进入_Emplace_reallocate处理。

bool _Has_unused_capacity() const noexcept
{// micro-optimization for capacity() != size()
  return (this->_Myend() != this->_Mylast());
}
template<class... _Valty>
decltype(auto) emplace_back(_Valty&&... _Val)
{// insert by perfectly forwarding into element at end, provide strong guarantee
  if (_Has_unused_capacity())
  {
    return (_Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...));
  }
  _Ty& _Result = *_Emplace_reallocate(this->_Mylast(), _STD forward<_Valty>(_Val)...);
  return (_Result);
}

在_Emplace_reallocate实现中：
使用_Calculate_growth(_Newsize)函数中来计算新的数组容量_NewCapacity，并在后续进行分配与使用。

_NODISCARD size_type max_size() const noexcept
{// return maximum possible length of sequence
  return (_Min_value(static_cast<size_type>((numeric_limits<difference_type>::max)()), _Alty_traits::max_size(this->_Getal())));
}
[[noreturn]] static void _Xlength()
{// report a length_error
  _Xlength_error("vector<T> too long");
}
template<class... _Valty>
pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val)
{// reallocate and insert by perfectly forwarding _Val at _Whereptr
  // pre: !_Has_unused_capacity()
  const size_type _Whereoff = static_cast<size_type>(_Whereptr - this->_Myfirst());
  _Alty& _Al = this->_Getal();
  const size_type _Oldsize = size();
  if (_Oldsize == max_size())
  {
    _Xlength();
  }
  const size_type _Newsize = _Oldsize + 1;
  const size_type _Newcapacity = _Calculate_growth(_Newsize);
  ...
  const pointer _Newvec = _Al.allocate(_Newcapacity);
  const pointer _Constructed_last = _Newvec + _Whereoff + 1;
  pointer _Constructed_first = _Constructed_last;
  ...
}

下来看看_Calculate_growth如何进行分配方式计算的

size_type _Calculate_growth(const size_type _Newsize) const
{// given _Oldcapacity and _Newsize, calculate geometric growth
  const size_type _Oldcapacity = capacity();
  if (_Oldcapacity > max_size() - _Oldcapacity / 2)
  {
    return (_Newsize);	// geometric growth would overflow
  }
  const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
  if (_Geometric < _Newsize)
  {
    return (_Newsize);	// geometric growth would be insufficient
  }
  return (_Geometric);	// geometric growth is sufficient
}

分配方式的代码也很简单，主要关注这一行即可：
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
很明显，主要是使用老的容量的1.5倍。
old容量为0时呢？使用容量1返回；old容量为1时呢，使用_NewSize即2返回；其它情况使用1.5倍返回。

初始容量是否为0呢？如果不指定参数的话，从定义看是的：容量的几个指针初始化都都用的缺省()进行初始化，也即初始容量为0。

template<class _Val_types>
class _Vector_val	: public _Container_base
{
public:
  ...
  _Vector_val():_Myfirst(), _Mylast(), _Myend()
  {// initialize values
  }
  pointer _Myfirst;	// pointer to beginning of array
  pointer _Mylast;	// pointer to current end of sequence
  pointer _Myend;	// pointer to end of array
};
template<class _Alloc_types>
class _Vector_alloc
{// base class for vector to hold allocator
  ...
  _Vector_alloc():_Mypair(_Zero_then_variadic_args_t())
  {// default construct allocator
  }
  ...  
  _Compressed_pair<_Alty, _Vector_val<_Val_types>> _Mypair;
};
template<class _Ty,	class _Alloc = allocator<_Ty>>
class vector : public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>
{
  ...
  vector() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Alty>)
  : _Mybase()
  {// construct empty vector
  }
  ...
}

那windows下vector分配的大小可以显式的预测，vector分配时，按照：1，2，3，4，6，9，13，19，28，42… 进行分配。
vecotr初始容量使用的0，如果不添加内容，不会产生堆内存的申请；当插入元素时，才会产生堆内存申请，同时前期分配空间大小增长比较小，后续慢慢增长比较大。
另外，如果想对vector瘦身，使得cacpacity和size一致，可以使用shrink_to_fit函数来做。

测试程序，分别在windows下和linux下运行该测试程序，看看windows下与linux是否有所不同

#include <vector>
#include <stdio.h>
int main()
{
  std::vector<int> array;
  for (int i = 0; i < 30; i++) {
     printf("array size-%d, array capacity-%d\n", array.size(), array.capacity());
     array.push_back(i);
  }
  return 0;
}

windows下运行结果，可以看出符合预期，按照1.5倍方式进行vector分配：

array size-0, array capacity-0
array size-1, array capacity-1
array size-2, array capacity-2
array size-3, array capacity-3
array size-4, array capacity-4
array size-5, array capacity-6
array size-6, array capacity-6
array size-7, array capacity-9
array size-8, array capacity-9
array size-9, array capacity-9
array size-10, array capacity-13
array size-11, array capacity-13
array size-12, array capacity-13
array size-13, array capacity-13
array size-14, array capacity-19
array size-15, array capacity-19
array size-16, array capacity-19
array size-17, array capacity-19
array size-18, array capacity-19
array size-19, array capacity-19
array size-20, array capacity-28
array size-21, array capacity-28
array size-22, array capacity-28
array size-23, array capacity-28
array size-24, array capacity-28
array size-25, array capacity-28
array size-26, array capacity-28
array size-27, array capacity-28
array size-28, array capacity-28
array size-29, array capacity-42

linux运行结果，可以看出linux下是按照2倍的方式进行vector内存分配的，与windows下并不相同。

array size-0, array capacity-0
array size-1, array capacity-1
array size-2, array capacity-2
array size-3, array capacity-4
array size-4, array capacity-4
array size-5, array capacity-8
array size-6, array capacity-8
array size-7, array capacity-8
array size-8, array capacity-8
array size-9, array capacity-16
array size-10, array capacity-16
array size-11, array capacity-16
array size-12, array capacity-16
array size-13, array capacity-16
array size-14, array capacity-16
array size-15, array capacity-16
array size-16, array capacity-16
array size-17, array capacity-32
array size-18, array capacity-32
array size-19, array capacity-32
array size-20, array capacity-32
array size-21, array capacity-32
array size-22, array capacity-32
array size-23, array capacity-32
array size-24, array capacity-32
array size-25, array capacity-32
array size-26, array capacity-32
array size-27, array capacity-32
array size-28, array capacity-32
array size-29, array capacity-32

linux下的比较好算出分配次数与容量对应，比较容易计算，容量=(次数-1)2，例如分配3次为(3-1)2容量为4

1: capacity-1
2: capacity-2
3: capacity-4
4: capacity-8
…

windows下计算就麻烦一点，下面列出几个常用的分配次数与容量对应，供参考：

1: capacity-1
2: capacity-2
3: capacity-3
4: capacity-4
5: capacity-6
6: capacity-9
7: capacity-13
8: capacity-19
9: capacity-28
10: capacity-42
11: capacity-63
12: capacity-94
13: capacity-141
14: capacity-211
15: capacity-316
16: capacity-474
17: capacity-711
18: capacity-1066
19: capacity-1599
20: capacity-2398
21: capacity-3597
22: capacity-5395
23: capacity-8092
24: capacity-12138
25: capacity-18207
26: capacity-27310
27: capacity-40965
28: capacity-61447
29: capacity-92170
30: capacity-138255
31: capacity-207382
32: capacity-311073
33: capacity-466609
34: capacity-699913
35: capacity-1049869
36: capacity-1574803

(Owed by: 春夜喜雨 http://blog.csdn/chunyexiyu)

本文标签： 增长率内存stdVector