vector模拟实现

迭代器失效我们先实现一个简单的vector逻辑#pragma once #includeassert.h #includeiostream ​ namespace bit { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; ​ iterator begin() { return _start; } ​ iterator end() { return _finish; } ​ const_iterator begin() const { return _start; } ​ const_iterator end() const { return _finish; } ​ vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { } ​ ~vector() { if (_start) { delete[] _start; _start _finish _endofstorage nullptr; } } ​ ​ ​ void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start tmp; _finish _start sz; _endofstorage _start n; ​ } } ​ size_t capacity() const { return _endofstorage - _start; } ​ size_t size() const { return _finish - _start; } ​ T operator[](size_t pos) { assert(pos size()); return _start[pos]; } ​ const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; } private: iterator _start; iterator _finish; iterator _endofstorage; }; }迭代器失效1-扩容在此基础上增加push_back和insert​ void push_back(const T x) { //if (_finish _endofstorage) //{ // size_t newcapacity capacity() 0 ? 4 : capacity() * 2; // reserve(newcapacity); //} //*_finish x; //_finish; ​ insert(end(), x); } ​ void insert(iterator pos, const T x) { assert(pos _start pos _finish); ​ if (_finish _endofstorage) { size_t newcapacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapacity); } ​ iterator end _finish - 1; ​ while (end pos) { *(end 1) *end; end--; } ​ *pos x; _finish; }这里push_back在调用insert时就会出现一个典型问题迭代器失效当push_back 调用insert时若需要扩容则会进入reserve()reserve()内部delete[]释放旧数组内存_start指向新地址返回insert后原来的pos位置即旧finish的地址已经指向被释放的内存成为野指针后续再对pos访问会导致未定义行为解决方案在可能引起扩容的操作之前记录迭代器的相对位置偏移量扩容后重新计算新的迭代器。void insert(iterator pos, const T x) { assert(pos _start pos _finish); ​ if (_finish _endofstorage) { size_t offset pos - _start;//记录pos相对位置 size_t newcapacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapacity); ​ pos _start offset;//更新pos } ​ iterator end _finish - 1; ​ while (end pos) { *(end 1) *end; end--; } ​ *pos x; _finish; }此时解决了vector内部的迭代器失效问题但是外部调用时使用insert后迭代器仍可能失效扩容。insert后不要再次使用形参迭代器。C标准库采用了iterator返回值方式来解决iterator insert(iterator pos, const T x) { ​ ... return pos; }迭代器失效2-删除接下来看一个删除的场景void erase(iterator pos) { assert(pos _start pos _finish); ​ iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; }对erase进行调用void test_2() { bit::vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); for (auto e : v1) { cout e ; } cout endl; ​ v1.erase(v1.begin() 4); //erase后迭代器失效vs强制检查访问 auto it v1.begin() 4; v1.erase(it); cout *it endl;//未定义操作 it--;//未定义操作 cout *it endl;//未定义操作 ​ ​ }erase后it仍保留原来的内存地址但这个地址已经不在容器有效范围内it变成悬空迭代器尽管--it后仍能访问容器中的元素但是在标准语义中此时的it已经是失效迭代器对it的任何操作都是未定义行为尽管it可能和容器物理上紧邻。vs中会强制检查erase后的迭代器不允许对其再次访问正确写法是返回迭代器iterator erase(iterator pos) { assert(pos _start pos _finish); ​ iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; return pos; }深浅拷贝拷贝构造与复制拷贝//vector(const vectorT v) // :_start(nullptr) // , _finish(nullptr) // , _endofstorage(nullptr) //{ // _start new T[v.capacity()]; // memcpy(_start, v._start, sizeof(T) * size()); // _finish _start v.size(); // _endofstorage _start v.size(); ​ //} ​ vector(const vectorT v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } ​ void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } ​ vectorT operator(vectorT v) { swap(v); return *this; } ​复制拷贝使用了copy-and-swap的典型实现memcpy的拷贝问题void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size());//memcpy delete[] _start; } _start tmp; _finish _start sz; _endofstorage _start n; ​ } } ​ void test_4() { bit::vectorstring v; v.push_back(111111); v.push_back(222222); v.push_back(333333); v.push_back(444444); v.push_back(555555); ​ for (auto e : v) { cout e ; } cout endl; ​ }如果扩容采用memcpy此时新内存tmp与原指针指向同一块地址空间delete[]后旧内存被释放源string被析构此时tmp的string对象指针变成了悬空指针当再次对vector析构时会导致对同一块内存二次释放程序崩溃。事实上memcpy只是对源内存区域的数据原封不动复制到目标区域逐字节拷贝对于内置类型没有问题但无法处理自定义类型改进方案void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size()); //memcpy逐字节拷贝无法处理自定义类型 ​ for (size_t i 0; i size(); i) { tmp[i] _start[i]; } ​ delete[] _start; } _start tmp; _finish _start sz; _endofstorage _start n; ​ } }调用赋值运算符重载实现对string的深拷贝完整实现#pragma once #includeassert.h #includeiostream ​ namespace bit { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; ​ ​ iterator begin() { return _start; } ​ iterator end() { return _finish; } ​ const_iterator begin() const { return _start; } ​ const_iterator end() const { return _finish; } ​ vector(size_t n, const T val T()) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { resize(n, val); } ​ vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { } ​ ~vector() { if (_start) { delete[] _start; _start _finish _endofstorage nullptr; } } ​ //vector(const vectorT v) // :_start(nullptr) // , _finish(nullptr) // , _endofstorage(nullptr) //{ // _start new T[v.capacity()]; // memcpy(_start, v._start, sizeof(T) * size()); // _finish _start v.size(); // _endofstorage _start v.size(); ​ //} ​ vector(const vectorT v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } ​ void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } ​ vectorT operator(vectorT v) { swap(v); return *this; } ​ void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size());//memcpy逐字节拷贝无法处理自定义类型 ​ for (size_t i 0; i size(); i) { tmp[i] _start[i]; } ​ delete[] _start; } _start tmp; _finish _start sz; _endofstorage _start n; ​ } } ​ size_t capacity() const { return _endofstorage - _start; } ​ size_t size() const { return _finish - _start; } ​ T operator[](size_t pos) { assert(pos size()); return _start[pos]; } ​ const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; } ​ void pop_back() { erase(--end()); } ​ void resize(size_t n, const T val T()) { if (n size()) { _finish _start n; } else { reserve(n); while (_finish ! _start n) { *_finish val; _finish; } } } ​ void push_back(const T x) { //if (_finish _endofstorage) //{ // size_t newcapacity capacity() 0 ? 4 : capacity() * 2; // reserve(newcapacity); //} //*_finish x; //_finish; ​ auto it insert(end(), x); } ​ iterator insert(iterator pos, const T x) { assert(pos _start pos _finish); ​ if (_finish _endofstorage) { size_t offset pos - _start; size_t newcapacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapacity); ​ pos _start offset; } ​ iterator end _finish - 1; ​ while (end pos) { *(end 1) *end; end--; } ​ *pos x; _finish; return pos; } ​ iterator erase(iterator pos) { assert(pos _start pos _finish); ​ iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; return pos; } ​ private: iterator _start; iterator _finish; iterator _endofstorage; }; }