STL讲解——模拟实现vector

STL讲解——模拟实现vector

vector深度剖析

在STL源码中，发现vector定义的并不是 start、size、capacity，而是start、finish、end_of_storage.
这样就可以得到size()和capacity()。
size=finish-start
capacity=end_of_storage-start
扩容可能是本地扩容也可能是异地扩容，但大约是扩容1.5倍-2倍（vs是扩容1.5倍，g++是2倍）

设计一个框架

namespace tom
{template<class T>class vector{public:vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//一个类模板的成员函数，又可以是一个函数模板（套娃，可以在模板类里面再上增加模板类）~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

这里设计的构造函数和拷贝构造一定要初始化列表（把所有的成员都初始称nullptr），不初始化的话就是随机地址这样没法正常赋值和析构。
析构函数一定要用delete[ ] start；不要忘记‘[ ]’

查一下std::vector的构造函数有哪些。发现有迭代器实现的，可以初始化的，还有拷贝构造。

我们也添加一下

namespace tom
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr), _finish(NULL), _endofstorage(NULL){}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);}}//一个类模板的成员函数，又可以是一个函数模板（套娃，可以在模板类里面再上增加模板类）template <class InputIterator>vector<T>(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);++first;}}void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//vector(const vector& v) 这样写也可以的vector<T>(const vector<T>& v)//回顾一下，拷贝构造和复制构造不用加<T>.:_start(nullptr)//一定要初始化，不然会给随机值，析构随机地址会报错的, _finish(nullptr), _endofstorage(nullptr){_start = new T[v.capacity()];//经典写法_finish = _start + v.size();_endofstorage = _start + v.capacity();memcpy(_start, v._start, v.size() * sizeof(T));}//vector& operator=(vector v)vector<T>& operator=(vector<T> v)//推荐写这个，好理解{swap(v);return *this;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

还设计了size（）与capacity（）。

注意：

1、构造函数重载是如果只有一个vector(size_t n, const T& val = T()) 和 vector(InputIterator first, InputIterator last)是不行的，比如vector v1(16,5);时这该怎么办？调用哪一个呢？编译器会直接调用迭代器调用的，因为构造函数的两个参数的类型完全一致。这个时候我们要再重载一个vector(int n, const T& val = T())的就不会出现这种情况了。
2、可以在模板类里面再上增加模板类，一个类模板的成员函数，又可以是一个函数模板。
3、我们要写一个赋值构造就需要运算符重载一下 ‘=’ 不然会出现浅拷贝（自定义类型涉及到资源开辟就会析构报错）。
4、还可以用拷贝构造，复制构造可以用现代写法，因此我们也要重载一个内部 swap( )函数，可以减少三次深拷贝。

增、删、查、改

迭代器

		iterator begin(){return _start;}const_iterator end() const{return _finish;}const_iterator begin() const{return _start;}iterator end(){return _finish;}

有了迭代器就方便后面的循环与增删查改了

void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];int old_size=size();if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;++_finish;}}}void push_back(const T& x){if (_finish == _endofstorage){size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);}*_finish = x;_finish++;}void pop_back(){if (_start < _finish){--_finish;}}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish==_endofstorage)//必须这么写，不然会pos迭代器失效{size_t len = pos - _start;reserve(capacity()==0?4:capacity()*2);pos = _start + len;}iterator end = _finish;//必须写在扩容后面，因为另开辟空间，会更改finishwhile (end > pos){*(end) = *(end-1); --end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos)//会引发迭代器失效{assert(pos >= _start);assert(pos <= _finish);iterator start = pos+1;iterator end = _finish;while (start < end){*(start - 1) = *start;++start;}--_finish;return pos;}

增

