迭代器失效
我们先实现一个简单的vector逻辑
#pragma once #include<assert.h> #include<iostream> namespace bit { template<class 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::vector<int> 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 vector<T>& 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 vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> 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::vector<string> 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 #include<assert.h> #include<iostream> namespace bit { template<class 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 vector<T>& 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 vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> 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; }; }
