[ C++ ] STL---vector的模拟实现

阅读本书更多章节>>>>

目录

vector的成员变量

迭代器的实现

容量相关接口

size()与capacity()

reserve()

   resize()

vector增删查改

push_back()

pop_back()

insert()

erase()

operator[ ]

构造函数

无参构造

n个值为val的元素构造vector

迭代器区间构造

拷贝构造

 赋值运算符重载

析构函数

---

vector的成员变量

vector容器是类模版，可以存储不同数据类型的元素，其迭代器是数据类型的指针；

namespace vec{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private://指向vector容器中首元素位置的指针iterator _start = nullptr;//指向vector容器中尾元素的下一位置的指针iterator _finish = nullptr;//指向vector容器中存储容量的下一位置的指针iterator _endofstorage = nullptr;//成员变量声明处给定缺省值自动传递给初始化列表};}

迭代器的实现

begin()函数返回vector容器首元素的位置，end()返回vector容器尾元素的下一个位置，即迭代器区间左闭右开[begin，end)；

//普通迭代器--可读可写iterator begin(){   return _start;}iterator end(){   return _finish;}//const迭代器--只读const_iterator begin()const{   return _start;}const_iterator end()const{   return _finish;}

容量相关接口

size()与capacity()

指针减指针返回指针之间数据元素的个数

//注:由于const对象不可调用非const成员函数,涉及权限的放大//因此size()与capacity()为const成员函数,保证普通对象与const对象均可调用size_t size()const {   return _finish - _start;}size_t capacity()const{   return _endofstorage - _start;}

reserve()

void reserve(size_t n)
case1: 当n>v.capacity()时,重新分配空间，使得capacity()扩容至n,size()不发生变化；
case2: 当n<v.capacity()时,size()与capacity()均不发生改变；

//vector分配空间的策略:空间已满,异地扩容void reserve(size_t n){    if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start != nullptr){    memcpy(tmp, _start, sizeof(T)*oldsize());}    delete[] _start;_start = tmp;_finish = tmp + oldsize;_endofstorage = tmp + n;}}

若vector容器存储的数据为内置类型，使用memcpy将旧空间的数据拷贝到新空间时，不会导致任何问题；

若vector容器存储的数据为自定义类型，使用memcpy将旧空间的数据拷贝到新空间时，会导致系统崩溃，什么原因导致的呢？

扩容时，tmp指向新开辟的空间，但是memcpy会将_start所指向的空间中的值按照逐字节拷贝的方式拷贝到tmp所指向的空间；

接下来，执行delete[ ] _start；首先会调用string类的析构函数，释放_str所指向的空间，随后会调用vector的析构函数，释放_start所指向的空间，此时新开辟的空间tmp中_str全部变为野指针，导致系统崩溃；

解决方案：

对于vector容器中涉及资源申请的数据实现深拷贝，通过赋值运算符重载函数完成深拷贝；

//vector分配空间的策略:空间已满,异地扩容void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start != nullptr){for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];//注意:此处对于内置类型相当于使用=,对于自定义类型相当于调用其赋值函数重载;}}delete[] _start;_start = tmp;_finish = tmp + oldsize;_endofstorage = tmp + n;}}

   resize()

case1:  当n<size()时，直接删除数据：只需将_finish置为_start+n即可；

case2：当size()<n<capacity()时，只需将剩余的空间初始化：只需从原先的_finish开始依次往后填写缺省值或者指定值直到达到有效数据个数即可；

case3： 当n>capacity()时，需要扩容+初始化：case3只是比case2多了一个扩容操作，将case2与case3统一使用reserve()处理，因为当n<capacity()时，reserve()什么也不做；

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

vector增删查改

push_back()

//尾插void push_back(const T& x){//检查容量    if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;}

pop_back()

void pop_back(){    //检查vector中是否存在可以删除的元素assert(size() > 0);--_finish;}

insert()

使用库中的vector,导致上述现象产生的原因是什么？

reserve()扩容时，开辟新空间，将原空间的数据拷贝至新空间，释放旧空间，此时pos指向一块被释放的空间，pos变成野指针，导致迭代器失效；

解决方案：

内部失效，更新pos位置；

外部失效，采用返回值解决，返回新空间pos位置使得外部可以进行访问；

iterator insert(iterator pos, const T& x){assert(pos <= _finish);//pos == _finish时，相当于尾插 //检查容量,容量已满,异地扩容if (_finish == _endofstorage){size_t n = pos - _start;//计算原空间pos与_start的相对距离size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);//更新pos位置,解决内部迭代器失效pos = _start + n;}//插入之前需要往后挪动1个数据iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}//插入数据*pos = x;++_finish;    return pos;}

erase()

使用库中的vector,导致上述现象产生的原因是什么？

解决方案：

erase()外部失效，采用返回值解决，erase()返回删除元素的下一个位置，外部接收返回值从而更新外部迭代器；

iterator erase(iterator pos){      //检查待删除元素位置的合法性assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){    //将pos位置之后的值从前向后覆盖*(it - 1) = *it;++it;}_finish--;    //当删除的数据被删除，erase原地不动，已自动指向下一位置return pos;}

operator[ ]

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

构造函数

无参构造

vector(){}//声明时三个成员变量给定缺省值，缺省值自动传递给初始化列表，对三个指针已经进行赋空操作

n个值为val的元素构造vector

vector(size_t n, const T& val = T()){   _start=new T[n];   for(size_t i = 0; i < n; i++)   {       *(_start + i)= x;   }    _finish = _endofstorage= _start + n;}

迭代器区间构造

template <class InputIterator>//此模板类型可以接收其他容器的迭代器,迭代器本质为指针或封装过的指针vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);//复用push_back(),尾插元素++first;}}

 解决方案：

利用运算符重载函数，重载为vector(int n, const T& val = T())；

vector(int n, const T& val = T()){resize(n, val);}

拷贝构造

//拷贝构造函数传统写法vector(const vector<T>& v){//开辟空间_start = new T[v.capacity()];//利用赋值运算符,对于内置类型实现浅拷贝,对于自定义类型实现深拷贝;for (size_t i = 0; i < v.size(); i++){    *(_start + i) = *(v._start + i);}_finish = _start + v.size();    _endofstorage = _start + v.capacity();}

//拷贝构造现代写法vector(const vector<T>& v){reserve(v.capacity());for (const auto& e : v){push_back(e);}}

 赋值运算符重载

//细致分析过程见string类的模拟实现void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}// v1 = v2vector<T>& operator=(vector<T> v){swap(v);return *this;}

析构函数

//析构函数~vector(){if (_start != nullptr){delete[] _start;_start = _finish = _endofstorage = nullptr;}}

欢迎大家批评指正，谢谢观看，码字不易，希望大家给个一键三连支持~

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-06/154952.html，文章来源：网络cs，作者：焦糖，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！