夜雨聆风
STL 源码解读:手写 MiniVector
告别死记硬背！手写一个 MiniVector 彻底搞懂 STL 容器底层逻辑
1.1. vector
1.1.1. 内存三剑客 (The Three Pointers)
这是 vector 的空间基石。不要寻找 size 变量，寻找以下三个成员：
_M_start
: 内存起始，对应 begin()。_M_finish
: 最后一个元素的后一个位置，对应 end()。_M_end_of_storage
: 整块分配空间的末尾。 - 关键公式
：size = finish – start；capacity = end_of_storage – start。
pointer _M_start;pointer _M_finish;pointer _M_end_of_storage;
1.1.2. 内存管理与对象构造的解耦
这是理解“组件分离”的关键。
std::allocator
: 观察源码如何通过它调用 allocate申请字节流，而非直接new。placement new
: 寻找 _M_construct或类似的包装，看它如何在已分配的内存上精准构造对象。- 析构不释放
：观察 pop_back，它只调用destroy（析构），绝不触发内存回收。
pointer _M_allocate(size_t __n){// 这里调用了 allocate_traits::allocate，最终调到底层的 allocator::allocate// 它只返回一块能容纳 __n 个 T 的裸内存，里面的比特是随机的（未初始化）typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();}
这块内存拿到手后，虽然它是 T* 类型，但它指向的地方 并没有 合法的 T 对象。如果你直接去访问 *ptr ，行为是未定义的。
push_back(const value_type& __x){if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)//确认已经有内存空间{_GLIBCXX_ASAN_ANNOTATE_GROW(1);//它告诉编译器： “别去申请新内存了，就在 _M_finish 指向的这个地址上，调用 T 的拷贝构造函数吧。”_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,__x);++this->_M_impl._M_finish;_GLIBCXX_ASAN_ANNOTATE_GREW(1);}else_M_realloc_append(__x);}
voidpop_back() _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();// 1. 指针倒退，逻辑上减少一个元素--this->_M_impl._M_finish;// 2. 显式调用析构函数_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);// 3. 这里的内存并没有被 free！_M_end_of_storage 没变！// 下次 push_back 可以直接复用这块内存，无需再次 allocate。}
这种机制保证了 vector 在 capacity 范围内的操作完全是用户态的内存读写，没有任何操作系统开销。
1.1.3. 指数级扩容算法 (Reallocation Logic)
寻找 _M_reallocate_dispatch 或 _M_insert_aux。
- 扩容倍数
：确认是 1.5 times 还是 2 times。
_M_check_len(size_type __n, const char* __s) const{if (max_size() - size() < __n)__throw_length_error(__N(__s));//const size_type __len = size() + (std::max)(size(), __n);return (__len < size() || __len > max_size()) ? max_size() : __len;}
– 当 push_back 触发扩容时，插入元素个数 __n 为 1。
– size() 是当前大小。
– 新大小 __len = size() + max(size(), 1) = 2 * size() 。
– 结论 ：GCC 采用的是 2 倍扩容 策略（MSVC 通常是 1.5 倍）。
- 备位空间
：思考为什么必须一次性申请新空间，而不是在原空间后追加。
pointer __new_start(this->_M_allocate(__len)); // 申请全新的内存块// ... 搬运数据 ...this->_M_deallocate(__old_start, ...); // 释放旧的内存块
– 分析 ：源码明确展示了 allocate 一个新地址，最后 deallocate 旧地址。
– 思考（为什么不能原地追加？） ：
– vector 承诺元素在内存中是 物理连续 的。
– 堆内存（Heap）像一个被切得七零八落的蛋糕。你当前占用的内存块后面，可能紧挨着另一个对象（比如一个 string 或者 map 节点）。
– 操作系统无法保证“原空间后面刚好有空地”。为了保证连续性，唯一的办法就是： 去别的地方找一块更大的连续空地，把大家全搬过去，然后退掉现在的房子 。
- 内存拷贝 vs 移动
：观察在搬运旧数据时，源码如何利用 std::move_if_noexcept进行性能优化。
__new_finish = std::__uninitialized_move_if_noexcept_a(__old_start, __position.base(),__new_start, _M_get_Tp_allocator());
– 细节 ：
– 它调用的不是 copy ，而是 move_if_noexcept 。
– 如果 你的对象提供了 noexcept 的移动构造函数（比如 std::string ，或者你自己写的 class MyObj { MyObj(MyObj&&) noexcept; } ），它就会用 Move （只是拷贝指针，开销极小）。
– 否则 （如果移动可能抛出异常），为了保证数据安全（Strong Exception Guarantee），它会退化成 Copy （深拷贝，开销大）。
– 实战启示 ：写 C++ 类时， 一定要把移动构造函数标记为 noexcept ，否则放进 vector 里扩容时会慢得像蜗牛。
1.1.4. 迭代器的本质 (Iterator Implementation)
- 原生指针
：你会发现 vector的迭代器在大多数实现中就是T*的简单封装。
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;这里的 pointer 其实就是 T* 。 __normal_iterator 这个类定义在 stl_iterator.h 中，它的内部成员只有一个
protected:_Iterator _M_current; // 这就是那个 T* 指针
它的所有操作（ *it , it++ , it[n] ）都是直接转发给内部的 _M_current 指针的。 为什么要包一层？ 为了类型安全（Type Safety）。防止你把 vector<int> 的迭代器误传给接受 int* 的函数，或者和 vector<float> 的迭代器混用。但在 Release 模式下，编译器会把它优化得和裸指针一模一样，零开销。
- 失效机理
：通过源码理解为什么一次 push_back可能导致所有迭代器变成野指针（因为_M_start变了）。
// 1. 记录旧地址pointer __old_start = this->_M_impl._M_start;// 2. 申请新地址 (此时 it 还是指向 __old_start 那块区域)pointer __new_start(this->_M_allocate(__len));// 3. 搬运数据到新地址// ...// 4. 【关键点】销毁并释放旧内存_Alloc_traits::destroy(..., __old_start, ...);_M_deallocate(__old_start, ...);// ---> 就在这一瞬间！__old_start 这块内存归还给操作系统了。// ---> 你的 it 依然指向这块“已经被回收”的内存。它变成了“野指针” (Dangling Pointer)。// 5. 更新 vector 内部指针this->_M_impl._M_start = __new_start;
结论 ：
当 vector 扩容时，它偷偷地“搬了家”。
– vector 自己知道新家在哪（步骤 5 更新了 _M_start ）。
– 但是你手里的 it 迭代器并不知道！它还傻傻地指着旧房子的废墟。
– 当你再次解引用 *it 时，就等于在访问一块已经释放的内存，导致 Undefined Behavior (通常是程序崩溃或数据乱码)。
注意：push_back()之后可能不会扩容|也会扩容
只要 size() < capacity() ，也就是说 _M_finish 还没撞到 _M_end_of_storage ， push_back 绝对不会 申请新内存地址。它只是简单地在已有的空闲内存上构造对象，然后把指针往后挪一位。
只有当 size() == capacity() ，也就是 _M_finish 撞到了墙， push_back 才会被迫进入慢速路径（扩容）。
1.1.5. 插入与删除的“大迁徙”
std::copy_backward
：在 insert时，观察源码如何将插入点后的元素向后平移。
假设当前 vector 状态是 [A, B, C, D, _]，finish 指向 _。你想在 B 的位置插入 X。
- 第一步：处理最末尾元素（D）
源码会先执行： construct(finish, *(finish - 1))。 这一步把D拷贝构造到了finish的位置。 此时布局：[A, B, C, D, D]，finish指针随后向后挪一位。 - 第二步：批量后移（你问的那行代码）
由于 D已经安全地复制到了新位置，现在的finish-2（原先的C）就可以挪到finish-1（原先D的位置）而不必担心数据丢失。 代码逻辑： 将[position, finish-2]搬到[position+1, finish-1]。 搬完后布局：[A, B, B, C, D]。 - 第三步：填入新值（X）
在 position（原本B的位置）写入新值X。 最终布局：[A, X, B, C, D]。
// 将 [position, finish-2] 的元素搬到 [position+1, finish-1]_GLIBCXX_MOVE_BACKWARD3(__position.base(),this->_M_impl._M_finish - 2,this->_M_impl._M_finish - 1);
– 为什么要 backward（从后往前搬）？
– 这就好比在排队的人群中间插一个人。如果从前往后搬（先把第 i 个人移到 i+1 ），那原来的第 i+1 个人就被覆盖掉了！
– 必须先让最后一个人往后退一步，倒数第二个退一步……直到腾出位置。
– _GLIBCXX_MOVE_BACKWARD3 ：这其实就是 std::move_backward 的宏（C++11），它会尽可能使用移动语义而非拷贝。
std::copy
：在 erase时，观察元素如何前移覆盖掉被删元素。
场景 ：删除中间的一个元素。 动作 ：必须把被删元素后面的所有元素 向前挪 ，覆盖掉那个空洞。
if (__position + 1 != end())_GLIBCXX_MOVE3(__position + 1, end(), __position);
– 逻辑 ：
– _GLIBCXX_MOVE3 等价于 std::move （C++11）或 std::copy （C++98）。
– 它将 [position+1, end) 这个区间的数据，搬运到以 position 为起点的目标区间。
– 方向 ： 从前往后 。因为目标地址比源地址小（更靠前），所以从前往后搬是安全的。
– 收尾 ：搬完之后， vector 的逻辑大小减小了，但原来的末尾位置还残留着一个有效对象（虽然它现在是多余的）。所以紧接着会调用 destroy 析构掉最后那个元素（第 187 行）。
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);性能彩蛋：memmove
虽然源码里写的是 move 或 copy ，但 GCC 的底层库（ bits/stl_algobase.h ）藏了一个巨大的优化：
如果元素类型是 POD (Trivial Type) （比如 int , float , struct Point { int x,y; } ）：
– 编译器会发现这些对象的拷贝/移动不需要调用构造函数。
– std::copy 和 std::move 会直接退化为 memmove 。
– 这意味着成千上万个元素的移动，可能只需要几条 CPU 向量指令就能完成，速度极快。
1.1.6. 异常安全性 (Exception Safety)
- Commit-or-Rollback
：重点看扩容逻辑。源码通常采用“先构造新空间，再销毁旧空间”的顺序。如果在构造新空间时抛出异常，原有的 vector依然保持原样，这就是强异常安全保证。
pointer __old_start = this->_M_impl._M_start; // 记住老家在哪pointer __new_start(this->_M_allocate(__len)); // 1. 申请新地盘
此时，如果 allocate 抛出 std::bad_alloc ，函数直接退出。因为没动 this->_M_impl 的任何指针，原来的 vector 完好无损。
GCC 在这里定义了一个名为 _Guard_alloc 的 RAII 类（第 471 行）。
// 2. 设立“撤销守卫”_Guard_alloc __guard(__new_start, __len, *this);
这个 __guard 的作用是： 如果在接下来的一系列构造/移动操作中抛出了异常，它的析构函数会自动释放 __new_start 这块新内存。 此时，老 vector 依然毫发无损。这就是 “Rollback” 。
// 3. 构造新元素_Alloc_traits::construct(..., __new_start + __elems_before, ...);// 4. 搬运旧元素__new_finish = std::__uninitialized_move_if_noexcept_a(...);
这里再次体现了 move_if_noexcept 的重要性。如果移动构造函数可能抛异常，为了保证强异常安全，它会退化为拷贝。因为如果在移动了一半时抛异常，原来的 vector 就已经被“掏空”了一半，无法回滚了。
只有当所有新元素都构造好、所有旧元素都搬运好， 没有任何异常发生 时，才会执行最后的“提交”操作
// 5. 交换守卫的责任：让它去释放“旧”内存__guard._M_storage = __old_start;__guard._M_len = this->_M_impl._M_end_of_storage - __old_start;// 6. 更新 vector 的指针指向“新”家this->_M_impl._M_start = __new_start;this->_M_impl._M_finish = __new_finish;this->_M_impl._M_end_of_storage = __new_start + __len;
这就是 “Commit” 点。
– 指针赋值是不会抛异常的（No-throw guarantee）。
– 一旦执行了第 6 步，vector 就正式切换到了新状态。
– 随后函数结束， __guard 析构，释放的是 旧内存 （因为它在第 5 步被切换了目标）。
总结
vector 的扩容就像做“心脏移植手术”：
1. 准备 ：在旁边准备一颗新的心脏（申请新内存）。
2. 连接 ：把血管接过去（构造/搬运对象）。
3. 回滚 ：如果连接过程中出问题，直接扔掉新心脏，病人（旧 vector）还是原样。
4. 切换 ：确认一切正常，瞬间切断旧连接，启用新心脏。
1.1.7. 空间回收的“潜规则”
clear()的真相
：观察 clear之后，capacity是否改变（源码告诉你：它只管析构，不管还钱）。
voidclear() _GLIBCXX_NOEXCEPT{_M_erase_at_end(this->_M_impl._M_start);}
void _M_erase_at_end(pointer __pos){// 1. 析构从 __pos 到末尾的所有对象std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());// 2. 仅仅移动了 finish 指针，size() 归零this->_M_impl._M_finish = __pos;// 3. 【关键】_M_end_of_storage 完全没动！}
结论 ： clear() 仅仅是把房间里的家具拆了（调用析构函数），然后把门牌号（ size ）改为 0。但那块巨大的地皮（内存）依然被 vector 紧紧攥在手里。 目的 ：为了让后续的 push_back 能直接复用这块内存，避免再次 allocate 。
- Swap 技巧
：搜索 shrink_to_fit的实现，看它是如何通过临时变量交换来实现真正释放多余内存的。
如果你真的想把内存还给操作系统，必须用“以旧换新”的策略。
在 C++11 之前，我们通常手写 vector<T>(v).swap(v) 。在 C++11 之后，标准提供了 shrink_to_fit() 。我们看看它的底层实现 _S_do_it 。
// 1. 如果 capacity 已经等于 size，就不折腾了if (__v.capacity() == __v.size()) return false;// 2. 创建一个临时的 vector，其大小刚好等于原 vector 的 size// 注意：这里只会申请 size() 大小的内存，没有多余的 capacityvector<_Tp> __tmp(__v.begin(), __v.end());// 3. 【关键】交换！// __tmp 拿走了原 vector 的大内存（准备析构）// __v 拿走了 __tmp 的小内存（紧凑）__v.swap(__tmp);// 4. 函数结束，__tmp 析构，释放那块大的旧内存return true;
结论 ： vector 自己没有“缩小内存块”的能力（ realloc 也不支持原地缩小）。唯一的办法就是 去申请一块刚刚好的新地皮，搬过去，然后把旧地皮卖掉 。
shrink_to_fit 的本质是一次 “以短时间的 CPU 搬运和微小的临时内存峰值，换取长期的、显著的内存节省” 。
它确实会“占用一块新内存”，但这块新内存通常 远小于 马上要释放的那块旧内存。【有些 vector 在构建完成后，就再也不会修改大小了（Read-only）。
比如加载一个 3D 模型的顶点数据。构建过程中可能触发了多次 2 倍扩容，最终导致 capacity 远大于实际 size （比如 size=10MB，capacity=16MB，浪费了 6MB）。
– 调用 shrink_to_fit 可以切掉这 6MB 的“泡沫”。
– 不仅节省内存，还能提高 CPU 缓存命中率 （因为数据更紧凑，没有多余的空洞）。】
#include<iostream>#include<algorithm>#include<assert.h>template <typename T>class MiniVector {public://迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _M_start_;}iterator end(){return _M_finish_;}const_iterator begin()const{return _M_start_;}const_iterator end()const{return _M_finish_;}//构造MiniVector() : _M_start_(nullptr), _M_finish_(nullptr), _M_end_of_storage_(nullptr) {}MiniVector(size_t n, const T& val = T()) : MiniVector() {reverse(n);while(n--) {push_back(val);}}//迭代器区间构造template <class InputIterator>MiniVector(InputIterator first, InputIterator last) : MiniVector() {while(first != last) {push_back(*first);++first;}}MiniVector(const MiniVector<T>& v) : MiniVector() {reverse(v.capacity);for (const auto& e : v) {push_back(e);}}~MiniVector() {_M_destroy_all();::operatordelete(_M_start_);_M_start_ = _M_finish_ = _M_end_of_storage_ = nullptr;}//运算符重载MiniVector<T> operator=(MiniVector<T> v) {this->Swap(v);return *this;}T& operator[] (size_t n) {assert(n < size());return _M_start_[n];}//增删改查voidreverse(size_t n){if (n > capacity()) {size_t old_size = size();T* temp = static_cast<T*>(::operator new(n*sizeof(T)));if (_M_start_) {for (size_t i = 0; i < old_size; i++) {new (temp + i) T(std::move(_M_start_[i]));_M_start_->~T();}::operatordelete(_M_start_);}_M_start_ = temp;_M_finish_ = _M_start_ + old_size;_M_end_of_storage_ = _M_start_ + n;}}voidpush_back(const T& val){if (_M_finish_ == _M_end_of_storage_) {reverse(capacity() == 0 ? 1 : capacity() * 2);}new (_M_finish_) T(val);++_M_finish_;}voidpop_back(){assert(!empty());--_M_finish_;_M_finish_->~T();}iterator insert(iterator pos, const T& val){assert(pos >= _M_start_ && pos <= _M_finish_);if (_M_finish_ == _M_end_of_storage_) {size_t len = pos - _M_start_;reverse(capacity() == 0 ? 1 : capacity() * 2);pos = _M_start_ + len;}if (pos != _M_finish_) {new(_M_finish_) T(std::move(*(_M_finish_ - 1)));std::copy_backward(pos, _M_finish_ - 1, _M_finish_);*pos = val;} else {new (pos) T(val);}++_M_finish_;return pos;}iterator erase(iterator pos){assert(pos >= _M_start_ && pos < _M_finish_);iterator next = pos + 1;if (next != _M_finish_) {std::copy(next, _M_finish_, pos);}--_M_finish_;_M_finish_->~T();return pos;}size_tsize()const{return _M_finish_ - _M_start_;}size_tcapacity()const{return _M_end_of_storage_ - _M_start_;}boolempty()const{return _M_start_ == _M_finish_;}voidSwap(MiniVector<T>& v){std::swap(_M_start_, v._M_start_);std::swap(_M_finish_, v._M_finish_);std::swap(_M_end_of_storage_, v._M_end_of_storage_);}private:T* _M_start_;T* _M_finish_;T* _M_end_of_storage_;void _M_destroy_all() {if (_M_start_) {for (T* p = _M_start_; p < _M_finish_; p++) {p->~T();}}}};intmain(){MiniVector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);std::cout << "Size: " << v.size() << " Capacity: " << v.capacity() << std::endl;v.insert(v.begin() + 1, 100); // [1, 100, 2, 3]std::cout << "After Insert: ";for (auto e : v) std::cout << e << " ";std::cout << std::endl;v.erase(v.begin() + 2); // [1, 100, 3]std::cout << "After Erase: ";for (size_t i = 0; i < v.size(); ++i) std::cout << v[i] << " ";std::cout << std::endl;return 0;}
