本篇目标掌握vector部分接口的简单实现一.vector类的底层实现1.三个指针首先通过对前面vector的使用我们就已经知道了vector可以实例化出intvectorintstring等各种类型无论是内置类型还是自定义类型都可以实例化那么我们自然就想到了vector的底层实现必然是有模板的参与但是有了模板以后我们就无法将类中接口的声明与定义放在两个不同的文件里了而通过对string的底层的探索我们知道了string底层是通过指针来管理一片连续的空间的那么vector 如何管理一块连续空间首先vector需要记录三个信息空间从哪里开始才能找到存储的元素。已经存了多少个元素对应size()。总共能存多少个元素对应capacity()用于判断是否需要扩容。这三个信息可以通过三个边界位置来表示指针含义_start存储空间的起始位置_finish最后一个有效元素的后一个位置_end_of_storage整块存储空间的结束位置即容量边界简化后成员可以这样写T* _start; T* _finish; T* _end_of_storage;由于元素连续存储指针相减就能得到元素个数size _finish - _start; capacity _end_of_storage - _start;例如已经存了3 个元素但分配了5 个元素的空间_start位于起点。_finish位于起点后第3个元素的位置。_endofstorage位于起点后第5个元素的位置。当_finish _end_of_storage时说明空间已经用满再插入就需要扩容。所以vector的大致框架为:在vector.h中#pragma once #include iostream #include assert.h using namespace std; namespace kong { templateclass T class vector { public: vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} private: T* _start; T* _finish; T* _end_of_storage; }; }注意其实底层也是通过三个指针来实现的但是目前vector的底层过于复杂就不带大家来验证了。2.迭代器前面我们已经知道vector 通过起始指针和有效元素的结束指针确定了元素所在的范围。那么当我们想在容器外部遍历这些元素时应该如何访问它们呢这些指针属于 vector 的内部成员我们可以通过begin()和end()向外提供有效元素范围的起点和终点。遍历时我们需要一种对象能够通过*访问当前元素通过移动到下一个元素并通过比较判断是否到达终点。这样的对象就是迭代器。由于 vector 的元素连续存储普通指针本身就支持这些操作因此在模拟实现 vector 时可以直接使用T*作为迭代器类型。begin()返回指向第一个元素的迭代器end()返回指向最后一个元素后一个位置的迭代器。于是从begin()开始不断向后移动直到到达end()就能遍历所有元素。注意end()表示遍历的终点不能对它进行解引用。示意图迭代器让我们通过统一的方式访问容器中的元素。对于其他存储结构的容器也可以提供支持相应操作的迭代器而不必让使用者直接处理它们的内部结构。所以为了与库保持一致我们就需要将T*typedef一下修改后的框架:namespace kong { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} private: iterator _start; iterator _finish; iterator _end_of_storage; }; }知道了上面的意思后迭代器的实现就简单了如代码所示:iterator begin() { return _start; } iterator end() { return _finish; } const_iterator cbegin()const { return _start; } const_iterator cend()const { return _finish; }顺便将size()capacity()和empty()实现一下:size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; }3.reserve接口我们发现当 vector 的容量不足以容纳新元素时需要先进行扩容。而后续的插入等操作也可能遇到容量不足的问题。因此我们可以将扩容逻辑单独封装成一个接口方便其他操作复用这就引出了reserve。reserve(n)用于保证 vector 的容量至少为 n。如果 n 不大于当前容量就不需要进行任何操作如果 n 大于当前容量就申请新的空间将原有元素迁移过去释放旧空间并更新三个指针。注意reserve只增加容量不增加有效元素的个数。代码块:templateclass T void vectorT::reserve(size_t n) { if (n capacity()) { T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start tmp; _finish _start size(); _end_of_storage _start n; } }注意这个是将reserve的实现放到了类外的但是我们还要指明这是那一个类里面的以及添加模板后续对应一些较长的代码我都是写在类外的当然大家也可以写在类里面。4.push_back接口前面我们已经了解了 vector 如何通过三个指针管理连续空间以及如何通过迭代器访问其中的元素。那么当我们需要向 vector 中添加一个新元素时又该如何操作呢这里先考虑最常用的尾部插入操作也就是push_back接口。由于_finish指向最后一个有效元素的后一个位置如果还有剩余容量就可以将新元素放到这个位置然后让_finish向后移动一个位置。这样有效元素的个数就增加了一个。不过插入之前还需要判断空间是否已经用满。当_finish _endofstorage时说明当前容量不足不能直接插入需要先扩容申请更大的空间将原有元素迁移过去释放旧空间并更新三个指针然后再完成尾部插入。因此实现push_back时需要先检查容量再根据情况完成扩容和插入。代码块templateclass T void vectorT::push_back(const T x) { if (_finish _end_of_storage) { //我们需要先找到旧空间的空间大小 size_t newCapacity capacity() 0 ? 4 : 2 * capacity(); reserve(newCapacity); } *_finish x; _finish; }测试代码void test_vector1() { kong::vectorsize_t v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); v.push_back(7); v.push_back(8); for (auto x : v) { cout x ; } cout endl; }可是测试结果这个居然显示错误了那么就让我们调试一下吧如图错误如图为啥这个_finish的地址是nullptr啊我不是已经在reserve里面更新了_finish吗答案我们确实是在reserve里面更新了_finish但是我们是先更新_start为tmp此时_start指向的是新的地址而_finish仍然指向旧空间地址那么我们调用size()即_finish-_start时不就是用旧地址减去新地址然后再加上_start那么_finish_start_finish-_start那么_finish不还是旧地址吗而我们构造时_finish不是nullptr吗所以我们*nullptr不就报错了吗那么该咋解决我们可以先更新_finish但是这样写不太雅观但是我们可以先保存一下旧的size后面更新时用old_size_start即可更新后的reserve如代码所示templateclass T void vectorT::reserve(size_t n) { if (n capacity()) { //我们需要先找到旧空间的空间大小 size_t old_size size(); T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * old_size); delete[] _start; } _start tmp; _finish _start old_size; _end_of_storage _start n; } }此时我们再进行测试就可以得出正确的结果了。5.pop_back()接口尾部删除的接口实现就非常简单了如代码templateclass T void vectorT::pop_back() { assert(!empty()); _finish--; }6.insert接口前面我们已经实现了push_back可以在 vector 的尾部插入数据那么如果我们想在开头或者中间插入数据又该怎么办呢这就需要引入insert接口了。我们可以通过迭代器指定插入位置将新的数据插入到这个位置。那么该如何实现呢由于 vector 管理的是一块连续空间我们不能直接将数据放到指定位置否则就会覆盖原来的数据。因此我们需要先将插入位置及其后面的元素从后往前依次向后移动一位腾出位置后再放入新的数据最后让_finish向后移动一位。当然如果空间已经满了就需要先通过reserve扩容再进行插入。然后我们这个insert的移动与string中的insert移动也一样就不再演示了。代码块templateclass T void vectorT::insert(iterator pos, const T x) { assert(pos _start pos _finish); if (_finish _end_of_storage) { size_t newCapacity capacity() 0 ? 4 : 2 * capacity(); reserve(newCapacity); } // 将插入位置及其后面的元素整体向后移动一位 std::memmove(pos 1, pos, sizeof(T) * (_finish - pos)); *pos x; _finish; }测试代码void test_vector2() { kong::vectorint v; v.insert(v.begin(), 1); v.insert(v.begin()1, 2); v.insert(v.begin()2, 3); v.insert(v.begin()1, 4); v.insert(v.begin()2, 5); v.insert(v.begin()5, 6); for (auto x : v) { std::cout x ; } std::cout std::endl; }运行结果为啥又出错了呢让我们再调试检查一下吧如图我们仔细一看嗯为啥又读到nullptr了此时_start和_finish都指向同一个地址说明还没有插入任何数据而_end_of_storage与_start的地址相差十六进制的0x10也就是 16 字节对于int类型来说正好可以存放 4 个元素。这说明空间已经开辟成功了啊可是为什么pos仍然是nullptr呢那么我们再仔细想一下这个pos保存的不还是扩容之前的地址吗扩容后_start、_finish和_end_of_storage都已经更新为新空间中的对应位置但是pos并不会跟着它们自动更新它仍然保留着原来的值。这里原来的值就是nullptr那我们继续使用这个旧的pos不就会出错了吗所以我们需要在扩容之前先保存pos相对于_start的偏移量等扩容完成后再根据新的_start和之前保存的偏移量重新确定pos的位置这样它才能正确指向新空间中的插入位置。所以我们还需要更新一下pos因此我们需要记录一下lenlenpos-_start;如代码所示:templateclass T void vectorT::insert(iterator pos, const T x) { assert(pos _start pos _finish); if (_finish _end_of_storage) { size_t lenpos-_start; size_t newCapacity capacity() 0 ? 4 : 2 * capacity(); reserve(newCapacity); pos_startlen; } // 将插入位置及其后面的元素整体向后移动一位 std::memmove(pos 1, pos, sizeof(T) * (_finish - pos)); *pos x; _finish; }7.erase接口前面我们已经实现了insert接口可以在指定位置插入数据那么如果我们想删除指定位置的数据又该怎么办呢这就需要引入erase接口了同样通过迭代器来指定要删除的位置。那么该如何实现呢由于 vector 管理的是一块连续空间删除一个元素后我们需要将它后面的元素依次向前移动一位覆盖掉要删除的数据最后让_finish向前移动一位这样有效元素的个数就减少了一个。这里减少的是size而capacity不变因为我们并没有释放原来开辟的空间。需要注意的是end()指向最后一个有效元素的下一个位置并没有可供删除的元素所以传入的位置必须满足pos _start pos _finish。代码块templateclass T voud vectorT::erase(iterator pos) { assert(pos _start pos _finish); for (iterator it pos 1; it _finish; it) { *(it - 1) *it; } _finish--; }测试代码void test_vector2() { kong::vectorint v; v.insert(v.begin(), 1); v.insert(v.begin()1, 2); v.insert(v.begin()2, 3); v.insert(v.begin()1, 4); v.insert(v.begin()2, 5); v.insert(v.begin()5, 6); v.insert(v.begin()5, 6); for (auto x : v) { std::cout x ; } std::cout std::endl; for (auto it v.begin(); it v.end(); ) { if (*(it) % 2 0) { v.erase(it); } it; } std::cout std::endl; for (auto x : v) { std::cout x ; } std::cout std::endl; }运行结果看这个运行结果是不是非常的奇怪为啥6没有被删除呢?那么要讲清楚这个就要提到迭代器失效问题了。8.迭代器失效通过上面的报错让我来解释一下吧。你插入数据后vector 中的元素为1 4 5 2 3 6 6当it指向4时执行erase(it)后面的元素依次向前移动得到1 5 2 3 6 6在你当前使用指针作为迭代器的实现中it保存的地址没有改变但是这个位置上的数据已经由4变成了5。如果接着执行it就会走到2跳过刚刚移动过来的5。跳过奇数暂时看不出问题但是最后两个连续的6就能体现出来操作vector 中的元素it所在位置删除前一个6之前1 5 3 6 6前一个6删除后后一个6向前移动1 5 3 6移动过来的6再执行it1 5 3 6新的end()此时循环结束移动过来的6没有被检查所以最终输出的是1 5 3 6对于标准std::vectorerase会使删除位置及其后面的迭代器失效应该使用它返回的有效迭代器继续遍历。因此我们模拟实现的erase也可以返回删除位置删除后下一个元素会移动到这里如果删除的是最后一个元素这里就是新的end()。代码templateclass T typename vectorT::iterator vectorT::erase(iterator pos) { assert(pos _start pos _finish); for (iterator it pos 1; it _finish; it) { *(it - 1) *it; } _finish--; return pos; }然后我来解释一下这个typename的作用在这段代码中templateclass T typename vectorT::iterator vectorT::erase(iterator pos)typename的作用是告诉编译器后面的vectorT::iterator是一个类型名。我们在类中定义过typedef T* iterator;所以知道iterator是类型。但是vectorT依赖模板参数T这种依赖模板参数的名字称为依赖名。编译器解析模板时不能仅凭vectorT::iterator就确定它是类型还是静态成员变量等其他成员。因此写上typename vectorT::iterator就是明确告诉编译器“把它当作类型来解析它是这个函数的返回类型。”那么insert其实也会犯同样的问题如果insert触发扩容it仍然指向旧空间。虽然insert内部修正了pos但外面的it不会自动更新所以后面的*it和it都会出问题所以我们也应该返回插入后的位置代码templateclass T typename vectorT::iterator vectorT::insert(iterator pos, const T x) { assert(pos _start pos _finish); if (_finish _end_of_storage) { //我们需要先找到旧空间的空间大小 size_t len pos - _start; size_t newCapacity capacity() 0 ? 4 : 2 * capacity(); reserve(newCapacity); pos _start len; } memmove(pos 1, pos, sizeof(T) * (_finish - pos)); *pos x; _finish; return pos; }9.resize接口前面我们已经实现了reserve接口可以调整 vector 的容量那么如果我们想直接调整有效元素的个数又该怎么办呢这就需要引入resize接口了。假设我们要将有效元素的个数调整为n那么就需要分情况考虑如果n小于当前的size()就将有效元素的个数缩减到n如果n大于当前的size()就需要补充新的元素并用指定的值进行初始化。如果没有指定这个值对于int类型新增元素就初始化为0。当然增加元素时也要考虑空间是否足够。如果n大于当前的capacity()就需要先通过reserve扩容再填充新增的元素最后更新_finish。所以reserve调整的是容量而resize调整的是有效元素的个数缩小size时容量并不会随之缩小。代码块templateclass T void vectorT::resize(size_t n, const T x) { if (n capacity()) { reserve(n); } if (n size()) { for (size_t i size(); i n; i) { push_back(x); } } else { _finish _start n; } }10.构造函数我们之在使用vector的构造函数时是可以用一个vector的迭代器区间构造的那么这个的实现也是十分的简单的如代码template class InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } }之前我们实现的构造是vector的默认构造函数那么此时我们就需要实现vector的拷贝构造那么就需要用到现代的写法那么就需要用到swap函数了如代码所示:void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }拷贝构造vector(const vectorT v) { vector tmp(v.cbegin(), v.cend()); swap(tmp); }还有个构造函数如代码所示vector(size_t n, const T x T()) { reserve(n); for (size_t i 0; i n; i) { push_back(x); } }测试代码void test_vector3() { kong::vectorint v1(10,1); kong::vectorint v2(v1); for(autox:ch) { coutx ; } }运行结果这又整啥幺蛾子呢答案问题主要出在这一句kong::vectorint v1(10, 1);你想调用的是“创建 10 个值为 1 的元素”的构造函数但编译器优先匹配了迭代器构造函数。看这两个构造函数vector(size_t n, const T x T()); templateclass InputIterator vector(InputIterator first, InputIterator last);10 和 1 都是 int第一个构造函数需要将 10 从 int 转成 size_t。第二个构造函数可以直接推导出 InputIterator int两个参数都精确匹配。但是第二个匹配得更好编译器会尝试实例化vector(int first, int last) { while (first ! last) { push_back(*first); first; } }但是first 是 int不能解引用。你可以先这样修改调用让第一个参数明确为 size_tkong::vectorint v1(10u, 1);此时两个参数类型分别为 size_t 和 int迭代器构造函数无法将它们推导为同一个 InputIterator就会调用你需要的构造函数。我们也可以再添加一个int的如代码所示:vector(int n, const T x T()) { reserve(n); for (int i 0; i n; i) { push_back(x); } }11.赋值重载函数首先呢我们需要重载一下[]如代码T operator[](size_t pos) { assert(pos size()); return _start[pos]; } const T operator[](size_t pos)const { assert(pos size()); return _start[pos]; }然后重载一下如代码所示vectorT operator(vectorT v) { swap(v); return *this; }12.析构函数~vector() { delete[] _start; _start _finish _end_of_storage nullptr; }注意当我们没有写析构函数时我们还没有写拷贝构造和关于的赋值重载那么此时的拷贝构造和vector和vector间的赋值都是浅拷贝。13.通用打印前面我们在测试 vector 时每次都要写一段遍历代码来打印里面的数据那么能不能将这部分代码封装起来写成一个通用的打印函数呢自然就想到了函数模板让Container表示传入的容器类型。只要容器支持这里使用的迭代器接口我们就可以通过同一个函数来遍历并打印其中的元素。由于打印只需要读取数据不需要修改容器所以参数使用const Container既避免了拷贝也限制了对容器的修改。同时我们通过cbegin()和cend()获取遍历范围使用Container::const_iterator来访问元素。这里的迭代器类型依赖模板参数Container因此在前面加上typename明确告诉编译器它是一个类型名。代码块templateclass Container void print(const Container con) { typename Container::const_iterator it con.cbegin(); while (it ! con.cend()) { cout *it ; it; } cout endl; }14.浅拷贝问题或许到了这里有人觉得浅拷贝的问题都已经解决了倘若我给你个这样的测试用例呢void test_vector3() { kong::vectorstring v; v.push_back(terhsehseheshdhdhhfg); v.push_back(terhsehseheshdhdhhfg); v.push_back(terhsehseheshdhdhhfg); v.push_back(terhsehseheshdhdhhfg); v.push_back(terhsehseheshdhdhhfg); v.push_back(terhsehseheshdhdhhfg); print(v); }运行结果这个打印结果是乱码而且还报错了吗、那么这到底是什么问题呢哪么这就要提到memcpy的浅拷贝问题了。问题这里要分清两层空间vector 开辟的空间存放的是string对象而string对象自身还可能管理另一块存放字符的动态空间。T* tmp new T[n]; memcpy(tmp, _start, sizeof(T) * old_size);我们确实给 vector 开辟了新的空间但是memcpy只是将旧string对象的字节原样复制到新对象中。如果旧对象内部保存着指向字符空间的指针这个指针的地址也会被直接复制而不会另外开辟字符空间。这样新旧两个string对象就会指向同一块字符空间这就是这里所说的浅拷贝问题。接下来执行delete[] _start;它不仅释放旧 vector 的空间还会先调用其中每个string对象的析构函数释放它们管理的字符空间。但是新对象中复制过来的指针仍然保存着原来的地址此时这些指针就成了悬空指针。所以后续打印时可能访问已经释放的空间出现乱码或报错等新对象析构时还可能再次释放同一块空间造成重复释放。示意图所以我们应该将memcpy替换成如下的代码for (size_t i 0; i old_size; i) { tmp[i] _start[i]; }这时执行的是T的赋值操作如果是自定义类型就调用它的赋值重载函数没有的话仍然是浅拷贝所以当T为std::string时会调用它的拷贝赋值运算符正确复制字符串内容让新对象拥有独立的字符串数据。这样销毁旧对象就不会影响新对象。同理memmove也有同样的问题它和memcpy都是直接复制字节不会调用对象的拷贝构造或赋值运算符。两者的区别在于memmove支持源区间和目标区间重叠但这并不能解决string内部资源的浅拷贝问题。修改后的insert代码templateclass T typename vectorT::iterator vectorT::insert(iterator pos, const T x) { assert(pos _start pos _finish); if (_finish _end_of_storage) { //我们需要先找到旧空间的空间大小 size_t len pos - _start; size_t newCapacity capacity() 0 ? 4 : 2 * capacity(); reserve(newCapacity); pos _start len; } for (iterator i _finish; i pos; i--) { *(i) *(i-1); } *pos x; _finish; return pos; }总结本篇通过模拟实现 vector 的常用接口理解了它如何利用三个指针管理连续空间以及 size 与 capacity 的区别。通过插入、删除和扩容中的问题我们认识了迭代器失效并了解了如何通过返回值继续正确遍历。最后通过 vectorstring 的测试明白了容器开辟新空间并不意味着其中的对象完成了深拷贝处理这类对象时应使用类型自身的拷贝或赋值操作而不能直接使用 memcpy、memmove 复制字节。