MSVC STL中vector::shrink_to_fit及扩容与缩容源码解析
我看了一堆相关文章，都把读者当聪明人。提到shrink_to_fit只提一嘴会收缩内存。初学的时候我天真的以为把原来持有的内存后半段不用的释放掉。但是如果经常这么释放的话难道不会造成一堆夹在中间的小内存碎片吗？还是看看源码来得实在。
随便写一个vector，ctrl一下都能导航到标准库的源码（win所以看的是MSVC）。
搜索shrink，发现shrink出现在了两个地方：
1
2
3
4
5
6
7
8
9
10
11
12
13
| _CONSTEXPR20 void shrink_to_fit() {
auto& _My_data = _Mypair._Myval2;
const pointer _Oldlast = _My_data._Mylast;
if (_Oldlast != _My_data._Myend) {
const pointer _Oldfirst = _My_data._Myfirst;
if (_Oldfirst == _Oldlast) {
_Tidy();
} else {
size_type _Newcapacity = static_cast<size_type>(_Oldlast - _Oldfirst);
_Reallocate<_Reallocation_policy::_Exactly>(_Newcapacity);
}
}
}
|
1
2
3
4
5
6
| _CONSTEXPR20 void shrink_to_fit() {
if (this->_Myvec.capacity() != this->_Myvec.size()) {
this->_Orphan_all();
this->_Myvec.shrink_to_fit();
}
}
|
第二个shrink_to_fit很明显是在调用第一个之前去做了一些检查或者通知的操作。
让我们仔细看看第一个实际实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| _CONSTEXPR20 void shrink_to_fit() {
auto& _My_data = _Mypair._Myval2;
const pointer _Oldlast = _My_data._Mylast;
if (_Oldlast != _My_data._Myend) {
const pointer _Oldfirst = _My_data._Myfirst;
if (_Oldfirst == _Oldlast) {
_Tidy();
} else {
size_type _Newcapacity = static_cast<size_type>(_Oldlast - _Oldfirst);
_Reallocate<_Reallocation_policy::_Exactly>(_Newcapacity);
}
}
}
|
这里的实现细节值得注意。通常 vector 的扩容（如 push_back 触发）会采用几何级数增长（例如 1.5 倍），以减少未来的分配次数。但在 shrink_to_fit 中，通过模板参数 _Reallocation_policy::_Exactly 显式覆盖了这一默认行为。这意味着 _Reallocate 内部会执行一次标准的“分配新块 -> 移动/拷贝元素 -> 释放旧块”流程，且新块的大小被严格限制为 size()。注释中提到的 “strong guarantee” 意味着如果在移动构造元素过程中抛出异常，原 vector 的状态保持不变，不会丢失数据。
注意到了这一行：
1
| _Reallocate<_Reallocation_policy::_Exactly>(_Newcapacity);
|
_Reallocation_policy意味着还有别的策略，进去看一眼：
会发现这么一段代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| enum class _Reallocation_policy { _At_least, _Exactly };
template <_Reallocation_policy _Policy>
_CONSTEXPR20 void _Reallocate(size_type& _Newcapacity) {
auto& _Al = _Getal();
auto& _My_data = _Mypair._Myval2;
pointer& _Myfirst = _My_data._Myfirst;
pointer& _Mylast = _My_data._Mylast;
const auto _Size = static_cast<size_type>(_Mylast - _Myfirst);
pointer _Newvec;
if constexpr (_Policy == _Reallocation_policy::_At_least) {
_Newvec = _Allocate_at_least_helper(_Al, _Newcapacity);
} else {
_STL_INTERNAL_STATIC_ASSERT(_Policy == _Reallocation_policy::_Exactly);
_Newvec = _Al.allocate(_Newcapacity);
}
_Simple_reallocation_guard _Guard{_Al, _Newvec, _Newcapacity};
if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
_Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
} else {
_Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
}
_Guard._New_begin = nullptr;
_Change_array(_Newvec, _Size, _Newcapacity);
}
|
看来有两种策略：_At_least 与 _Exactly
1
2
3
4
5
6
7
8
| if constexpr (_Policy == _Reallocation_policy::_At_least) {
_Newvec = _Allocate_at_least_helper(_Al, _Newcapacity);
} else {
_STL_INTERNAL_STATIC_ASSERT(_Policy == _Reallocation_policy::_Exactly);
_Newvec = _Al.allocate(_Newcapacity);
}
|
这时候好奇在至少分配模式的时候，这个_Newcapacity是不是会被修改。
应该是push_back的时候就应该已经预分配好了容量了吧。验证一下：
找push_back:
1
2
3
4
5
6
7
8
| _CONSTEXPR20 void push_back(const _Ty& _Val) {
_Emplace_one_at_back(_Val);
}
_CONSTEXPR20 void push_back(_Ty&& _Val) {
_Emplace_one_at_back(_STD move(_Val));
}
|
这应该是两个实现，一个接收左值引用一个接收右值引用以启用移动构造。
看一下_Emplace_one_at_back的右值引用版本
1
2
3
4
5
6
7
8
9
10
11
12
13
| template <class... _Valty>
_CONSTEXPR20 _Ty& _Emplace_one_at_back(_Valty&&... _Val) {
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
return *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
}
|
看一下_Emplace_reallocate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| template <class... _Valty>
_CONSTEXPR20 pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {
_Alty& _Al = _Getal();
auto& _My_data = _Mypair._Myval2;
pointer& _Myfirst = _My_data._Myfirst;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast == _My_data._Myend);
const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);
const auto _Oldsize = static_cast<size_type>(_Mylast - _Myfirst);
if (_Oldsize == max_size()) {
_Xlength();
}
const size_type _Newsize = _Oldsize + 1;
size_type _Newcapacity = _Calculate_growth(_Newsize);
const pointer _Newvec = _STD _Allocate_at_least_helper(_Al, _Newcapacity);
const pointer _Constructed_last = _Newvec + _Whereoff + 1;
...
_Guard._New_begin = nullptr;
_Change_array(_Newvec, _Newsize, _Newcapacity);
return _Newvec + _Whereoff;
}
|
终于找到了
1
2
3
4
5
| const size_type _Newsize = _Oldsize + 1;
size_type _Newcapacity = _Calculate_growth(_Newsize);
const pointer _Newvec = _STD _Allocate_at_least_helper(_Al, _Newcapacity);
const pointer _Constructed_last = _Newvec + _Whereoff + 1;
|
那么增长逻辑就在：size_type _Newcapacity = _Calculate_growth(_Newsize);里，计算完新Newcapacity直接传给刚刚已经看过的_Allocate_at_least_helper(_Al, _Newcapacity)。
继续打开看看_Calculate_growth(_Newsize)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| _CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max;
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize;
}
return _Geometric;
}
|
着急下班吃饭懒得写注释了，交给AI老师帮忙解析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| _CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max;
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize;
}
return _Geometric;
}
|
注意到
1
2
3
| if (_Geometric < _Newsize) {
return _Newsize;
}
|
扩容也不是无限制的，1.5倍不够就直接按需分配了。