泰安网站开发,google广告投放技巧,建网站的手机软件,建设一个网站首先需要vector 引言#xff08;实现概述#xff09;接口实现详解默认成员函数构造函数析构函数赋值重载 迭代器容量size与capacityreserveresizeempty 元素访问数据修改inserterasepush_back与pop_backswap 模拟实现源码概览总结 引言#xff08;实现概述#xff09;
在前面… vector 引言实现概述接口实现详解默认成员函数构造函数析构函数赋值重载 迭代器容量size与capacityreserveresizeempty 元素访问数据修改inserterasepush_back与pop_backswap 模拟实现源码概览总结 引言实现概述
在前面我们介绍了vector的使用 戳我康vector介绍与使用
在本篇文章中将重点介绍vector的接口实现通过模拟实现可以更深入的理解与使用vector。
我们可以在网上搜索到vector的实现源码 与string中使用一个指针指向存储数据的空间两个整型来刻画size与capacity不同vector中是通过三个迭代器 _start、_finish、_endOfStorage分别指向数据块的起始位置、有效数据末尾的下一个位置、存储容量末尾的下一个位置来管理数据的。vector中迭代器就是原生指针本质上就是使用三个指针来管理动态申请的存储数据的空间。 vector是一个类模板其声明与定义不能分离。我们将模拟实现的vector放在我们创建的命名空间内以防止与库发生命名冲突。
在vector的模拟实现中我们只实现一些主要的接口包括默认成员函数、迭代器、容量、元素访问与数据修改
接口实现详解
默认成员函数
构造函数
构造函数的模拟实现包括无参构造、n个指定元素构造、迭代器区间构造与拷贝构造
无参构造即首先在初始化列表中将三个属性全部初始化为空指针即可 vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}n个指定元素构造
这个重载版本有两个参数第一个是int第二个是const T表示用n个value构造vector第二个参数缺省值为其默认构造T()
首先new一块大小为n个元素大小的空间将其赋值给_start 然后_finish的值就是_start n _endOfStorage的值与_finish相同 最后for循环将n个value写入空间中 vector(int n, const T value T()) //{_start new T[n];_finish _start n;_endOfStorage _finish;for (int i 0; i n; i){*(_start i) value;}}迭代器区间构造
使用迭代器区间的构造是一个函数模板即可以使用其他容器的迭代器区间来构造vector。
这个重载版本的实现有许多方式这里的实现是偷懒版本的即首先将三个属性初始化为空指针后再复用push_back后面实现来将迭代器区间中的元素尾插到新vector中 templateclass InputIteratorvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first last){push_back(*first);first;}}拷贝构造
拷贝构造时首先将三个属性都初始化为空指针 然后使用reserve后面会实现将新vector扩容与原vector一致 最后循环将原vector中的数据拷贝到新vector中即可 vector(const vectorT v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){int sz v.size();reserve(sz);for (int i 0; i sz; i){*(_start i) v[i];}}析构函数
析构函数即释放动态申请的资源即delete[] _start即可同时可以顺便将三个属性均置空 ~vector(){if (_start ! nullptr){delete[] _start;_start _finish _endOfStorage nullptr;}}赋值重载
在实现赋值运算符重载时存在深浅拷贝的问题为了简便我们使用现代版本
现代版本的参数类型为vectorT而不是引用这就使得vector对象在传参时会生成一个临时对象我们将这个临时对象与要替换的对象*this互换就实现了将一个对象赋值到了*this最后返回*this即可临时对象会在函数栈帧销毁时析构swap后面实现。 vectorT operator (vectorT v){swap(v);return *this;}迭代器
vector的迭代器本质上就是原生指针所以我们只需要将T* 重命名为iterator即可实现迭代器并且具有原生指针的、--、、-、指针相减等的属性 typedef T* iterator;typedef const T* const_iterator;与string部分相同我们暂时只实现begin与end关于反向迭代器的实现在后面会详细介绍。 begin返回首元素的地址end返回尾元素下一个位置的地址他们分别重载有const版本 iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}容量
size与capacity
之前讲到vector迭代器的底层是原生指针支持指针减指针的操作。 对于size即元素的个数_finish - _start的值即空间中数据的末尾的下一个位置的指针减首元素位置的指针即元素个数 对于capacity即容量的大小_endOfStorage - _start的值即空间末尾下一个位置的指针减首元素位置的指针即容量大小 size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}reserve
reserve用于扩容 对于C而言使用new扩容时必须进行重新开辟空间将原空间中的元素转移至新空间最后释放原空间的操作。这样的过程将是十分影响效率的
在库实现中当传参的n大于原容量时reserve会实现扩容小于原容量时reserve不进行缩容操作。所以我们模拟实现时先判断n是否大于原容量当大于原容量时在再进行后续操作 首先new一块大小为n个元素大小的空间 然后就需要挪动数据需要注意的是不能使用memcpy来拷贝数据到新空间中因为memcpy是逐字节拷贝而自定义类型是会有动态申请的资源的这样在释放原空间时就会使新空间中的属性为野指针当生命周期结束时释放资源时就会释放野指针从而崩溃。所以我们需要调用operator逐一拷贝数据到新空间中并释放原空间 最后令_start指向新空间的首元素_finish指向数据的结尾可以在释放前记录size的值此时加上即可_endOfStorage指向空间的结尾即_start n void reserve(size_t n){if (n capacity()){T* temp new T[n];int sz size();if (sz ! 0){ //当T为自定义类型时memcpy为浅拷贝temp中的自定义类型的数据与*this是相同的delete调析构释放原空间就会使temp中数据为野指针//memcpy(temp, cbegin(), sizeof(T) * size()); for (size_t i 0; i size(); i){*(temp i) *(_start i);}delete[] _start;}_start temp;_finish _start sz;_endOfStorage _start n;}}resize
resize用于改变元素个数 当n小于元素个数时删除多于的元素n大于元素个数时使用指定的元素value补足value为缺省参数缺省值为T()
首先判断n是否大于元素个数当大于元素个数时还需要进一步判断n是否大于容量需要扩容 之后逐一用value补足这里同样需要是用operator来避免浅拷贝带来的问题并调整_finish的指向 当小于元素个数时直接将_finish的值调整为_start n即可 void resize(size_t n, const T value T()){if (n size()){if (n capacity()){reserve(n);}int oldSize size();_finish _start n;for (size_t i oldSize; i n; i){*(_start i) value;}}else{_finish _start n;}}empty
empty用于判断vector是否为空为空返回true否则返回false。这里复用size即可当size返回0时即为空 bool empty(){if (size() 0){return true;}return false;}元素访问
元素访问即实现operator[]可以实现通过下标访问元素 有两个重载版本即普通对象与const对象。
首先判断pos是否越界因为pos为无符号整型所以只需要判断_start pos 是否小于 _finish即可 然后直接返回_start pos的解引用即可 T operator[](size_t pos){assert(_start pos _finish);return *(_start pos);}const T operator[](size_t pos) const{assert(_start pos _finish);return *(_start pos);}数据修改
insert
insert用于在pos位置插入数据模拟实现insert时我们只实现在pos位置迭代器插入一个元素的情况
首先判断pos是否越界没有越界时还需要再判断是否需要扩容 这里就存在一个问题在上一篇文章提到了迭代器失效的问题扩容后指向原来空间的迭代器pos就会成为野指针而失效。为解决这个问题我们可以事先计算pos对于_start的相对位置sz从而在释放原空间后通过这个相对位置在新空间中重新找到pos即_start sz 然后就可以循环将pos位置及以后的元素逐一向后移动一个元素。这个过程是十分影响效率的 最后将要插入的元素放在pos位置并_finish iterator insert(iterator pos, const T x) //pos传参在reserve后会出现迭代器失效{assert(pos _start pos _finish);int sz pos - _start; if (size() capacity()){reserve(capacity() 0 ? 10 : capacity() * 2);pos _start sz; //解决迭代器失效}vectorT::iterator it end() - 1;while (it pos){*(it 1) *it;--it;}*pos x;_finish;return _start;}erase
erase用于删除一段数据这里只模拟实现删除pos位置迭代器的一个元素
首先判断pos是否越界如果没有越界再判断容器是否为空为空就直接返回_start 然后循环将pos后面的元素逐一向前移动一个元素从后向前覆盖 最后--_finish并返回_start iterator erase(iterator pos){assert(pos _start pos _finish);if (empty()){return _start;}vectorT::iterator it pos 1;while (it _endOfStorage){*(it - 1) *it;it;}--_finish;return _start;}push_back与pop_back
由于在任意位置插入与删除十分影响效率头插与头删更甚所以库中只提供了尾插与尾删的接口不用挪动数据使得其效率很高
模拟实现时其实只需要调用上面实现的insert与erase即可 push_back即在end()的位置插入一个元素x pop_back即在end() - 1的位置删除一个元素 void push_back(const T x){insert(end(), x);}void pop_back(){erase(end() - 1);}swap
swap函数用于交换两个对象的数据
使用算法库中的swap通过创建临时变量交换的话就会发生多次深拷贝十分影响效率。 对于vector对象的交换只需要逐一交换他们的三个属性即可 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}模拟实现源码概览
关于反向迭代器的实现在后面会详细介绍现在可以暂时忽略
#includeiostream
#includecassert
#includemy_reverse_iterator.hnamespace qqq
{templateclass Tclass vector{public:/ iterator /////vector的迭代器是一个原生指针 typedef T* iterator;typedef const T* const_iterator;typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}/// construct and destroy //vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T value T()) //{_start new T[n];_finish _start n;_endOfStorage _finish;for (int i 0; i n; i){*(_start i) value;}}templateclass InputIteratorvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first last){push_back(*first);first;}}//vector(const vectorT v)//{// _start new T[v.size()];// _finish _start v.size();// _endOfStorage _start v.capacity();// // memcpy(begin(), v.cbegin(), sizeof(T) * v.size());//}vector(const vectorT v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){int sz v.size();reserve(sz);for (int i 0; i sz; i){*(_start i) v[i];}}vectorT operator (vectorT v){swap(v);return *this;}~vector(){if (_start ! nullptr){delete[] _start;_start _finish _endOfStorage nullptr;}} capacity ///size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty(){if (size() 0){return true;}return false;}void reserve(size_t n){if (n capacity()){T* temp new T[n];int sz size();if (sz ! 0){ //当T为自定义类型时memcpy为浅拷贝temp中的自定义类型的数据与*this是相同的delete调析构释放原空间就会使temp中数据为野指针//memcpy(temp, cbegin(), sizeof(T) * size()); for (size_t i 0; i size(); i){*(temp i) *(_start i);}delete[] _start;}_start temp;_finish _start sz;_endOfStorage _start n;}}void resize(size_t n, const T value T()){if (n size()){if (n capacity()){reserve(n);}int oldSize size();_finish _start n;for (size_t i oldSize; i n; i){*(_start i) value;}}else{_finish _start n;}}///accessT operator[](size_t pos){assert(_start pos _finish);return *(_start pos);}const T operator[](size_t pos) const{assert(_start pos _finish);return *(_start pos);}///modify/void push_back(const T x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T x)//pos传参在reserve后会出现迭代器失效{assert(pos _start pos _finish);int sz pos - _start; if (size() capacity()){reserve(capacity() 0 ? 10 : capacity() * 2);pos _start sz; //解决迭代器失效}vectorT::iterator it end() - 1;while (it pos){*(it 1) *it;--it;}*pos x;_finish;return _start;}iterator erase(iterator pos){assert(pos _start pos _finish);if (empty()){return _start;}vectorT::iterator it pos 1;while (it _endOfStorage){*(it - 1) *it;it;}--_finish;return _start;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}总结
到此关于vector的主要接口实现就结束了 相信通过接口的模拟实现可以使我们更深入的了解vector 关于STL容器的介绍才刚刚开始欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
