(C++ STL) 详解vector模拟实现
目录
一.vector的介绍
1.vector的介绍
二.vector的定义模拟实现
三.vector各接口的模拟实现
1.vector迭代器的模拟实现
2.构造函数
2.1无参构造
2.2 n个val构造
2.3迭代器区间构造
2.4通过对象初始化（拷贝构造）
3.析构函数
4.size
5.operator=
6.capacity
7.reserve
8.resize
9.operator[ ]
10.insert
11.push_back
12.erase
13.pop_back
14.empty
一.vector的介绍
1.vector的介绍
这是官方的文档介绍
cplusplus.com/reference/vector/vector/
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好
二.vector的定义模拟实现
首先我们先 定义一个命名空间 来模拟实现咱们的vector类
类里面有三个私有 指针变量 分别指向数据块的开始，尾和存储容量的尾
namespace zyl
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}三.vector各接口的模拟实现
1.vector迭代器的模拟实现
vector的迭代器分为俩种
一种是普通迭代器 指向的内容可以被修改
一种是const迭代器 不可以修改只可读
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}2.构造函数
vector 的四种构造函数
2.1无参构造
主要是对各个指针初始化 赋值为空
vector():_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){}2.2 n个val构造
直接向数组中尾插数据，用reserve提前扩容, 提高效率
然后需要注意的是 这里传参的第二个参数使用匿名对象，const T& val = T() 这种写法会调用默认构造(可以是任意类型)，我们前面讲内置类型是没有默认构造函数的, 理论而言是没有的, 但是调用模板之后必须要支持默认构造
vector(int n, const T& value = T()):_endOfStorage(nullptr), _start(nullptr), _finish(nullptr){reserve(n);//提前开n个空间for (int i = 0;i < n;i++){push_back(value);//缺省值默认为val；}}2.3迭代器区间构造
这里又要使用模板实现， 要实现一个任意类型的迭代器允许任意类型的数据使用，直接用迭代器遍历数组, 尾插数据即可
template<class InputIterator>vector(InputIterator first, InputIterator last):_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){while (first != last){push_back(*first);++first;}
2.4通过对象初始化（拷贝构造）
通过传一个vector对象 然后进行交换
vector(const vector<T>& v){vector<T> tmp(v.cbegin(), v.cend());swap(tmp);}3.析构函数
析构函数的主要功能 释放掉所有数据 然后三个指针指向空
~vector(){delete[]_start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}4.size
返回当前vector长度
size_t size() const{return _finish - _start;}5.operator=
运算符重载= 实现深拷贝 把v对象赋给this
vector<T>& operator= (vector<T> v){if (this != &v){delete[] _start;_start = new T[v.capacity()];for (size_t i = 0;i < v.size();i++){_start[i] = v[i];}_finish = _start + v.size();_endOfStorage = _start + v.capacity();}return *this;}6.capacity
返回当前vector对象的容量是多少
size_t capacity() const{return _endOfStorage - _start;}7.reserve
在n>capacity时去进行扩容 是为了防止程序缩容
判段当前数据是为为空，需不需要旧数据的拷贝转移
遍历的时候，一定要使用深拷贝，不要使用memcpy去进行拷贝
void reserve(size_t n){if (n >capacity()){size_t sz = size();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;_endOfStorage = _start + n;}}8.resize
n < size()就是删除数据，直接改变 _finish的指向即可
n > capacity()调用reserve函数扩容， 后遍历给数组赋值
void resize(size_t n, const T& value = T()){//查看是否需要扩容if (n > capacity()){reserve(n);}if (n > size()){while (_finish > _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}9.operator[ ]
vector也支持下标访问
重载 [ ] 可以快速的对数据进行访问
T& operator[](size_t pos){assert(pos < size());return _start[pos];}10.insert
检查容量，观察是否需要扩容, 扩容前计算出pos与start之间，pos与start之间相对距离不变，扩容后更新pos位置(这里存在迭代器失效的问题)
遍历挪动数据
将val插入pos位置
注意: 检查pos位置的合法性
iterator insert(iterator pos, const T& x){//pos范围必须在_start和_finish之间assert(pos>=_start);assert(pos <= _finish);//内存满了 进行扩容if (_finish == _endOfStorage){size_t len = pos - _start;reseve(capacity() > 0 ? 4 : capacity * 2);pos = _start + len;}iterator end = _finish;//移动数据 进行插入while (end >= pos){*end = *(end - 1);end--;}*pos = x;++_finish;return pos;}11.push_back
尾插 直接调用insert 在_finish位置去插入
void push_back(const T& x){insert(_finish, x);}12.erase
erase函数可以删除所给迭代器pos位置的数据
在删除数据前需要判断容器释放为空
若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可。
iterator erase(iterator pos){//判断pos是否合法assert(pos > _finish);assert(pos < _start);assert(!empty());iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}13.pop_back
pop_back直接调用erase去_finish位置进行删除
void pop_back(){erase(_finish);}14.empty
进行判空 直接看_finish == _start是否相同就可以了
bool empty() const{return _finish == _start;}