编程语言
453
一、vector的注意事项
1. [] 和 at() 的越界访问
vector<int> v1{ 1,2,3,4 }; //v1[4] = 5; //越界直接结束,assert判断 try { v1.at(4) = 5; //抛异常 } catch (...) { cout << "beyond" << endl; //输出beyond }
2.迭代器失效问题
简单来说就是在迭代器创建后 使用了reverse,resize,insert,push_back等导致的增容 导致迭代器仍然指向已经被释放的旧空间
一个应对迭代器失效的过程
//删除容器中所有的偶数 vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.erase(it); } //然后该怎么++it? ++it; //此时会报错,为什么? //erase删除一个数据后,其他数据向前移动,移动后其实it已经指向我们想要遍历的下一个元素 //此时再++it就会导致错过部分数据 else { ++it; //那么这样处理可以么? //Linux环境下这样可以达到目的,但是vs编译环境自动检查且较为严格,仍然报错 } } //正确做法 vector<int>::iterator it2 = v.begin(); while (it2 != v.end()) { if (*it2 % 2 == 0) it2 = v.erase(it2); //正确做法 erase会返回删除的it的下一个位置的迭代器 else ++it2; }
二、vector的模拟实现
有以下要点:
reserve中浅拷贝memmove问题 新型拷贝构造和重载赋值符写法 insert时的迭代器失效
namespace 9TSe { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) {} //v2(v1) //vector(const vector<T>& v) //{ // _start = new T[v.capacity()]; //开辟新空间 // _finish = _start; // _endofstorage = _start + capacity(); // for (size_t i = 0; i < v.size(); ++i) // { // *_finish = v[i]; // ++_finish; // } //} //拷贝构造的另一种方法 vector(const vector<T>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { for (auto& e : v) { reserve(v.capacity()); push_back(e); } } //vector<T>& operator=(const vector<T>& v) //{ // if (*this != &v) //防止自己赋值给自己 // { // delete[] _start; //s1 = s2 s1有自己的空间,先释放 // _start = new T[v.capacity()]; // memcpy(_start, v._start, sizeof(T) * v.size()); // } // return *this; //} //重载赋值运算符简便写法 void swap(vector<T>& v) { ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> v) { if (*this != &v) swap(v); //这里不用库内自带的swap是因为,其会生成三个深拷贝,有很大的代价 return *this; } ~vector() { 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) //这里的用意是防止_start为空指针时扩容,会导致memcpy出错(memcpy内不能存在空指针) { //memcpy(tmp, _start, sizeof(T) * size()); //这个memcpy是浅拷贝,当T为string时,会导致指针指向同一位置,释放两次同一空间 for (size_t i = 0; i < sz; ++i) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = tmp + sz; //如果这里赋予 tmp + size() 会出错 //sz的计算方式是_finish-_start //_start已经指向新空间了,finish还指向旧空间 _endofstorage = tmp + n;//这里如果赋予tmp + capacity() 也会出错,与上同理 } } void resize(size_t n, const T& v = T()) //这里的T()为T类型的默认缺省值,有int() double() 等都有 //int() double()等内置类型,只是专门创建了此形式的东西 //string ,vector 是调用构造函数 { if (n < size()) //缩容 { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish < _start + n) { *_finish = v; ++_finish; } } } void push_back(const T& x) { if (_finish == _endofstorage) //扩容 { size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; } void insert(iterator pos, const T& v) //这里会有迭代器失效问题 { assert(pos <= _finish); if (_finish == _endofstorage)//pos会扩容后失效 { size_t n = pos - _start; //因此要记录之间的距离,以明确新pos指针指向的位置 size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2; reserve(newcapacity); pos = _start + n; //设置新pos } iterator end = _finish - 1; while (end >= pos) //移动数据 { *(end + 1) = *end; end--; } *pos = v; ++_finish; } iterator erase(iterator pos) { assert(pos < _finish&& _start != _finish); iterator it = pos; while (it < _finish) { *it = *(it + 1); ++it; } _finish--; return pos; } size_t size()const { return _finish - _start; } size_t capacity()const { return _endofstorage - _start; } iterator end() { return _finish; } iterator begin() { return _start; } const_iterator end()const { return _finish; } const_iterator begin()const { return _start; } T& operator[](size_t i) { assert(i < size()); return *(_start + i); } const T& operator[](size_t i)const { assert(i < size()); return *(_start + i); } void pop_back() { assert(_start < _finish); _finish--; } private: iterator _start; iterator _finish; //这个指针指向的是最后一个数据的下一个数据的位置 iterator _endofstorage; }; }
