阅读量:0
✨✨ 欢迎大家来到贝蒂大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++学习
贝蒂的主页：Betty’s blog
为了让我们更加深入理解vector，接下来我们将模拟实现一个·简易版的vector。而为了和STL库中的vecotr以示区分，我们将使用命名空间namespace对其封装。
1. vector的成员变量
vector的底层其实就是我们之前在数据结构学习的顺序表，但是与顺序表不同的是vector的成员变量是三个迭代器，也可以说是三个指针。
下面是vector的成员变量：
namespace betty { template<class T> class vector { public: //... private: iterator _start; iterator _finish; iterator _end_of_storage; }; } 其中start指向起始位置，_finish指向有效数据末尾的后一个位置，最后_end_of_storage指向容量大小末尾的后一个位置。
2. vector的成员函数
在知道vector的成员变量之后，接下来我们将探究vector的成员函数，而常见成员函数的用法我们早在之前就已经介绍过了 ，下面我们将来具体实现一下：
2.1. vector的迭代器
首先我们来模拟实现一下迭代器iterator，而在vector中迭代器iterator与string中的迭代器类似就是一个指针。所以我们直接使用typedef实现
typedef char* iterator;//普通迭代器 typedef const char* const_iterator;//const迭代器 接下来我们来实现begin()与end()，其中begin()指向的是数组的起始位置即_start，而end指向有效长度最后的下一位即_finish的位置。
iterator begin() { return _start; } iterator end() { return _finish; } 实现完普通迭代器之后，我们可以顺便重载一个const_iterator的版本。
const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } 我们知道在vector中还有一个反向迭代器，这个我们在之后会统一实现。
2.2. vector的初始化与销毁
2.2.1. 构造函数与拷贝构造
我们之前在学习vector时知道其初始化方式有很多，可以通过默认构造函数给其初始化，n个val初始化，也可以通过迭代器初始化。
首先我们写一个默认构造函数，将其所有变量都设为空。
vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) { ; } 接下来我们来实现迭代器初始化，而因为我们可以通过其他容器的迭代器对其初始化，所以要通过模版来实现。
template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } 最后我们来实现n个val初始化。
vector(size_t n, const T& val = T()) { resize(n, val); } vector(int n, const T& val = T()) { resize(n, val); } 至于为什么要同时重载int与size_t两种不同类型，那是为了防止在传两个int类型的参数时被编译器交给模版InputIterator识别，然后报错。
拷贝构造也十分简单，直接拷贝就行，但是也有一些注意事项。
vector(const vector<T>& v) { _start = new T[v.capacity()];//开辟capacity的空间 for (size_t i = 0; i < v.size(); ++i) { _start[i] = v._start[i];//进行深拷贝 } _finish = _start + v.size();//更新_finish _end_of_storage = _start + v.capacity();//更新_end_of_storage } 这里注意不能利用memcpy()等库函数进行拷贝，因为这些函数都是进行的浅拷贝。如果模版参数T是string，vector等自定义类型，当程序结束回收内存时就会发生内存错误。
当然我们也可以通过一个取巧的方式来实现拷贝构造。
vector(vector<int>& v) { // 根据v的capacity()去开出对应的空间 reserve(v.capacity()); //进行深拷贝 for (size_t i = 0; i < v.size(); i++) { push_back(v[i]); } } 首先通过构造出一个与数组相同的数组v，然后让this所指向的数组与其交换，这样出了作用域之后销毁的就是原this所指向的数组。当然我们必须先将this所指向的数组先初始化扩容。
2.2.2. 赋值重载与析构函数
赋值运算符重载与拷贝构造的实现就非常类似了，直接实现即可。
vector<T> operator = (vector<T> v) { swap(v); return *this; } 最后我们实现析构函数，只需要清理资源即可
~vector() { delete[]_start; _start = _finish = _end_of_storage = nullptr; } 2.3. vector的容量操作
2.3.1. 有效长度与容量大小
首先我们先实现返回数组有效长度的size() 与容量大小的capacity()。并且为了适配const对象，最后用const修饰this指针。
size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } 2.3.2. 容量操作
接下来我们来实现扩容函数reserve()与·resize()，其中reserve()最简单，只要新容量大于旧容量就发生扩容，其中注意需要提前记录size大小，防止数组异地扩容原数组释放之后找不到原数组大小。
void reserve(size_t n) { //提前原本记录长度 size_t sz = size(); if (n > capacity()) { T* tmp = new T[n]; if (_start) { //深拷贝 for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i];//赋值重载 } delete[]_start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } 而resize()的逻辑就比较复杂，需要分三种情况讨论。设字符串原来有效长度为size，容量为capacity，新容量为n
- 当
n<size时，resize会删除有效字符到指定大小。- 当
size<n<capcity时，resize会补充有效字符(默认为0)到指定大小。- 当
n>capacity时，resize会补充有效字符(默认为0)到指定大小。
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; } } } 2.4. vector的访问操作
为了符合我们C语言访问数组的习惯，我们可以先重载operator[]。当然我们也要提供两种不同的接口：可读可写与可读不可写。并且使用引用返回，减少不必要的拷贝。
// 可读可写 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } // 可读不可写 T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } 同理我们也可以实现front()与back()函数。
// 可读可写 char& front() { return _start[0]; } char& back() { return _start[_size() - 1]; } // 可读不可写 const char& front()const { return _start[0]; } const char& back()const { return _start[_size() - 1]; } 2.5. vector的修改操作
2.5.1. 常见的修改操作
首先我们将实现两个常用的修改函数：push_back()与pop_back()。
void push_back(const T& x) { //判断是否扩容 if (_finish == _end_of_storage) { size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newCapacity); } *_finish = x; ++_finish; } void pop_back() { --_finish; } 随后我们来实现数组的交换swap()函数，我们知道vector的交换其实就是指针_start，_finish，_end_of_storage的交换。
void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } 
2.5.2. 迭代器失效
接下来我们实现insert()与erase()两个函数。其中insert()在插入时可能扩容，这时就需要记录起始长度，方便更新迭代器返回。
iterator insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); //检查是否扩容 if (_finish == _end_of_storage) { //先记录长度 size_t len = pos - _start; size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); //更新迭代器指向新空间 pos = _start + len; } //往后覆盖 iterator end = _finish; while (end > pos) { *end = *(end - 1); --end; } *pos = x; ++_finish; return pos; } 同样的为了防止迭代器失效，需要返回新的迭代器。
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; ++end; } --_finish; return pos; } 3. 源码
#pragma once namespace betty { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) { ; } vector(size_t n, const T& val = T()) { resize(n, val); } vector(int n, const T& val = T()) { resize(n, val); } template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } //vector(const vector<T>& v) //{ // _start = new T[v.capacity()];//开辟capacity的空间 // for (size_t i = 0; i < v.size(); ++i) // { // _start[i] = v._start[i];//循环拷贝 // } // _finish = _start + v.size();//更新_finish // _end_of_storage = _start + v.capacity();//更新_end_of_storage //} vector(vector<int>& v) { // 根据v的capacity()去开出对应的空间 reserve(v.capacity()); //进行深拷贝 for (size_t i = 0; i < v.size(); i++) { push_back(v[i]); } } vector<T> operator=(vector<T> v) { swap(v); return *this; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void reserve(size_t n) { //提前原本记录长度 size_t sz = size(); if (n > capacity()) { T* tmp = new T[n]; if (_start) { //深拷贝 for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i];//赋值重载 } delete[]_start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } void push_back(const T& x) { //判断是否扩容 if (_finish == _end_of_storage) { size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newCapacity); } *_finish = x; ++_finish; } 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; } } } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } iterator insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); //检查是否扩容 if (_finish == _end_of_storage) { //先记录长度 size_t len = pos - _start; size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); //更新迭代器指向新空间 pos = _start + len; } //往后覆盖 iterator end = _finish; while (end > pos) { *end = *(end - 1); --end; } *pos = x; ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; ++end; } --_finish; return pos; } void pop_back() { --_finish; } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } ~vector() { delete[]_start; _start = _finish = _end_of_storage = nullptr; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; } ase(iterator pos) { assert(pos >= _start && pos < _finish); iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; ++end; } --_finish; return pos; } void pop_back() { --_finish; } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } ~vector() { delete[]_start; _start = _finish = _end_of_storage = nullptr; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; } 