ARTICLE · 1232085
libcxx stl源码分析-容器vector分析(2)
libcxx stl源码分析-容器vector分析(2)我们继续来分析std::vector的实现，这篇文章我们主要讲解如下内容 我们还是采用情景分析的方式。 当我们有一个如下实现时，std::vector是如何构造和初始化的呢？ 通过https://cppinsights.io/ 可知 会被转化成如下形式 所以上述语句最终会调用std::vector的如下构造函数 这里我们补充下vector的模版声明的前半部实现 关于vector_layout相关的实现本篇文章不讲解，这里我们提一下__trivially_relocatable（https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p1144r6.html） "重定位"（relocation）= 把对象从一块内存搬到另一块内存，然后销毁原对象。对很多类型来说，这等价于memcpy+ 不调用原析构（因为析构无副作用）。 如果类型是 trivially relocatable，vector在扩容时可以用memcpy批量搬移元素，而不是逐个移动构造 + 析构，性能大幅提升（这是 P1144 等提案的内容，libc++ 已有内部实现）。 判断规则：一个类如果所有成员都可平凡重定位，且没有自引用（self-reference，即内部指针指向自身内部），那么它整体也可平凡重定位。 vector的成员本质上就是三个指针（begin/end/cap，或类似布局）加上一个 allocator。这些成员都不指向 vector 自身内部，所以没有自引用问题。因此只需检查pointer和allocator_type是否可平凡重定位。 这里用__conditional_t<条件, vector, void>的惯用法：如果满足条件，__trivially_relocatable这个别名就是vector自身（表示"我是可平凡重定位的"）；否则是void（表示"不声明"）。这是 libc++ 内部 trait 的约定写法。 假设我们有如下代码 那么上述两次resize的行为是怎么样的呢？ 下面我们来看下resize的标准库实现，然后来分析上述行为应该是啥样 
首先我们看size()函数，这个size函数最终会调用到如下__size()函数 所以vector的这个size()函数返回的是当前vector中有多少个对象初始化构造成功。在我们的例子中，此时size()返回为1,所以第一个resize(10) 命中了resize函数中的这个if分支 上述__current_size= 1,__new_size= 10. 此外vector的capacity()函数 最终会调用到__vector_layout的__capacity函数，这个函数实现如下 故针对本文的例子，一开始这个__capacity函数返回的值为1,故此时__new_size是大于capacity()返回值的，所以在第一个resize(10)语句中，我们最终会进入如下分支 下面我们来详细讲解上述几个语句的实现和含义。 我们先介绍瞎SplitBuffer的概念，关于其源码部分讲解 我们放到下篇文章中，否则这篇文章会太长。 __split_buffer 是一种连续数组数据结构。它可以在序列的两端都持有预留容量。这使得 __split_buffer 能够从前端和后端同时增长，而无需重新定位其内容，直到空间耗尽。这一特性使其区别于 std::vector——后者只在尾部持有预留容量。因此，__split_buffer 既可用于实现 std::vector，也可用于实现 std::deque。 序列存储为一块连续内存，由以下“指针”界定（o 表示未初始化内存，x 表示有效对象）： 范围 [__front_cap_, __begin_) 包含未初始化内存，称为“前端预留容量”。 范围 [__begin_, __end_) 包含有效对象，称为“有效范围”。 范围 [__end_, __back_cap_) 包含未初始化内存，称为“后端预留容量”。 __split_buffer 的布局由 _Layout 模板模板参数决定。该 _Layout 允许上述指针以不同的表示形式存储，例如整数偏移量。 __split_buffer是一块两端都有预留容量的连续缓冲区，用于高效实现 vector 和 deque 的双端增长；_Layout模板参数把“边界指针的存储表示”抽象出来，允许用整数偏移等紧凑形式替代四个裸指针，而__layout接口则规定了布局类必须提供的访问、修改、交换和重置操作，使__split_buffer的逻辑与底层表示解耦。 这个函数是std::vector扩容决策的核心：给定一个期望的新大小__new_size，推荐一个实际分配的容量。前置条件是__new_size > capacity()，也就是说只在确实需要扩容时才会调用它。 它的函数实现如下 两个条件同时满足才安全：
继续回到resize函数，下面这两行 的结果如下所示（这两行的功能 我们留在下一篇文章讲解） 
resize最后的核心操作是__layout_.__relocate(__v);表达式，这个函数实现如下 这个函数最终会调用splitbuffer的__relocate函数，这个函数的实现为 这段代码是 libc++vector内部实现中的一个关键函数__relocate，用于在扩容/重分配时把旧缓冲区中的元素"重定位"到新缓冲区的指定位置，并交换两块缓冲区的布局信息。 这个函数我们不详细分析，在下一篇splitbuffer中，会回过头来继续分析这个实现，这里我们主要看一下std::__uninitialized_allocator_relocate 这个函数，其实现为 下面我们来详细分析下对应的实现。我们讲解第二个if分支和第三个if分支。 第二个if分支的条件为 库没有启用异常支持（用户以-fno-exceptions编译，libc++ 相应地把_LIBCPP_HAS_EXCEPTIONS定义为 0）。既然根本不会抛异常，也就不需要任何异常 guard。 is_nothrow_move_constructible<__value_type>::valuevalue_type的移动构造承诺不抛异常（noexcept）。既然构造阶段不会失败，就不需要回滚机制。 一般场景下 我们会将C++标准库的异常打开，所以 如果你的类的移动构造函数存在 但是没有声明为noexcept，那么也不会走到这个if分支里来。 如果你的移动构造函数声明为noexcept，那么会走到这个if分支来，默认用移动构造来初始化相应的vector中的成员对象 假设用户的移动构造函数未声明为noexcept，那么此时会进入else分支，会调用如下实现 这里的关键在于 std::move_if_noexcept函数，它的实现为 move_if_noexcept是一个"由返回类型决定行为"的转发函数——当移动构造可能抛异常且类型可拷贝时，它退回成拷贝构造以保证强异常安全；否则正常移动。函数体只需std::move，所有策略都在返回类型的条件选择里。 条件 即：移动构造可能抛异常（不是 nothrow）且类型可拷贝构造。
为什么不成立时用 move：有两种情况会让条件不成立： 移动构造是 nothrow（is_nothrow_move_constructible == true）：移动不会抛，当然优先 move（更快）。 不可拷贝构造（is_copy_constructible == false）：即使移动可能抛，也没有拷贝可退，只能用 move——反正没有更强保证的选项，move 是唯一选择。 为什么成立时用拷贝：移动构造可能抛异常且类型可拷贝 → 为了强异常保证，退回拷贝构造。因为拷贝构造不修改源对象：若拷贝过程中抛异常，源对象__x完好无损，接收方（配合异常 guard 清理已构造部分）就能完全回滚，仿佛什么都没发生。而若用移动构造中途抛异常，源对象可能已被部分移走，无法恢复原状。 这正是上一轮__uninitialized_allocator_relocate的else分支用move_if_noexcept来保证强异常保证的机制：它让"可能抛且可拷贝"的类型退化为拷贝，从而在失败时源对象不受损。
因此通过上述分析，我们需要得出如下结论：如果使用vector，那么类的移动构造函数优先声明为noexcept，若移动构造函数没有声明为noexcept，那么不要声明拷贝构造函数或者禁用拷贝构造函数。 在vector扩容的时候，会优先调用移动构造函数，提升性能；否则会采用拷贝构造函数。 当然最优的方案是，把你的vector变成可重定位的方式，这样扩容的时候，搬对象只需要一次memcpy操作即可。 我们会在下一篇文章中讲解resize(10)之后调用resize(2)的行为，以及进一步讲解splitbuffer的实现。
列表初始化构造函数实现 splitbuffer介绍 resize是如何工作的，有什么潜在的坑
列表初始化构造函数
#include<vector>#include<iostream>class A {public:A(int) {std::cout << "A(int)\n";}};intmain(){std::vector<A> a{5};return 0;}
std::vector<A> a{5};std::vector<A, std::allocator<A> > a = std::vector<A, std::allocator<A> >{std::initializer_list<A>{std::vector<A>::value_type(5)}, std::allocator<A>()};
vector(initializer_list<value_type> __il, const allocator_type& __a): __layout_(__a) {__init_with_size(__il.begin(), __il.size());}
template <class _Tp, class _Allocator /* = allocator<_Tp> */>class _LIBCPP_WARN_UNUSED vector {using __base_type = __vector_layout<_Tp, _Allocator>;using __bound_type = typename __base_type::__bound_type;using _SplitBuffer = typename __base_type::_SplitBuffer;public://// Types//using value_type = _Tp;using allocator_type = _Allocator;using __alloc_traits = allocator_traits<_Allocator>;using reference = _Tp&;using const_reference = const _Tp&;using size_type = typename __alloc_traits::size_type;using difference_type = typename __alloc_traits::difference_type;using pointer = typename __alloc_traits::pointer;using const_pointer = typename __alloc_traits::const_pointer;#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR// Users might provide custom allocators, and prior to C++20 we have no existing way to detect whether the allocator's// pointer type is contiguous (though it has to be by the Standard). Using the wrapper type ensures the iterator is// considered contiguous.using iterator = __bounded_iter<pointer>;using const_iterator = __bounded_iter<const_pointer>;#elseusing iterator = __wrap_iter<pointer>;using const_iterator = __wrap_iter<const_pointer>;#endifusing reverse_iterator = std::reverse_iterator<iterator>;using const_reverse_iterator = std::reverse_iterator<const_iterator>;// A vector contains the following members which may be trivially relocatable:// - pointer: may be trivially relocatable, so it's checked// - allocator_type: may be trivially relocatable, so it's checked// vector doesn't contain any self-references, so it's trivially relocatable if its members are.using __trivially_relocatable _LIBCPP_NODEBUG =__conditional_t<__is_trivially_relocatable_v<pointer> && __is_trivially_relocatable_v<allocator_type>,vector,void>;static_assert(__check_valid_allocator<allocator_type>::value, "");static_assert(is_same<typename allocator_type::value_type, value_type>::value,"Allocator::value_type must be same type as value_type");
一个 vector 包含以下可能可平凡重定位（trivially relocatable）的成员：
pointer：可能是可平凡重定位的，所以检查它
allocator_type：可能是可平凡重定位的，所以检查它
vector 不包含任何自引用，所以如果它的成员可平凡重定位，那么它也可平凡重定位。
继续回到vector的构造函数，列表初始化的构造函数最终会调用
__init_with_size(__il.begin(), __il.size());函数，这个函数实现为
template <class _InputIterator>_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __init_with_size(_InputIterator __first, size_type __n) {auto __guard = std::__make_exception_guard(__destroy_vector(*this));if (__n > 0) {__vallocate(__n);__construct_at_end(std::move(__first), __n);}__guard.__complete();}
上述中__vallocate和__construct_at_end实现在libcxx stl源码分析-容器vector分析（1）中已经分析过此处不再赘述。
resize是如何工作的
class A {public:A(int) {std::cout << "A(int)\n";}A() = default;};intmain(){std::vector<A> a{5};a.resize(10);a.resize(2);return 0;}
template <class_Tp, class_Allocator>void vector<_Tp, _Allocator>::resize(size_type __new_size) {size_type __current_size = size();if (__current_size < __new_size) {if (__new_size <= capacity()) {__construct_at_end(__new_size - __current_size);} else {_SplitBuffer __v(__recommend(__new_size), __current_size, __layout_.__alloc());__v.__construct_at_end(__new_size - __current_size);__layout_.__relocate(__v);}} else if (__current_size > __new_size) {this->__destruct_at_end(this->__layout_.__begin_ptr() + __new_size);}}
下面我们来详细讲解下上述代码实现。以
std::vector<A> a{5};为例来进行分析。上述语句最终的vector的内存布局如下
此时的__begin_是分配的内存的首地址，__capacity_ =__begin_ + 1 =__end_.
template <class _Tp, class _Alloc>typename __vector_layout<_Tp, _Alloc>::size_type__vector_layout<_Tp, _Alloc>::__size() const _NOEXCEPT {return static_cast<size_type>(__end_ - __begin_);}
if (__current_size < __new_size) {if (__new_size <= capacity()) {__construct_at_end(__new_size - __current_size);} else {_SplitBuffer __v(__recommend(__new_size), __current_size, __layout_.__alloc());__v.__construct_at_end(__new_size - __current_size);__layout_.__relocate(__v);}}
template <class _Tp, class _Alloc>typename __vector_layout<_Tp, _Alloc>::size_type__vector_layout<_Tp, _Alloc>::__capacity() const _NOEXCEPT {return static_cast<size_type>(__capacity_ - __begin_);}
_SplitBuffer __v(__recommend(__new_size), __current_size, __layout_.__alloc());__v.__construct_at_end(__new_size - __current_size);__layout_.__relocate(__v);
什么是SplitBuffer
|oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo|^ ^ ^ ^__front_cap_ __begin_ __end_ __back_cap_
__recommend扩容机制
// Precondition: __new_size > capacity()template <class _Tp, class _Allocator>inline typename vector<_Tp, _Allocator>::size_typevector<_Tp, _Allocator>::__recommend(size_type __new_size) const {const size_type __ms = max_size();if (__new_size > __ms)this->__throw_length_error();const size_type __cap = capacity();if (__cap >= __ms / 2)return __ms;return std::max<size_type>(2 * __cap, __new_size);}
首先 我们来看下max_size函数，这个函数实现如下
[[__nodiscard__]] size_type max_size() const _NOEXCEPT {return std::min<size_type>(__alloc_traits::max_size(__layout_.__alloc()), numeric_limits<difference_type>::max());}
这个函数返回vector在当前分配器下理论上能容纳的最大元素个数。核心是两个上限取最小值：分配器允许的上限，和difference_type能表示的上限。
__alloc_traits::max_size(__layout_.__alloc()) 这是分配器层面的上限，即当前分配器一次能管理的最大元素数。
对 std::allocator<T>，通常是 SIZE_MAX / sizeof(T)，因为分配器内部用 size_t 表示字节数，而每个元素占 sizeof(T) 字节。
自定义分配器可以实现自己的 max_size()，比如受限于某个内存池大小。
它回答的是：“分配器最多能给我多少块T大小的内存？”
numeric_limits::max() difference_type是 vector 迭代器差值类型，通常是 ptrdiff_t（64 位平台上为 int64_t，上限 2^63 - 1）。
它回答的是：“两个迭代器相减，结果还能正确表示的最大元素数是多少？”
vector的size()返回size_type（通常size_t，无符号 64 位），但很多内部操作（迭代器减法、std::distance）用有符号的difference_type。如果元素数超过difference_type::max()，两个迭代器相减就会有符号溢出，产生未定义行为。
std::min(分配器上限, difference_type 上限)分配器能分配得出来（否则分配失败）；
迭代器差值能表示得出来（否则内部运算溢出）。
所以取较小者作为max_size()。
注意：每个vector的容量有默认上限值，当vector的capacity大于vector容量上限值的一半时，无论resize(capacity + 1) 这个函数 扩容的大小均为vector的默认上限值
继续回到__recommend函数，在这个函数最后一行有如下实现
return std::max<size_type>(2 * __cap, __new_size);这个就是普通场景下vector的扩容机制。当前vector的容量的2倍 和 resize函数中参数的值的最大值即是扩容的容量。
以resize(10）为例，2 * _cap = 2, __new_size = 10, 所以resize(10) 会导致vector扩容，其容量扩到10,也即__recommend返回10.
_SplitBuffer __v(__recommend(__new_size), __current_size, __layout_.__alloc());__v.__construct_at_end(__new_size - __current_size);
__relocate是如何重定位的
template <class _Tp, class _Alloc>void __vector_layout<_Tp, _Alloc>::__relocate(_SplitBuffer& __buffer) {__annotate_delete();__buffer.__relocate(__begin_, __end_, __capacity_);__annotate_new(__size());}
/// Relocates the objects in the range `[__first, __last)` to the front of the buffer, then swaps/// `__first`, `__last`, and `__capacity` with `__begin_`, `__end_`, and `__back_cap_`,/// respectively.////// Precondition: `__front_spare() == __last - __first`./// Exceptions: This function has a strong exception guarantee.void__relocate(pointer& __first, pointer& __last, pointer& __capacity) {auto __size = __last - __first;auto __new_begin = __begin_ - __size;std::__uninitialized_allocator_relocate(__alloc_, std::__to_address(__first), std::__to_address(__last), std::__to_address(__new_begin));__begin_ = __new_begin;__last = __first;__swap_layouts(__first, __last, __capacity);__front_cap_ = __begin_;}
功能：把[__first, __last)范围内的对象重定位到"缓冲区的前端"（即新缓冲区this的可用空间前端），然后把传入的三个指针__first/__last/__capacity与this的__begin_/__end_/__back_cap_交换。
前置条件：__front_spare() == __last - __first。__front_spare()表示this缓冲区中"前端空余槽位数"（即__begin_ - __front_cap_之类）。这个条件保证：目标位置（新缓冲区前端）恰好能容纳要搬过来的元素数量，不会溢出、也不会浪费。
异常保证：强异常保证（strong exception guarantee）——如果重定位过程中抛异常，this对象的状态保持不变（如同调用未发生）。
// __uninitialized_allocator_relocate relocates the objects in [__first, __last) into __result.// Relocation means that the objects in [__first, __last) are placed into __result as-if by move-construct and destroy,// except that the move constructor and destructor may never be called if they are known to be equivalent to a memcpy.//// Preconditions: __result doesn't contain any objects and [__first, __last) contains objects// Postconditions: __result contains the objects from [__first, __last) and// [__first, __last) doesn't contain any objects//// The strong exception guarantee is provided if any of the following are true:// - is_nothrow_move_constructible<_ValueType>// - is_copy_constructible<_ValueType>// - __is_trivially_relocatable_v<_ValueType>template <class _Alloc, class _ContiguousIterator>void __uninitialized_allocator_relocate(_Alloc& __alloc, _ContiguousIterator __first, _ContiguousIterator __last, _ContiguousIterator __result) {static_assert(__libcpp_is_contiguous_iterator<_ContiguousIterator>::value, "");static_assert(__is_cpp17_move_insertable_v<_Alloc>, "The specified type does not meet the requirements of Cpp17MoveInsertable");using __value_type = typename iterator_traits<_ContiguousIterator>::value_type;if _LIBCPP_CONSTEXPR (__allocator_has_trivial_move_construct_v<_Alloc, __value_type> &&__allocator_has_trivial_destroy_v<_Alloc, __value_type> &&__is_trivially_relocatable_v<__value_type>) {if (!__libcpp_is_constant_evaluated()) {// Casting to void* to suppress clang complaining that this is technically UB.__builtin_memcpy(static_cast<void*>(std::__to_address(__result)),std::__to_address(__first),sizeof(__value_type) * (__last - __first));return;}}using __alloc_traits = allocator_traits<_Alloc>;#ifndef _LIBCPP_CXX03_LANGifconstexpr(!_LIBCPP_HAS_EXCEPTIONS || is_nothrow_move_constructible<__value_type>::value){while (__first != __last) {__alloc_traits::construct(__alloc, std::__to_address(__result), std::move(*__first));__alloc_traits::destroy(__alloc, std::__to_address(__first));++__first;++__result;}} else#endif{auto __destruct_first = __result;auto __guard = std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _ContiguousIterator>(__alloc, __destruct_first, __result));auto __iter = __first;while (__iter != __last) {allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move_if_noexcept(*__iter));++__iter;++__result;}__guard.__complete();std::__allocator_destroy(__alloc, __first, __last);}}
__uninitialized_allocator_relocate 将 [__first, __last) 范围内的对象重定位到 __result。重定位的意思是：[__first, __last) 中的对象被放入 __result，其效果如同（as-if）经过移动构造和销毁， 但例外情况是：如果已知移动构造函数和析构函数等价于一次 memcpy，那么它们可以根本不被调用。
!_LIBCPP_HAS_EXCEPTIONS || is_nothrow_move_constructible<__value_type>::value)如果「库以无异常模式编译」或「__value_type的移动构造保证不抛异常」，就走这个简单循环；否则走下面的带异常 guard 的复杂路径。
allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move_if_noexcept(*__iter));template <class_Tp>using __move_if_noexcept_result_t =__conditional_t<!is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value, const _Tp&, _Tp&&>;template <class_Tp>__move_if_noexcept_result_t<_Tp>move_if_noexcept(_LIBCPP_LIFETIMEBOUND _Tp& __x) _NOEXCEPT {return std::move(__x);}
!is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value
