vector底层机制vector本质是一个动态分配连续内存的数组维护了三个指针迭代器_start指向连续内存的起始物理地址_finish指向当前最后一个有效元素下一个位置_end_of_storage指向整块内存的末尾有了三个指针所有方法都是指针运算size()当前元素个数就是finish - startcapacity()当前总容量就是end_of_storage - startempty()是否为空就是判断start finish这里需要注意CSTL设计是左闭右开[start, end)动态扩容机制什么时候会扩容怎么扩容触发场景_finish _end_of_storage时没有空间塞数据了做法一定不是原地扩容OS很难在原内存后面找到一块合适的空间去堆上找一块全新的、更大的内存GCC通常2倍MSVC通常1.5倍把老内存里的数据逐一**拷贝或移动**到新内存调用老内存中所有对象的析构函数释放老内存空间为什么不能原地扩容涉及到缓存命中的问题内存碎片堆上的内存分配是动态、无序的new了一个100字节内存随着程序运行这100字节前后的内存大概率都被其它对象占用了缓存命中CPU从内存中读数据非常慢本质是拷贝CPU内部有L1/L2/L3三级缓存SRAMCPU每次去内存拿数据会把目标地址附近的一整块连续内存通常是64字节一个Cache Line一次性取完如果vector容量满了你想在原地直接把这块内存拉长现实中极大概率是做不到的因为屁股后面紧挨着的那块物理内存已经被别人占了深拷贝、浅拷贝、移动辨析浅拷贝纯粹按位赋值对于内置类型没问题但是对于自定义类型浅拷贝只会拷贝指针的地址这导致了新老vector里的指针指向同一块内存任意一方修改数据会影响到另一方而且会造成Double Free问题深拷贝开辟一块和源vector一样的内存空间并拷贝源vector的数据到新的内存中移动语义老内存若是快要销毁直接把老对象的资源指针偷过来把老对象的指针置空即可注意只有当类明确使用noexcept标记了移动构造函数时vector扩容才会大胆地使用移动语义vector是极其保守的迭代器机制迭代器本质是封装了指针的类对象并重载了、--、\*、-等运算符对于使用者来说无论底层是连续数组还是复杂的红黑树都可以统一使用it来走向下一个元素用*it来获取数据。它完美屏蔽了底层数据结构内存布局的差异这就是C封装的思想屏蔽底层实现细节暴露给用户一套标准的操作接口用户不用关心底层到底是怎么实现的但是迭代器很容易失效我们先讲连续内存派vector、string为例失效场景1触发动态扩容原因vector扩容是去堆上找一块新内存然后把老内存释放掉。如果在扩容前保存了一个迭代器扩容后这个迭代器里面包着的指针还指着那块已经被系统回收的老内存解决 扩容后绝对不要使用任何之前保存的迭代器、指针或引用。如果需要记录位置记录索引而不是迭代器失效场景2中间插入或删除原因 当调用v.erase(it)删除中间某个元素时为了保持物理连续性vector会把该位置之后的所有元素统统往前挪一步。此时手里的it虽然物理地址没变但它指向的数据已经变成了原本在它后面的那个元素如果你再执行一次it你就会漏掉一个元素解决利用erase的返回值。erase会自动返回一个指向被删除元素下一个位置的有效迭代器// 错误写法会漏删元素或者越界崩溃while(it!v.end()){if(*it2)v.earse(it);it;}// 正确写法while(it!v.end()){if(*it2)itv.earse(it);// 删除了erase已经帮你走了一步接管新迭代器就好elseit;// 只有在没有删除的情况下才会手动往后走}高频APIpush_back()和emplace_back()push_back的本质接收一个已经构造好的对象或者右值。在底层会调用拷贝构造函数或移动构造函数将数据放进vector的内存中emplace_back的本质它的底层使用了 C11 的可变参数模板和完美转发。它不接收对象而直接接收“构造对象所需的参数”然后在vector_finish指针指向的那块裸内存上直接调用定位 newPlacement new原位构造对象emplace_back伪代码templatetypename...Args// 1. 可变参数模板接收任意数量参数voidemplace_back(Args...args){// 万能引用接住所有左值/右值// 检查容量不够就扩容...if(_finish_end_of_storage){// ... 扩容逻辑}// 核心动作// 2. 完美转发std::forwardArgs(args)... 原封不动地把参数状态传下去// 3. 定位 new在 _finish 裸指针指向的内存上直接原地构造对象new((void*)_finish)T(std::forwardArgs(args)...);// 指针后移_finish;}为什么emplace_back比push_back快两者执行v.push_back(User(张三, 18))和v.emplace_back(张三, 18)时的动作push_back路线在外面的栈上构造一个临时的User对象把临时对象作为参数传进push_backpush_back内部调用移动构造函数或拷贝构造把数据挪到_finish的内存上析构外面栈上的那个临时User对象emplace_back路线把字符串张三和整数18打包完美转发到底层在_finish内存上直接调用带参构造函数一次性成型零次临时对象创建零次拷贝/移动构造零次临时对象析构总结只要是往容器尾部追加元素无脑优先使用emplace_backclear()clear的本质是逻辑清空循环调用所有有效元素的析构函数然后把_finish指针拉回到_start的位置size归零但是capacity还占着呢内存并没有释放把这个释放时机交给用户处理那怎么释放这块大内存呢std::vectorintv;// ... 假设 v 经历了大量插入capacity 暴涨到了 100000但现在 size 只有 10// v.clear(); // 没用capacity 还是 100000// 利用匿名临时对象交换指针std::vectorint(v).swap(v);std::vectorint(v)触发拷贝构造创建了一个匿名临时对象只申请刚好能装下 10 个元素的内存它的capacity就是 10.swap(v)将临时对象内部的三个指针与原来v内部的三个指针进行互换。互换后v的容量成功收缩到了 10。而那个匿名临时对象手里现在攥着原来那 100000 的庞大内存这行代码一结束匿名临时对象生命周期到期自动调用析构函数顺理成章地带着那块庞大的内存同归于尽resize()和reserve()reserve(n)预留空间操作的是_end_of_storage指针动作和OS交涉“给我准备能装n个元素的连续空间”结果只改变capacity绝对不改变size_finish指针保持不动新开辟的空间未初始化绝对不能v[index]去访问resize(n)调整大小操作_finish指针动作它不仅要求物理空间到位还会在这些空间上真正去构造对象结果它同时改变capacity和size。如果n大于当前的size它会调用对象的默认构造函数把多出来的坑填满。填满后可以直接用v[index]去访问修改未完待续~