一、vector 简介1. 什么是 vectorvector是 C STL 提供的一个动态数组容器。普通数组int arr[10];特点大小固定内存连续不支持动态增长而 vectorvectorint v;特点动态开辟空间自动扩容支持随机访问内存连续可以存储任意类型例如#include iostream #include vector using namespace std; int main() { vectorint v; v.push_back(10); v.push_back(20); v.push_back(30); for(int x : v) { cout x ; } return 0; }输出10 20 30二、vector 的底层原理1. vector 的本质vector 底层维护了一块连续的动态内存。内部类似templateclass T class vector { private: T* _start; // 指向数据起始位置 T* _finish; // 指向有效数据末尾 T* _endofstorage; // 指向空间末尾 };三个核心指针_start | v ---------------- | 10 | 20 | 30 | | ---------------- ^ | _finish ^ | _endofstorage2. size 和 capacityvector 有两个重要概念size表示当前存储了多少个元素例如vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); cout v.size();输出3capacity表示当前vector申请了多少空间代码vectorint v; v.push_back(1); cout v.capacity();可能输出1继续v.push_back(2); cout v.capacity();可能2size 和 capacity 区别概念含义size有效元素数量capacity已经申请的空间大小例如capacity 10 -------------------- | 1 | 2 | 3 | | | -------------------- size 3三、vector 的初始化方式1. 默认构造vectorint v;创建空vectorsize0 capacity02. 指定大小vectorint v(10);创建10个元素默认初始化0 0 0 0 0 0 0 0 0 03. 指定大小和值vectorint v(10,5);结果5 5 5 5 5 5 5 5 5 54. 数组初始化int arr[]{1,2,3,4}; vectorint v(arr,arr4);结果1 2 3 45. 拷贝构造vectorint v1(5,10); vectorint v2(v1);v210 10 10 10 10四、vector 常用接口1. push_back()作用尾插元素。vectorint v; v.push_back(10); v.push_back(20);结果10 20时间复杂度O(1)2. pop_back()删除最后一个元素。v.pop_back();例如10 20 30执行pop_back();结果10 203. size()获取元素数量。coutv.size();4. capacity()获取容量。coutv.capacity();5. empty()判断是否为空。if(v.empty()) { cout空; }返回true为空false非空6. clear()清空数据。v.clear();注意clear不会释放空间。例如vectorint v; v.push_back(1); coutv.capacity(); v.clear(); coutv.capacity();capacity仍然存在。7. resize()改变size大小。扩大vectorint v{1,2,3}; v.resize(5);结果1 2 3 0 0指定值v.resize(5,100);结果1 2 3 100 100缩小v.resize(2);结果1 28. reserve()提前开辟空间。例如vectorint v; v.reserve(100);此时size0 capacity100用途减少扩容次数。例如没有reservefor(int i0;i10000;i) { v.push_back(i); }可能不断扩容1 2 4 8 16 32 ...有v.reserve(10000);一次申请capacity10000效率更高。五、vector 遍历方式1. 下标访问vectorint v{1,2,3}; for(int i0;iv.size();i) { coutv[i]; }2. 迭代器遍历vectorint::iterator it; for(itv.begin();it!v.end();it) { cout*it; }3. 范围forC11for(auto e:v) { coute; }推荐使用。六、vector 迭代器begin()返回第一个元素位置。v.begin();end()返回最后一个元素后面的位置。注意end不是最后一个元素例如1 2 3 ^ ^ | | begin endrbegin()反向开始。v.rbegin();rend()反向结束。七、vector 插入和删除1. insert()指定位置插入。vectorint v{1,2,3}; v.insert(v.begin()1,100);结果1 100 2 3插入多个v.insert(v.begin(),3,5);结果5 5 5 1 2 32. erase()删除元素。删除指定位置v.erase(v.begin()1);删除区间v.erase(v.begin(),v.begin()2);八、vector 扩容机制重点当size capacity继续插入vector会申请更大空间拷贝旧数据释放旧空间例如原空间capacity4 1 2 3 4插入第五个重新申请capacity8 1 2 3 4 5扩容比例不同编译器不同常见2倍增长例如1 2 4 8 16 32九、vector 的深浅拷贝问题vector内部管理动态内存。例如vectorint v1{1,2,3}; vectorint v2v1;不是简单复制指针。而是v1 1 2 3 v2 1 2 3两个空间独立。属于深拷贝十、vector 存储自定义类型例如class Student { public: string name; int age; }; vectorStudent v; Student s1; s1.nameTom; s1.age18; v.push_back(s1);vector可以存intdoublestring类对象结构体十一、vector 的优缺点优点1. 随机访问快因为连续空间v[100];时间复杂度O(1)2. 尾插效率高push_back()平均O(1)3. 内存连续利于CPU缓存。缺点1. 中间插入慢例如1 2 3 4 5插入100需要移动2 3 4 5复杂度O(n)2. 扩容成本扩容需要申请新空间拷贝数据十二、vector 和其他容器比较容器特点vector动态数组list链表deque双端队列array固定数组map键值结构set集合vector vs listvectorlist底层数组链表随机访问快慢头插慢快空间利用高低十三、vector 常见面试问题1. vector为什么支持随机访问因为vector底层是一段连续内存。可以通过首地址 偏移量快速定位。2. vector扩容为什么效率低因为需要新空间拷贝元素释放旧空间3. reserve和resize区别函数作用reserve改变capacityresize改变size例如vectorint v; v.reserve(100);结果size0 capacity100而v.resize(100);结果size100 capacity1004. 为什么vector的迭代器会失效因为扩容旧地址0x1000新地址0x2000原迭代器仍指向旧空间。十四、vector模拟实现简单版本templateclass T class Vector { public: Vector() { _startnullptr; _finishnullptr; _endnullptr; } void push_back(const T x) { if(_finish_end) { size_t oldcapacitycapacity(); size_t newcapacity oldcapacity0?4:oldcapacity*2; reserve(newcapacity); } *_finishx; _finish; } private: T* _start; T* _finish; T* _end; };核心思想三个指针动态扩容连续空间十五、vector使用建议1. 提前知道数量时使用reservevectorint v; v.reserve(10000);2. 避免频繁insert不要v.insert(v.begin(),x);大量数据使用deque/list3. 使用emplace_back例如v.emplace_back(Tom,18);相比v.push_back(Student(Tom,18));减少临时对象。十六、总结vector 是 C STL 中最重要的容器之一。核心知识知识点重点底层结构动态数组内存特点连续空间三个指针start、finish、endsize有效元素数量capacity申请空间大小扩容重新申请空间并拷贝访问随机访问O(1)尾插平均O(1)中间插入O(n)迭代器可能失效优势访问快缺点扩容和移动成本
)
