微操征霸
351.42M · 2026-02-04
STL 中最常用到的容器可能是Vector。今天从源码角度梳理下Vector。建议带着数组和Vector区别来阅读这篇文章。
clang stl 源码: github.com/llvm/llvm-p…
Vector STL 头文件里提供了2种Vector 模板类：
template <class _Tp, class _Allocator /* = allocator<_Tp> */>
class _LIBCPP_TEMPLATE_VIS vector {}
template <class _Allocator>
class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> {}
刚看的第一眼就被晕倒了,明明vector 是2个参数的模板类，但是，创建的时候，明明可以只给一个类型就可以，比如：
vector<int> coll(10)
源码里仿佛不是这个样子呢？
vector 头文件 有个include：
#include <iosfwd> // for forward declaration of vector
没有一句注释是无用的,且看iosfwd 前置声明的头文件：
// Include other forward declarations here
template <class _Tp, class _Alloc = allocator<_Tp> >
class _LIBCPP_TEMPLATE_VIS vector;
默认的分配函数 allocator<_tp>,在Vector 头文件见到的是模板类的定义实现。
这里还涉及到了模板的偏特化，全特化的概念。第2个模板类就是偏特化。
全特化,完全指定所有模板参数，例如：
template <>
class vector<bool, allocator<bool>> { /*...*/ };
偏特化,仅对部分模板参数进行特化，保留其他参数的泛型性。例如 vector<bool>的特化：
template <class _Allocator>
class vector<bool, _Allocator> { /*...*/ }; // 固定第一个参数为 bool，第二个参数仍可变
template <__enable_if_t<__is_allocator_v<_Allocator>, int> = 0>
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
vector(size_type __n, const value_type& __x, const allocator_type& __a)
: __alloc_(__a) {
printf("[Vector debug] %s called,__n:%dn", __func__, __n);//用来 debug
auto __guard = std::__make_exception_guard(__destroy_vector(*this));
if (__n > 0) {
__vallocate(__n);
__construct_at_end(__n, __x);
}
__guard.__complete();
}
针对下面2句展开
__vallocate(__n);
__construct_at_end(__n, __x);
先上test 程序：
template <typename _Tp,typename = std::enable_if_t<!std::is_pointer_v<_Tp>,bool>>
void functor(_Tp a) {
std::cout <<"General case: "<< std::endl;
}
template <typename _Tp, std::enable_if_t<std::is_pointer_v<_Tp>, int> = 0>
void functor(_Tp a) {
std::cout <<"Pointer case: "<< std::endl;
}
int main() {
float a = 1.0;
float *ptr =&a;
functor(1);
functor(false);
functor(ptr);
std::cout << "testVector:" << std::endl;
auto alloc = std::allocator<int>();
std::vector<int> vec(10, 8, alloc);
std::cout << "Vector size:<<sizeof(vec) :"<< sizeof(vec) << std::endl;
for (auto i : vec) {
std::cout << i << " ";
}
std::cout << std::endl;
}
结果：
General case:
General case:
Pointer case:
testVector:
[Vector debug] vector called,__n:10
Vector size:<<sizeof(vec) :24
8 8 8 8 8 8 8 8 8 8
(base) PS E:workspacellvm-projectbuild_libcxx_arm64testSpacetest1>
functor 仅仅是用来验证一下 SFINAE(Substitution Failure Is Not An Error) 替换失败非错误，这个机制。
__vallocate(__n);
private:
pointer __begin_ = nullptr;
pointer __end_ = nullptr;
_LIBCPP_COMPRESSED_PAIR(pointer, __cap_ = nullptr, allocator_type, __alloc_);
// Allocate space for __n objects
// throws length_error if __n > max_size()
// throws (probably bad_alloc) if memory run out
// Precondition: __begin_ == __end_ == __cap_ == nullptr
// Precondition: __n > 0
// Postcondition: capacity() >= __n
// Postcondition: size() == 0
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
if (__n > max_size())
this->__throw_length_error();
auto __allocation = std::__allocate_at_least(this->__alloc_, __n);
__begin_ = __allocation.ptr;
__end_ = __allocation.ptr;
__cap_ = __begin_ + __allocation.count;
__annotate_new(0);
}
这里基于堆上开辟一段buffer, __allocation.count 等于 参数__n, buffer的结束地址记在了__cap_.
解释这里的宏：
_LIBCPP_COMPRESSED_PAIR(pointer, __cap_ = nullptr, allocator_type, __alloc_);
展开约等于：
//vector<int> 背景下
struct {
_LIBCPP_NO_UNIQUE_ADDRESS pointer __cap_ = nullptr;
_LIBCPP_NO_UNIQUE_ADDRESS ::std::__compressed_pair_padding<pointer> __padding1_582_;
_LIBCPP_NO_UNIQUE_ADDRESS std::allocator<int> __alloc_;
_LIBCPP_NO_UNIQUE_ADDRESS ::std::__compressed_pair_padding<std::allocator<int>> __padding2_582_;
};
利用宏在vector类里声明了匿名struct结构，外部可以直接引用匿名struct的成员。
vector::__vallocate()
↓
std::__allocate_at_least()
↓
allocator::allocate()
↓
__libcpp_allocate()
↓
__libcpp_operator_new()
↓
::operator new() [标准库全局 operator new]
总结vector 总览：
vector<int> 内存布局示意图
+------------------+ offset 0
| __begin_ | 8 bytes (int*) ────┐
+------------------+ offset 8 │ 指向已分配内存的起始
| __end_ | 8 bytes (int*) ────┤ 指向当前有效元素的末尾
+------------------+ offset 16 │
| __cap_ | 8 bytes (int*) ────┘ 指向已分配内存的末尾
+------------------+ offset 24
| __alloc_ | 0 bytes (空基类优化，std::allocator<int> 通常是空类)
+------------------+
空基类优化：_LIBCPP_NO_UNIQUE_ADDRESS 属性允许编译器让空类的数据成员不占用额外的存储空间。
堆上内存:
__begin_ __end_ __end_cap()
↓ ↓ ↓
+---------+---------+---------+---------+---------+---------+
| elem[0] | elem[1] | elem[2] | ... | | |
+---------+---------+---------+---------+---------+---------+
←──────────── size() ────────→ ←── capacitysize ──→
←────────────────────── capacity() ───────────────→
__construct_at_end(__n, __x);
// Default constructs __n objects starting at __end_
// throws if construction throws
// Precondition: __n > 0
// Precondition: size() + __n <= capacity()
// Postcondition: size() == size() + __n
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) {
_ConstructTransaction __tx(*this, __n);
const_pointer __new_end = __tx.__new_end_;
for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
__alloc_traits::construct(this->__alloc_, std::__to_address(__pos));
}
}
std::allocator_traits::construct 的主要作用是在指定的未初始化内存地址上构造对象。
它是对 new (placement new) 的一种封装，为容器（如 std::vector、std::list）提供了一种统一的方式来管理内存分配与对象构造的分离。
内存分配之后, 再去初始化buffer。上一步分配的阶段(__vallocate(__n);)， __end_ 等于__begin_ ,所以 vector 这里是尾插初始化buffer。
vector 构造函数有多种，目的只有一个，先分配一段内存，再去初始化buffer，2步操作。构造函数搞明白了，再看其他接口就顺利了很多。比如push_back 和 emplace_back
void push_back(const_reference __x) { emplace_back(__x); }
void push_back(value_type&& __x) { emplace_back(std::move(__x)); }
源码里push_back 调用的emplace_back. 所以，单从这一点上就可以知道emplace_back调用成本更低。
这是第二次看vector 源码，从内存布局的角度去理解vector ，有种豁然开朗的感觉。vector，它不是直接存储数据，而是管理数据的存储。
重要的事情写在最后。比起理解vector 背后的原理，更重要的是如何阅读STL。
这次才发现，重点要去关注STL里的注释，注释里没有一句废话。以vector 为例子，
/*
vector synopsis
namespace std
{
template <class T, class Allocator = allocator<T> >
class vector
{
public:
typedef T value_type;
//...
}
*/
第一次看忽略了这个注释里的概要，看的比较痛苦。这次结合注释看，因为注释里没有眼花缭乱的宏，顺利很多。
若这篇博文，能给道友带来点滴的启示或共鸣，那它便有了价值。