第一个问题就是扩容问题：
设计一个resize（），在设计一个reserve（）函数进行扩容，第一个可以扩容+初始化，第二个只是单纯扩容。
在这里用的是memcpy进行拷贝。扩容的时候要记得记录一下原来的size大小，如果原地扩容还好，异地扩容就会有天然之别，换了换了所有的地址，这时候start、finish、endofstorage都要更改.
resize可以复用一下reserve函数，然后再初始化赋值。
接下来就是设计push_back()、insert(pos,x)函数，先判断是否超出capacity，如果超出就进行扩容（1.5-2倍）。

void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];int old_size=size();if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}}

insert（）函数先检查容量，容量不够扩容，再移动数据，如果空间足够直接移动数据。但是要记得一件事，有可能会出现迭代器失效的。

插入时时迭代器失效

int a[] = { 1, 2, 3, 4 };
tom::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));// 删除pos位置的数据，导致pos迭代器失效auto pos = find(v.begin(), v.end(), 3);v.erase(pos);cout << *pos << endl; // 此处会导致非法访问pos = find(v.begin(), v.end(), 3);v.insert(pos, 30);cout << *pos << endl; // 此处会导致非法访问

在pos位置插入数据，导致pos迭代器失效。
insert会导致迭代器失效，是因为insert可
能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。
于是乎pos变成了野指针，无法在pos处插入数据。
要随时更新pos的位置，先设置一个变量len记录pos到start的距离，最后再将pos更新，返回值设为pos就好。

删

删除也会出现迭代器失效问题

int a[] = { 1, 2, 3, 4 };
tom::vector<int> v(a, a + sizeof(a) / sizeof(a[0]))
// 实现删除v中的所有偶数
// 下面的程序会崩溃掉，如果是偶数，erase导致it失效
// 对失效的迭代器进行++it，会导致程序崩溃auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}

以上的函数就会出现问题甚至崩溃：有两个连续的偶数时就会出现漏删，当有偶数结尾时就会出现崩溃。

it(pos每次都会++)，是偶数时finish每次–，这样最后pos超过了finish就会失效，一直跑下去知道崩溃，那可不可以用pos<finish呢？还是不行，这是为了以后和list的迭代器用法统一，以为listNode没法比较地址大小。
要怎么修改呢，第一要实时更新pos，第二要控制pos++（遇到偶数不加，奇数就++）；

it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}

memcpy拷贝的局限

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;
}

问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且
   自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
   
   
   
   结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是 浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

修改代码

因为讲了memcpy只能进行浅拷贝，我用vector时是没什么问题的，可是vector就会出现很严重的问题，会引发析构报错。
这时我们要运算符重载一下‘=’
赋值构造就用现代写法

vector<T>& operator=(vector<T> v)//推荐写这个，好理解{swap(v);return *this;}

reserve()需要修改,扩容就一步一步拷贝。

void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (_start){for (int i = 0; i < size(); i++){*(tmp + i) = _start[i];}delete[] _start;}_finish = tmp + size();//先定义finish，不要换顺序_start = tmp;_endofstorage = _start + n;}}

resize()复用reserve的不用改，修改代码也不能用memcpy，直接一个一个赋值拷过去。

void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;++_finish;}}}

就解决了浅拷贝的问题了。不管是插入还是删除都不能用memcpy（）都要用赋值拷贝一个一个传。

拷贝构造也要改造一下：

vector<T>(const vector<T>& v)//回顾一下，拷贝构造和复制构造不用加<T>.:_start(nullptr)//一定要初始化，不然会给随机值，析构随机地址会报错的, _finish(nullptr), _endofstorage(nullptr){/*_start = new T[v.capacity()];//经典写法_finish = _start + v.size();_endofstorage = _start + v.capacity();memcpy(_start, v._start, v.size() * sizeof(T));*/ //memcpy是一种浅拷贝（vector<string> 就死定了），不能用/*for (size_t i = 0; i < v.size(); i++)//用这个就可以深拷贝了{_start[i] = v._start[i];}*/vector<T> tmp(v.begin(), v.end());//现代写法swap(tmp);}

增加细节

vector还有一个运算符重载‘[ ]’
这个很重要

T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}

还要设计一个const类型的。
反向迭代器就到list我们再细讲