目录手写vector的必要性代码的骨架构造函数和析构函数默认构造填充构造迭代器区间模板带来的陷阱拷贝构造析构函数赋值重载reserve()和resize()reserve——预留空间问题1:这个地方能不能用memecpy?问题2这里面为什么要记录旧空间的大小和string的实现差别是什么resize()改变大小push_back和pop_back迭代器迭代器的失效问题insert和迭代器失效问题情况1扩容导致的失效insert 和 push_back情况2移动元素导致的失效insertearse和迭代器失效的问题手写vector的必要性在上文提过学习C标准库只知道他的用法只是在第一层除此以外还要理解他的内部实现原理知道内存怎么管理迭代器何时失效异常如何保证。更进一步的能根据特定场景定制容器甚至自己写一个符合 STL 规范的容器。因此本篇就来重点谈谈第二层——从会用到明理。代码的骨架#pragma once #includeassert.h #includelist #includestring namespace me { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; // ... private: iterator _start nullptr; iterator _finish nullptr; iterator _end_of_storage nullptr; }; }namespace bit通过自定义一个命名空间防止和std的vector造成冲突方便对比。templateclass T构建模板在class上面T是元素类型更有通用性这样T可以是任意类型甚至是vectorTtypedef T* iterator定义迭代器类型为原生指针。因为vector内存连续指针天然支持,--,n,-n等随机访问操作。const_iterator是const T*用于 const 对象防止修改元素。_start , _finish ,_end_of_storage:vector的核心描述vector骨架的关键。_start指向动态数组的第一个元素。_finish指向当前最后一个有效元素的下一个位置即end()。_end_of_storage指向当前分配的内存块的末尾即capacity的边界。这三个指针决定了所有容量的接口。为什么用三个指针而不是size和capacity变量因为指针运算更高效size _finish - _startcapacity _end_of_storage - _start。同时指针天然支持迭代器操作begin()和end()直接返回_start和_finish无需额外转换。size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; }构造函数和析构函数这里有两种写法vector() default;//C11 vector() {} vectorint v1; // 调用 vector() vectorint v2{}; // 也调用 vector()默认构造C11的写法是让编译器生成默认构造函数的默认实现所有成员执行默认初始化这里更推荐C的写法因为会按成员声明顺序执行默认初始化对于内置类型default 不初始化保持随机值但对于类类型会调用默认构造而vector {}也是什么都不做两者效果一样但default 更明确表达意图填充构造vector(size_t n, const T val T()) { reserve(n); for (size_t i 0; i n; i) { push_back(val); } } vector(int n, const T val T()) { reserve(n); for (int i 0; i n; i) { push_back(val); } } { vectorint v(10, 1);//针对这种类型的构造 }先看一个疑点const T val T()这里的T()是什么本质是构造函数这里面无论是内置类型还是自定义类型如果是内置类型T()默认是T(0),如果是自定义就调用默认构造函数vectorint v(10); //这样可以创建 10 个元素每个都是 0为什么会有两个版本迭代器区间模板带来的陷阱是为了区分迭代器版本的填充构造。template class InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } }这是一个函数模板成员函数——类模板的成员函数还可以继续是函数模板。当遇到迭代器区间构造的时候可以让任意类型的迭代器自动匹配。// 用 vector 的部分区间构造 vectorint v1 {1, 2, 3, 4, 5}; vectorint v2(v1.begin(), v1.begin() 3); // {1, 2, 3} // 用 list 构造 vector listint lt {10, 20, 30, 40}; vectorint v3(lt.begin(), lt.end()); // {10, 20, 30, 40}如果不写vector(int n, const T val T())会怎么样在没有vector(int n, const T val T())的情况如果是以下的构造会调用哪个函数vectorint v(10, 1);答案是可能会调用迭代器的构造引用10,1都是int类型根据匹配程度10不是size_t自动识别为模板类型的InputIterator更加匹配但是如果调用了迭代器的版本传入整形*first这行代码不能对整形值进行解引用所有会报错。当然编译器也可能会认为有二义性编译错误。拷贝构造vector(const vectorT v) { reserve(v.size()); for (auto e : v) { push_back(e); } }这里很容易理解v是vectorT类型的被const修饰只能读不能写不影响被拷贝的值。先给拷贝值一个预留的空间的大小然后通过for的迭代器进行遍历。析构函数~vector() { delete[] _start; _start _finish _end_of_storage nullptr; }这个函数很简单就是直接释放指向的空间注意的是只需要释放_start就可以了后面的都是指向的同一个空间。赋值重载// vectorT operator(const vectorT v) { if (this ! v) { clear(); reserve(v.size()); for (auto e : v) { push_back(e); } } return *this; } //v1v3 // 写法2 vectorT operator(vectorT v) { swap(v); return *this; }写法2更为简便而且他的时间复杂度是O(1),是传值传参v调用拷贝构造的时候v是v3的拷贝如果拷贝抛异常v1保持不变。reserve()和resize()reserve——预留空间void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* tmp new T[n]; // memcpy(tmp, _start, old_size * sizeof(T)); // 不能对vectorstring类型深拷贝 for (size_t i 0; i old_size; i) { tmp[i] _start[i]; // 逐个拷贝 } delete[] _start; _start tmp; _finish tmp old_size; _end_of_storage tmp n; } }问题1:这个地方能不能用memecpy?不能因为memcpy只能进行浅拷贝不能深拷贝。vectorstring v; v.push_back(1111111111111111111); v.push_back(world); v.reserve(100); // 扩容vectorstring本质就是vector容器里面加上了string然后string在细分为_str,_size_capacity,可以看成是容器对容器的包装所以当我我们使用memcpy的时候参数都是string类型的当我们拷贝的时候是整个string如图在拷贝的时候_size和_capacity是进行值拷贝的这个没有什么问题但是在拷贝_str的时候他会把_str里面存放的旧空间的地址拷贝给新空间的_str这样的话就会造成他们共同有一个地址当调用string的析构函数的时候就会释放两次就是所谓的野指针。所有说memcpy只是复制的是对象的外壳对于有指针成员的对象会把地址复制就会让新空间和就空间的指针成员的对象共享一块内存空间析构的时候就会释放两次形成野指针。因此这里面利用了for循环将成员指针变量逐个赋值问题2这里面为什么要记录旧空间的大小和string的实现差别是什么错误写法void reserve(size_t n) { if (n capacity()) { T* tmp new T[n]; // ... 拷贝数据 ... delete[] _start; _start tmp; _finish tmp size(); // 错误 调用 size()但 _start 已经是新地址了 // 这时 size() _finish - _start但 _finish 还没更新结果是随机的 _end_of_storage tmp n; } }在使用size()的时候由于上段代码delete掉了_start又因为size()是需要通过_finish来计算的这个时候由于_start和_finish不是在同一连续的内存当中的所以需要先提前记录原来size()的值。resize()改变大小void resize(size_t n, T val T()) { if (n size()) { _finish _start n; // 缩小直接移动 _finish } else { reserve(n); // 扩大先确保空间够 while (_finish _start n) { *_finish val; // 填充 _finish; } } }缩小时_finish后移元素被逻辑删除但内存不释放扩大时用val填充新元素默认值T()调用T的默认构造这里的T()既可以是内置类型也可以是自定义类型。push_back和pop_backpush_back()void push_back(const T x) { if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); } *_finish x; _finish; }pop_back()void pop_back() { assert(!empty()); --_finish; }迭代器iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }迭代器的失效问题insert和迭代器失效问题iterator insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); // 扩容 if (_finish _end_of_storage) { size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; // 关键扩容后 pos 失效重新计算 } iterator end _finish - 1; while (end pos) { *(end 1) *end; --end; } *pos x; _finish; return pos; }情况1扩容导致的失效insert 和 push_backvectorint v {1, 2, 3}; auto it v.begin(); // it 指向 1 v.push_back(4); // 如果扩容it 失效 // 此时 it 指向的内存可能已经被释放 // 使用 it → 未定义行为使用push_back()的时候会调用reserve(),会建立一个新的空间但是起初的时候迭代器指向的it是原来的空间这样如果使用itit所指向的空间会被释放掉。错误写法iterator insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); // 扩容 if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); } iterator end _finish - 1; while (end pos) { *(end 1) *end; --end; } *pos x; _finish; return pos; }由于pos是迭代器类型的他的返回值是_start,_finish的成员变量由于在调用insert()的时候调用了reserve()开辟新空间这个时候pos指向原理的空间不存在了就造成了所有迭代器都失效的问题所以这里同理这里先记录了原先容器的大小通过容器的大小记录旧空间pos指向的位置reserve完了之后重新计算他的pos让pos指向新的空间。if (_finish _end_of_storage) { size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; // 关键扩容后 pos 失效重新计算 }情况2移动元素导致的失效insertvectorint v {1, 2, 3, 4}; auto it v.begin() 1; // it 指向 2 v.insert(it, 100); // 插入后it 还指向原来的位置吗 // itv.insert(it, 100); //返回新的迭代器 初始状态容量 8当前 size4 地址: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 0x101C 内容: [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 未用 ] [ 未用 ] [ 未用 ] [ 未用 ] ↑ ↑ ↑ ↑ _start pos end _finish 步骤1end _finish - 1 0x100C指向元素4 while (end pos): *(end 1) *end → 将4拷贝到0x1010 --end → end指向0x1008元素3 步骤2end 0x1008指向元素3 *(0x100C) *0x1008 → 将3拷贝到原4的位置0x100C --end → end指向0x1004元素2 步骤3end 0x1004指向元素2 *(0x1008) *0x1004 → 将2拷贝到原3的位置0x1008 --end → end指向0x1000元素1此时 end pos循环退出 步骤4*pos x → 在0x1004位置写入100 _finish → _finish指向0x1014 最终状态 地址: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 0x101C 内容: [ 1 ] [ 100 ] [ 2 ] [ 3 ] [ 4 ] [ 未用 ] [ 未用 ] [ 未用 ] ↑ ↑ ↑ _start pos _finish通过返回新的迭代器的位置记录新的位置。earse和迭代器失效的问题void erase(iterator pos) { assert(pos _start); assert(pos _finish); iterator it pos 1; while (it ! end()) { *(it - 1) *it; it; } --_finish; } for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) { it v.erase(it); // erase 返回删除后的下一个位置 } else { it; } }vector的嵌套问题——vectorvectorintvectorint v(5, 1); vectorvectorint vv(10, v); // 10 行每行是 v 的拷贝 vv[2][1] 2; // 等价于vv.operator[](2).operator[](1) 2;这里vv的构造调用了vector(size_t n, const T val)其中T vectorint。所以先构造一个vectorint v(5, 1)包含 5 个1。vv(10, v)构造了 10 个vectorint对象每个都是v的深拷贝调用vectorint的拷贝构造。vv[2][1]连续两次调用operator[]。内存布局上外层vv是一个连续数组存了 10 个vectorint对象每个内层vectorint又各自在堆上有一块连续空间存 5 个int。行内连续行间不连续。以上就是我整个在实现vector的时候需要注意的问题后面我会继续补充。