本人志在持续更新计算机系统、计算机网络、C语言的核心知识点的系列合集以易懂、全面的方式讲解底层知识。对于正在准备面试八股的朋友来说本系列涵盖了本人面试中遇到的所有考点以及许多相关拓展知识读完后能帮助你从容面对大部分面试拷打对于想要深入学习计算机知识的朋友来说本系列比较系统地介绍了操作系统和网络等重点内容也举了不少例子大大有助于你从底层的视角去理解计算机系统。先说明本系列恐怕不是计算机小白或是想速通期末的朋友们的目标它需要一定系统和语言基础也并不是面向教材和考试要求去讲解所以更适合那些实操过代码、了解一些计算机系统知识、并且想要深入底层和扎实基础的朋友们去耐心学习。如果你是这样的人欢迎阅读该系列文章并分享自己的理解或提出文章中的模糊、错误的地方不排除有。想要阅读系列中其他内容或想要持续关注本系列更新可移步https://github.com/feiyangyang11/Cpp-Core-CS-Interview-Guide.git。vector 底层原理详解朴素版源码与实现思路下面是简化版的 vector 容器源码主要突出核心成员变量、核心函数逻辑实现思路vector 本身一般是栈上对象且并不是个数组实际数据都放在一个堆数组上它本身只有三个指针类型的成员变量本质上用三个指针管理一块连续动态内存begin指向首元素end指向已构造元素末尾cap指向已分配空间末尾元素内存通过allocator申请管理器allocator_traits统一负责allocate / construct / destroy / deallocate内存分配 / 对象构造 / 对象析构 / 内存回收支持动态扩容、移动和拷贝构造整体核心就是连续内存 三指针边界管理 对象生命周期与内存生命周期分离源码#includememory// std::allocator, allocator_traits#includeutility// std::move_if_noexcept#includecstddef// size_ttemplateclassTclassMyVector{public:usingAllocstd::allocatorT;usingTraitsstd::allocator_traitsAlloc;private:Alloc alloc_;// vector 本质上最核心就是三个指针T*begin_nullptr;// 第一个元素T*end_nullptr;// 最后一个有效元素的下一个位置T*cap_nullptr;// 已分配内存的末尾public:MyVector()default;~MyVector(){// 调用所有已经构造出来的 T 的析构函数clear();// destroy - 调用对象析构// deallocate - 释放原始内存if(begin_){Traits::deallocate(alloc_,begin_,capacity());}}size_tsize()const{// 指针差 已经构造的元素数量returnend_-begin_;}size_tcapacity()const{// [begin_, cap_) 是 vector 拥有的整块内存returncap_-begin_;}boolempty()const{returnbegin_end_;}Toperator[](size_t index){// vector 的 [] 本身不检查越界returnbegin_[index];}constToperator[](size_t index)const{returnbegin_[index];}voidclear(){// 从后往前析构所有元素while(end_!begin_){--end_;Traits::destroy(alloc_,end_);}}voidpush_back(constTvalue){// 左值版本 - 新元素需要拷贝构造if(end_cap_){// 没空间了进行扩容grow();}// 在 end_ 指向的“未构造内存”上构造 TTraits::construct(alloc_,end_,value);end_;}voidpush_back(Tvalue){// 右值版本 - 新元素移动构造if(end_cap_){grow();}Traits::construct(alloc_,end_,std::move(value));end_;}templateclass...ArgsTemplace_back(Args...args){if(end_cap_){grow();}// 直接在 vector 内存中构造对象Traits::construct(alloc_,end_,std::forwardArgs(args)...);T*new_elementend_;end_;return*new_element;}voidreserve(size_t new_capacity){// reserve 只扩 capacity不改变 sizeif(new_capacitycapacity()){return;}reallocate(new_capacity);}voidresize(size_t n){if(nsize()){// 缩小while(size()n){--end_;Traits::destroy(alloc_,end_);}}elseif(ncapacity()){// 容量够直接构造新元素while(size()n){Traits::construct(alloc_,end_);end_;}}else{// 容量不够reallocate(/* new capacity n */);while(size()n){Traits::construct(alloc_,end_);end_;}}}private:voidgrow(){size_t old_capacitycapacity();// 实际 STL 不保证一定 ×2这里只为了容易理解size_t new_capacityold_capacity0?1:old_capacity*2;reallocate(new_capacity);}voidreallocate(size_t new_capacity){T*new_beginTraits::allocate(alloc_,new_capacity);T*new_endnew_begin;try{for(T*pbegin_;p!end_;p){Traits::construct(alloc_,new_end,std::move_if_noexcept(*p));new_end;}}catch(...){/* * 如果迁移过程中失败抛出异常 * 已经成功构造出来的 A、B 必须析构。 */while(new_end!new_begin){--new_end;Traits::destroy(alloc_,new_end);}// 再释放新申请的原始内存Traits::deallocate(alloc_,new_begin,new_capacity);// 继续把异常抛给上层throw;}size_t old_capacitycapacity();for(T*pbegin_;p!end_;p){Traits::destroy(alloc_,p);}// 释放旧内存if(begin_){Traits::deallocate(alloc_,begin_,old_capacity);}//最后把三个核心指针指向新内存。begin_new_begin;end_new_end;cap_new_beginnew_capacity;}};核心成员变量vector 的核心数据对象都保存在堆上在栈对象中通过三个指针进行管理左闭右开T* begin_保存数组第一个有效元素的地址T* end_保存数组最后一个有效元素的下一个位置的地址T* cap_保存已分配的数组内存的末尾位置地址Alloc alloc_内存分配器实例vector 通过它申请数组内存它从 malloc / 自定义memory pool / arena……中申请内存。可以自定义内存分配器并通过 vector 的模板参数传入如std::vectorT, MyAllocatorT v;这样就 vector 就可以从自定义的内存池申请内存。如果使用的是默认的allocator就会走标准的动态内存分配路径new / malloc申请内存核心函数长度、容量vec.size()有效元素的个数由end_ - begin_得到vec.capcity()数组容量表示当前数组能容纳的最多有效元素的个数由cap_ - begin_得到vec.resize(N)在数组末尾填充元素直至有效元素个数至 N如果 N vec.capcity()就扩容数组再填充如果 N vec.size()那么就析构多出的数组元素vec.reserve(N)改变数组容量若 N vec.capcity()就触发扩容若 N vec.capcity()则直接返回内存与元素管理对于数组元素有插入与删除操作对应着内存分配/释放、元素构造/析构插入元素时通常先分配可用内存再在内存上调用元素的构造函数构造出对象删除元素时通常先调用对象的析构函数再回收对象原来占有的这片内存当然不是每次和删除都伴随着内存的分配与回收此处只是为了建立一个清晰的模型来介绍数组的机制Traits::allocate(alloc_,new_capacity)通过alloc_申请内存返回新内存的起址Traits::construct(alloc_,new_end,std::move_if_noexcept(*p))在数组末尾构造出一个新对象。优先尝试调用移动构造函数来构造对象通过std::move_if_noexcept(*p)判断该类的移动构造是否会抛异常如果会抛异常就退化为拷贝构造Traits::destroy(alloc_,new_end)主动调用数组最后一个有效元素的析构函数移除对象Traits::deallocate(alloc_,begin_,old_capacity)释放原数组申请的所有内存Traits是提供统一接口的内存管理器它调用alloc_提供的接口函数管理内存和对象。四个接口都要传入alloc_实例是因为——如果希望在操作内存或对象时增加一些自定义逻辑比如统计构造次数、使用特殊内存、记录调试信息……就需要传入自定义alloc_。为了兼容这种需求所以Traits的接口都要求传入alloc_实例扩容数组元素个数即将超出容量——触发扩容首先调用grow()grow()算出new_capacity通常扩充为原容量的 2 倍或 1.5 倍然后调用reallocate(new_capacity)reallocate(new_capacity)通过静态方法Traits::allocate申请new_capacity大小的新内存然后把原数组元素迁移过去优先移动构造其次拷贝构造。如果构造过程中抛出异常立即析构所有对象并释放新申请的内存然后将异常抛给上层如果成功构造就析构原有内存上的对象并释放所有内存然后更新三个指针