(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;}