ARTICLE · 1290770
libcxx stl源码分析-splitbuffer
libcxx stl源码分析-splitbuffer本章我们来讲解vector以及deque底层核心的数据结构：SplitBuffer。 在标准库中，有如下注释来解释split_buffer
下面我们来详细看看SplitBuffer类的实现。 首先我们解释下上述_split_buffer的模版类声明为啥能正常工作。 在上述实现中，模版参数中有一个类模版_Layout, 并且将这个_Layout作为了_split_buffer的基类。这里标准库使用了一种技巧叫 CRTP(奇异递归模板模式) 详细可以参考；https://en.cppreference.com/cpp/language/crtp 下面我们讲解下CRTP为啥能工作。 CRTP 的"能工作"不依赖于派生类已经完整，只依赖于两件事——(1) 基类模板实参允许不完整类型，(2) 基类对_Self的使用被延迟到派生类完整之后。下面逐条拆开 在libcxx中，split_buffer的layout有两种选择：__split_buffer_pointer_layout 和__split_buffer_size_layout。当前vector中默认采用的是__split_buffer_pointer_layout。关于vector中使用可参考libcxx stl源码分析-容器vector分析（1） libcxx stl源码分析-容器vector分析（2） libcxx stl源码分析-vector的resize函数 下面我们来看看__split_buffer_pointer_layout的实现。 为了阅读方便，我把相应的宏都给去掉。 这个类的默认内存布局分两种 本篇文章我们简单的介绍了下_split_buffer的概念，以及它的模版声明，并借此讲解了CRTP的工作原理，以及这里为啥能工作正确；此外我们也讲解了split_buffer的基类__split_buffer_pointer_layout的实现，包括它的内存布局以及关键的函数。 下一章，我们会基于vector的reserve函数的使用场景，来进一步讲解_split_buffer的构造，关键函数实现以及__split_buffer_pointer_layout的relocate接口。
SplitBuffer是什么？
// `__split_buffer` is a contiguous array data structure. It may hold spare capacity at both ends of// the sequence. This allows for a `__split_buffer` to grow from both the front and the back without// relocating its contents until it runs out of room. This characteristic sets it apart from// `std::vector`, which only holds spare capacity at its end. As such, `__split_buffer` is useful// for implementing both `std::vector` and `std::deque`.//// The sequence is stored as a contiguous chunk of memory delimited by the following "pointers" (`o` denotes// uninitialized memory and `x` denotes a valid object)://// |oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo|// ^ ^ ^ ^// __front_cap_ __begin_ __end_ __back_cap_//// The range [__front_cap_, __begin_) contains uninitialized memory. It is referred to as the "front spare capacity".// The range [__begin_, __end_) contains valid objects. It is referred to as the "valid range".// The range [__end_, __back_cap_) contains uninitialized memory. It is referred to as the "back spare capacity".//// The layout of `__split_buffer` is determined by the `_Layout` template template parameter. This// `_Layout` allows the above pointers to be stored as different representations, such as integer// offsets. A layout class template must provide the following interface://
这段注释描述的是 C++ 标准库（libc++）内部的一个底层数据结构__split_buffer。下面用中文逐段解释。
__split_buffer是一个连续数组数据结构，它可以在序列的两端都保留备用容量（spare capacity）。
这样它就能同时从前端和后端增长，而在还有空间时不需要搬移已有元素。
这一点让它区别于std::vector——std::vector只在尾部保留备用容量。
正因如此，__split_buffer既能用来实现std::vector，也能用来实现std::deque.
split_buffer是一块连续内存，默认用四个指针来划分，如下面所示，其中O代表未初始化的部分，X代表已经初始化的部分
|oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo|^ ^ ^ ^__front_cap_ __begin_ __end_ __back_cap_
四段区间分别是
实现分析
template <class _Tp, class _Allocator, template <class, class, class> class _Layout>class __split_buffer : _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator> {using __base_type _LIBCPP_NODEBUG = _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator>;public:using __base_type::__back_spare;using __base_type::__copy_without_alloc;using __base_type::__front_cap;using __base_type::__front_spare;using __base_type::__get_allocator;using __base_type::__raw_capacity;using __base_type::__raw_sentinel;using __base_type::__relocate;using __base_type::__relocate_with_pivot;using __base_type::__reset;using __base_type::__set_capacity;using __base_type::__set_data;using __base_type::__set_sentinel;using __base_type::__set_valid_range;using __base_type::__swap_layouts;using typename __base_type::__alloc_traits;using typename __base_type::allocator_type;using typename __base_type::const_iterator;using typename __base_type::const_pointer;using typename __base_type::const_reference;using typename __base_type::difference_type;using typename __base_type::iterator;using typename __base_type::pointer;using typename __base_type::reference;using typename __base_type::size_type;using typename __base_type::value_type;// A __split_buffer 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// __split_buffer doesn't have 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>,__split_buffer,void>;
这是 C++ 的"不完整类型可以作为模板参数"规则在起作用：
在类定义的基类列表中，类名__split_buffer<_Tp,_Allocator,_Layout>是一个已声明但尚未定义完整的类型（incomplete type）。
模板实参可以是不完整类型（对于类模板实例化来说，标准允许用 incomplete type 作实参，只要在需要完整类型之前它变成完整的）。
_Layout的类定义通常只在成员里用到_Self（比如在成员函数体内、在typedef里、指针成员里），这些位置对_Self的完整性要求可以延迟到"使用点"满足，而那时__split_buffer已经定义完整了。
换句话说，标准允许这种"基类模板参数是派生类"的模式，只要_Layout不要求在它自己的定义中就完整地使用_Self（例如不能让_Layout有_Self类型的数据成员，那会导致不完整类型成员错误；但_Self*、_Self&、typedef、成员函数内部使用都是合法的）。
CRTP 基类里对_Self的使用分两类，合法性截然不同：
类型 A：_Self 只出现在不需要完整类型的位置
typedef/using别名
指针_Self*、引用_Self&
成员函数的声明（参数、返回类型）
成员函数体内的static_cast<_Self*>(this)
模板参数
这些位置不要求_Self完整，所以在派生类定义过程中（甚至基类实例化时）都合法。
类型 B：_Self 出现在需要完整类型的位置
作为数据成员：_Self __x;
sizeof(_Self)、继承自_Self、按值传参/返回_Self
访问_Self的成员（static_cast<_Self*>(this)->member）
这些位置要求_Self完整，只能在派生类定义完成之后的"使用点"（成员函数体被实例化/调用时）才合法。
CRTP 的合法性 = A 类用法都在基类定义里，B 类用法都被推迟到使用点。这就是"延迟完整性"。
标准库Layout的实现
template <class _Tp, class _Allocator, template <class, class, class> class _Layout>class __split_buffer;template <class _SplitBuffer, class _Tp, class _Allocator>class __split_buffer_pointer_layout {protected:using value_type = _Tp;using allocator_type = _Allocator;using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;using reference = value_type&;using const_reference = const value_type&;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;using iterator = pointer;using const_iterator = const_pointer;using __sentinel_type = pointer;public:// Can't be defaulted due to _LIBCPP_COMPRESSED_PAIR not being an aggregate in C++03 and C++11.__split_buffer_pointer_layout() : __back_cap_(nullptr) {}explicit __split_buffer_pointer_layout(const allocator_type& __alloc): __back_cap_(nullptr), __alloc_(__alloc) {}pointer __front_cap() _NOEXCEPT { return __front_cap_; }const_pointer __front_cap() const _NOEXCEPT {return __front_cap_;}pointer begin() _NOEXCEPT { return __begin_; }const_pointer begin()const _NOEXCEPT { return __begin_; }pointer end() _NOEXCEPT { return __end_; }pointer end()const _NOEXCEPT { return __end_; }size_type size()const _NOEXCEPT {return static_cast<size_type>(__end_ - __begin_);}boolempty()const _NOEXCEPT { return __begin_ == __end_; }size_type capacity()const _NOEXCEPT {return static_cast<size_type>(__back_cap_ - __front_cap_);}allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; }allocator_type const& __get_allocator() const _NOEXCEPT {return __alloc_;}// Returns the sentinel object directly. Should be used in conjunction with automatic type deduction,// not explicit types.__sentinel_type __raw_sentinel() const _NOEXCEPT {return __end_;}__sentinel_type __raw_capacity() const _NOEXCEPT {return __back_cap_;}void __set_data(pointer __new_first) _NOEXCEPT {__front_cap_ = __new_first;}void__set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT {__begin_ = __new_begin;__end_ = __new_end;}void__set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT {__begin_ = __new_begin;__end_ = __begin_ + __new_size;}void __set_sentinel(pointer __new_end) _NOEXCEPT {_LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_");__end_ = __new_end;}void __set_sentinel(size_type __new_size) _NOEXCEPT {__end_ = __begin_ + __new_size;}void __set_capacity(size_type __new_capacity) _NOEXCEPT {__back_cap_ = __front_cap_ + __new_capacity;}void __set_capacity(pointer __new_capacity) _NOEXCEPT {__back_cap_ = __new_capacity;}size_type __front_spare() const _NOEXCEPT {return static_cast<size_type>(__begin_ - __front_cap_);}size_type __back_spare() const _NOEXCEPT {return static_cast<size_type>(__back_cap_ - __end_);}reference back() _NOEXCEPT { return *(__end_ - 1); }const_reference back()const _NOEXCEPT { return *(__end_ - 1); }void__swap_without_allocator(__split_buffer_pointer_layout& __other) _NOEXCEPT {std::swap(__front_cap_, __other.__front_cap_);std::swap(__begin_, __other.__begin_);std::swap(__back_cap_, __other.__back_cap_);std::swap(__end_, __other.__end_);}voidswap(__split_buffer_pointer_layout& __other) _NOEXCEPT {std::swap(__front_cap_, __other.__front_cap_);std::swap(__begin_, __other.__begin_);std::swap(__back_cap_, __other.__back_cap_);std::swap(__end_, __other.__end_);std::__swap_allocator(__alloc_, __other.__alloc_);}void __reset() _NOEXCEPT {__front_cap_ = nullptr;__begin_ = nullptr;__end_ = nullptr;__back_cap_ = nullptr;}void__copy_without_alloc(__split_buffer_pointer_layout const& __other)_NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) {__front_cap_ = __other.__front_cap_;__begin_ = __other.__begin_;__end_ = __other.__end_;__back_cap_ = __other.__back_cap_;}void__swap_layouts(pointer& __begin, pointer& __end, pointer& __back_capacity) {using std::swap;swap(__begin_, __begin);swap(__end_, __end);swap(__back_cap_, __back_capacity);}/// 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_;}/// Relocates the objects in the range `[__first, __pivot)` to the front of the buffer, the/// objects in `[__pivot, __last)` into the back of the buffer, then swaps `__first`, `__last`,/// and `__capacity` with `__begin_`, `__end_`, and `__back_cap_`, respectively.////// Preconditions:/// * `__front_spare() == __pivot - __first`/// * `__back_spare() == __last - __pivot`/// Exceptions: This function has a strong exception guarantee if `__first == __pivot` or/// `__last == __pivot`.pointer__relocate_with_pivot(pointer __pivot, pointer& __first, pointer& __last, pointer& __capacity) {pointer __result = __begin_;// Relocate [__p, __last) first to avoid having a hole in [__first, __last)// in case something in [__first, __p) throws.std::__uninitialized_allocator_relocate(__alloc_, std::__to_address(__pivot), std::__to_address(__last), std::__to_address(__end_));auto __relocated_so_far = __last - __pivot;__end_ += __relocated_so_far;__last = __pivot; // The objects in [__p, __last) have been destroyed by relocating them.auto __new_begin = __begin_ - (__pivot - __first);std::__uninitialized_allocator_relocate(__alloc_, std::__to_address(__first), std::__to_address(__pivot), std::__to_address(__new_begin));__begin_ = __new_begin;__last = __first; // All the objects have been destroyed by relocating them.__swap_layouts(__first, __last, __capacity);__front_cap_ = __begin_;return __result;}private:pointer __front_cap_ = nullptr;pointer __begin_ = nullptr;pointer __end_ = nullptr;_LIBCPP_COMPRESSED_PAIR(pointer, __back_cap_, allocator_type, __alloc_);template <class, class, class>friend class __split_buffer_pointer_layout;};
它是__split_buffer的基类（布局层），把"四个指针 + 分配器"的存储与访问封装起来。
_SplitBuffer是 CRTP 参数，即使用该布局的__split_buffer自身类型。虽然这个文件里没直接用_SplitBuffer做static_cast，但保留它是为了布局可替换：其他布局（如偏移量布局）可以用_SplitBuffer做特化或访问派生信息。
它不管理对象生命周期（不构造/析构元素），只负责"指针的存储、读写、以及搬迁（relocate）的底层搬运"。上层的__split_buffer负责 push/pop/destroy。
四个指针 + 一个分配器。注意最后一个用了_LIBCPP_COMPRESSED_PAIR：
这是 libc++ 的EBO（空基类优化）友好的压缩对。当allocator_type是空类型（无状态分配器，如std::allocator）时，__back_cap_和__alloc_会被压进同一块存储（分配器作为空基类，不占额外字节）。
当分配器非空（有状态）时，两者各占存储，等价于普通两个成员。
这就是注释 "Can't be defaulted due to_LIBCPP_COMPRESSED_PAIRnot being an aggregate in C++03 and C++11" 的含义：构造函数必须手写，不能= default，因为压缩对在旧标准下不是聚合体，无法用聚合初始化列表初始化它。
allocator_type 是空类型（如 std::allocator<T>，EBO 生效）
对象 __split_buffer_pointer_layout 本身（栈/堆上的一个对象）:┌──────────────────────────────────────────────────────────┐│ __front_cap_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __begin_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __end_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __back_cap_ (pointer, 8B) ← 压缩对里 ││ [__alloc_ 作为空基类，0B 额外开销] │└──────────────────────────────────────────────────────────┘总大小 ≈ 4 × sizeof(pointer)（空分配器不额外占空间）
allocator_type 是非空类型（有状态分配器）
┌──────────────────────────────────────────────────────────┐│ __front_cap_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __begin_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __end_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __back_cap_ (pointer, 8B) │├──────────────────────────────────────────────────────────┤│ __alloc_ (allocator_type, sizeof(allocator_type)) │└──────────────────────────────────────────────────────────┘总大小 = 4 × sizeof(pointer) + sizeof(allocator_type)（对齐后）
这四个指针指向的堆缓冲区（逻辑布局）
堆上的连续内存块：┌─────────────────────────────────────────────────────────────────────────────┐│ oooooooooooo │ xxxxxxxxxxxxxxxxxxxxxxxxxxx │ oooooooooooooooooo │└─────────────────────────────────────────────────────────────────────────────┘^ ^ ^ ^__front_cap_ __begin_ __end_ __back_cap_├─ front spare ─┤├──── valid range ────┤├──── back spare ──────┤未初始化内存 已构造对象 未初始化内存__front_spare() size() __back_spare()├──────────────── capacity() = __back_cap_ - __front_cap_ ────────────────────┤
__front_cap_：整块分配的起点（也是前端 spare 的起点）。
__begin_：第一个有效对象。
__end_：最后一个有效对象之后（__raw_sentinel()返回它）。
__back_cap_：整块分配的终点（后端 spare 的终点，__raw_capacity()返回它）。
注意：__back_cap_是"容量终点指针"，不是"最后一个元素的下一个"——它等于__front_cap_ + capacity()。
__relocate 之后布局如何变化
搬迁前:[front spare = size][valid: __first .. __last][back spare]^ ^ ^ ^__front_cap_ __begin_ __end_ __back_cap_把 [__first,__last) 搬到前端空余（恰 size 大）:[new valid: __begin_-size .. __begin_][原来的 valid 被销毁][back spare]^ ^ ^ ^__front_cap_(更新为 __begin_') __begin_' __end_' __back_cap_'
搬完后 __front_cap_ = __begin_（前端 spare 归零），外部变量 __first/__last/__capacity 通过 __swap_layouts 接走旧布局。
