一、vector与二维数组1.vectorvectorint在内存中如下存储_a是指向首元素的指针变量与元素类型相同下图中vectorvectorint表示二维数组看图中代码了解其写法图中vv[2][1]有两种理解方法一种直接按二维数组理解另外需要按照调用类的函数模板理解按照调用类的函数模板去理解_a[i]等价于 *(_a i)取出数组第 i 个元素以引用返回。左图为类的函数模板vv[2][1] 其实是调用了两个不同类的运算符重载operator[]函数。编译器从左到右依次首先读到vv[2]因为vv类型是vectorvectorint所以调用其对应模板结合vectorvectorint在内存中的存储方式且返回的是引用即返回下标为2的vectorint对象。继续从左到右读vv[2][1] 实际就是在下标为2的vectorint对象中找下标为1的元素找到后返回其引用。2.遍历这个二维数组二、练习只出现一次的数杨辉三角没看三、要尝试看源代码带着看了vector源代码没看源代码书籍推荐四、vector 模拟实现1.了解vector底层1vector 底层是一块连续堆内存靠 3 个指针管理内存start指向有效元素内存的起始位置对应begin()迭代器。finish指向最后一个有效元素的下一个位置。end_of_storage指向整块分配内存空间的末尾。2size 和 capacitysize()有效元素个数 finish - start左闭右开capacity()总容量 end_of_storage - start整块内存一共能存多少元素包含已经使用 备用空闲空间。size ≤ capacity备用空间就是finish ~ end_of_storage之间未使用的内存。3begin() / end()begin() 返回 start指向第一个元素。end() 返回 finish指向最后有效元素后面不是最后一个元素本身。vectorint iv(2,9); //初始化2个元素都为9此时size2iv.push_back(1);iv.push_back(2);iv.push_back(3);iv.push_back(4);有效元素依次991234start指向第一个9。finish指向 4 的后一个位置size6。end_of_storage在 finish 更靠后4后面两个是预留备用内存。operator[3]下标访问取索引为 3 的元素也就是2。4vector 扩容机制图中文本增加新元素如果超出当前容量就扩容。当push_back()size 等于 capacity备用空间耗尽必须扩容。旧 SGI‑STL vector 扩容策略容量扩大为原来2 倍如果 2 倍还不够则直接分配到需要的大小。重点不是直接在原内存后面追加扩容真实步骤① 在堆上开辟一块更大的新内存② 把旧内存全部元素拷贝移动到新空间③ 释放销毁原来旧的整块内存④ 更新 start、finish、end_of_storage 三个指针指向新内存。图上只是画示意图看起来像是原内存后面加长实际旧内存直接废弃地址全部改变。扩容后所有旧迭代器、指针全部失效因为内存已经换地方。2.模拟实现3 个指针因为是模拟实现模板模板只能在一份文件声明定义所以vector模拟实现只有两个文件.h .cpp因为库中只支持迭代器所以这里重命名原生类型指针T*当作iterator3.完成构造函数先给缺省值完成构造函数因为是内置类型所以不用显示写直接用默认构造即可。当然后面还得写因为后面要写深拷贝的拷贝构造之后默认构造就无法自己生成了规则只要用户声明了任意一个构造函数不管是普通有参构造、拷贝构造编译器就不再隐式合成默认无参构造函数。拷贝构造本质上也是构造函数只要手写了拷贝构造就属于 “用户声明构造函数”。4.push_back如果还有空闲空间就在_finish位置附加X,如果没有就用函数reserve扩容实现函数reserve又需要知道对象现在的size长度_capcity容量所以先实现这三个函数上下一样5.函数size_capcityreserve实现记得在.h加断言头文件new T[n]分配 n 个 T 对象的内存对每一个元素调用 T 的默认构造函数。 所以拿到的 tmp 指向的数组里面全部是已经构造完成、初始化好的对象可以直接赋值。没有初始化好的不可以直接赋值。new失败抛异常扩容n capacity需要new一块更大内存拷贝元素释放旧内存更新信息。目的提前预留空间避免未来 push_back 反复重分配提升性能。这就是 reserve 的本职工作。缩容n capacity要new一块更小内存、拷贝元素、释放原来的大块内存更新信息为什么vestor的reserve 不做缩容1.接口语义reserve的含义预先预留至少 n 个元素的空间目的是扩容避免多次 realloc不是用来释放内存。2.职责分离缩容交给另外一个接口shrink_to_fit()C 把两个行为拆开shrink_to_fit()请求把 capacity 降低到等于 size释放多余内存。3.性能角度缩容开销很大还容易引发反复震荡分配举一个典型场景就好比你租了一间可以放 100 个箱子的仓库。reserve(n)语义保证仓库至少能放下 n 个箱子。现在仓库能放 100 箱你说 “保证至少放 50 箱”仓库不会主动换一间更小的仓库。只有当你要求 “保证放 200 箱”才会去租更大仓库。想换小仓库单独调用shrink_to_fit主动申请换小仓库。如果 reserve 一看到更小数字就换小仓库万一你马上又要堆很多箱子又得重新租大仓库来回折腾开销巨大。1.push_back已经判断_finish _end_of_storage为什么还需要三目运算符capacity()0 ? 4 : capacity()*2答_finish _end_of_storage只代表现在空间满了但此时capacity()有可能等于 0如果没有三目直接写reserve(capacity()*2)就是reserve(0*2)reserve(0)调用reserve(0)不会扩容还是 0 容量后续*_finishx对空指针解引用程序直接崩溃。2.push_back 已经确认要扩容了传给 reserve 的 n 一定 capacity 为什么 reserve 内部还要写if(ncapacity())判断答1就算在 push_back 内部调用也要做防御虽然 push_back 逻辑上传给 reserve 的 n 一定大于 capacity但函数不能假设调用者一定传合法参数。函数本身要保证自身安全。举例子如果以后修改 push_back 代码改错传进去 n 比 capacity 小reserve 内部判断就可以阻止错误的内存操作。2reserve 还是对外的 public 成员函数用户代码也要调用要保证符合C 标准强制规定只扩容不缩容6.运算符重载operator[] 返回某位置引用测试在.h文件中包进头文件assert.h , 在.h文件中写出如下测试函数。先在test.cpp文件中包进头文件以便后续调用库中模板类再在包.h文件否则vector.h 内部 std 符号会找不到。在.cpp中运行该函数结果如下运行失败为什么delete[] _start; //释放的是 this-_start 指向的堆数组不会销毁 this 指向的对象本身。_start tmp; // _start 在这里才被改成新地址_finish _start size(); //这一行_end_of_storage _start n;执行顺序拆解1. _start tmp;把成员_start改成新空间的地址。2. 紧接着调用 size()size()函数return _finish - _start;❗此时_start已经是新地址_finish还没被修改仍然保存旧空间的旧_finish 的值旧_finish 指向旧内存已经被 delete [] 释放掉的野指针所以此时size() 旧_finish(野指针) − 新_start(有效新地址) 这是两个完全无关的指针相减结果完全是垃圾随机值可以先更新_finish再更新_start 或者提前将旧size()返回值给一个变量然后先更新_start再用该变量更新_finish再次测试7.迭代器支持迭代器就支持了范围for测试8.打印函数测试、报错原因所以const对象用const迭代器 也有了const begin() end()反向迭代器现在无法模拟实现测试时将迭代器名称改过来假设还有一个double类vector想打印他下面左图但之前的打印函数已经写死为int型上图所以将打印函数改为模板直接将int 改为 T但是编译报错显示缺少;原因若想在模板没有实例化前就确定::后是类型则需要在vectorT前加typename当然还可以用auto,意思是it的类型由v.begin自动推导9.pop_back 删除10.insert测试当插入后空间够用正常运行当插入时空间不够用需要扩容时测试崩溃 扩容有问题原因运行成功加入assert我现在输入某个值我也不确定它是否存在若它存在在它前面插入值所以首先要查找该值vector没有提供find所以用库算法里面的find它是个函数模板针对所有容器因为所有容器都支持迭代器将迭代器传给find下图val是要查找的值若果没找到返回last找到就返回其下标。注意C所有传迭代器区间时都是是左闭右开查 find 不用模拟实现用库算法里面的即可输入2插入40运行成功扩容了假如此时不仅要找到目标位置插入40还要让之前要找的x2变成2x1020有如下代码出错原因当插入40后pos位置依旧还是指向原来2的位置所以40变4002没有变在上图基础上再次输入240不变了为什么在调用insert函数时扩容将实参pos传给形参pos虽然函数内对形参pos进行了修正让它指向新pos,最后成功插入数据。但是*pos*10 的pos依旧是实参pos没有被修正相当于用野指针*1.为什么不能在形参pos上加那在上面基础上加const权限不就不变了吗但是形参pos无法改变所以insert之后,旧的实参pos不要再访问、改变了。可以将它更新为新pos再访问、改变下下图中库提供的insert可以帮助实现下图中p就是pos库中insert函数会返回迭代器迭代器指向新插入的元素位置(如下图模拟时不需要写成这样按原来模拟法即可)、