郑州专业网站建设,金华seo全网营销,招聘网站开发流程,能免费建网站吗vector是我接触的第一个容器#xff0c;好好对待#xff0c;好好珍惜#xff01; 目录
文章目录
前言
二、vector如何实现
二、vector的迭代器#xff08;原生指针#xff09;
三、vector的数据结构
图解#xff1a;
四、vector的构造及内存管理
1.push_back()
… vector是我接触的第一个容器好好对待好好珍惜 目录
文章目录
前言
二、vector如何实现
二、vector的迭代器原生指针
三、vector的数据结构
图解
四、vector的构造及内存管理
1.push_back()
代码如下
2.pop_back() 代码如下
3.insert()
图解
代码如下:
需要注意的是insert()迭代器失效问题
4.erase()
图解
代码如下:
需要注意的是erase()的迭代器失效问题
给出三种验证的例子
图解
五、vector的reserve与resize
1.reserve()
代码如下
需要注意的是memcpy()的浅拷贝问题
改进版
代码如下
2.resize()
代码如下
六、vector类的基本成员函数
1.default构造
代码如下
2.copy构造
1传统写法
代码如下
需要注意的仍然是memcpy()的浅拷贝
改进版
2现代写法
代码如下
3.用迭代器区间的copy构造函数
4.析构
代码如下
七、其他的一些函数
1.获取size
代码如下
2.获取capacity
代码如下
3.访问元素
代码如下
4.迭代器 - 使用范围for
代码如下
5.赋值重载
1传统写法
需要注意的仍然是memcpy()的浅拷贝
改进版
2现代写法
代码如下
6.swap()
代码如下
总结 前言 vector实现时最难想的是赋值重载时的现代写法很妙最有趣的是两种迭代器的失效问题。与数组相同但又多少有点不同。 一、vector是什么 vector是一个序列式容器其中的元素都可序ordered但是未必有序sorted本质上是可变数组尾插尾删效率较高。 二、vector如何实现 源代码中vector的实现使用到了alloc空间配置器但是鉴于自身技术水平个人只在本文中阐述如何实现无alloc版本的vector。 二、vector的迭代器原生指针 因为vector是一段连续的物理存储空间实现增删查改时需要对位置进行、--、、-、、-、-这些都是普通指针就具备的能力所以vector提供的是Random Access Iterators。 代码如下示例
templatetypename Tclass vector{public: typedef T valueType;typedef T* iterator;private:iterator _start;iterator _finish;iterator _endOfStorage;}
三、vector的数据结构 vector是一段连续的物理空间其中SGI版本使用了三个指针去管理这个变长数组、使用了两个unsigned int变量去标识有效字符与容量。 图解 四、vector的构造及内存管理 与之前学习数据结构实现的动态顺序表内存管理其实大同小异一开始有一块默认大小的内存 增 ①内存不够再存新元素扩容一般扩至原capacity的2倍 ②内存够直接存。 删 ①减少元素个数但是不缩容大部分版本。 1.push_back()
代码如下
void push_back(const valueType x) {// 增容if (_finish _endOfStorage){reserve((capacity() 0) ? 4 : capacity() * 2);}// 尾插*_finish x;_finish;}
2.pop_back() 代码如下
// 尾删void pop_back(){assert(_finish _start);--_finish;}
3.insert() 原stl给出的模板中insert()是返回了一个迭代器指向插入元素的位置。 目的若迭代器已经失效尽管在增容操作中更新迭代器的值进行规避风险但是调用时的迭代器仍为野指针失效状态若后续操作需要使用插入元素位置那就会在此出现问题所以可以再用这个迭代器接受insert()的返回值来进行更新。 图解 代码如下:
// 随机插入iterator insert(iterator pos, const valueType val){// 最小在头插最大在尾插assert(pos _start);assert(pos _finish);//增容会使迭代器失效if (_finish _endOfStorage){// 更新迭代器的值size_t len pos - _start;reserve((capacity() 0) ? 4 : capacity() * 2);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos val;// 元素个数1_finish1_finish;return pos;}
需要注意的是insert()迭代器失效问题 当插入时vector进行了扩容操作这一步会 ①使用一块新的、够大的tmp空间去拷贝原来_start指向的数据 ②将原来的_start指向的空间释放 ③把tmp的空间给_start 但是此时传进来的、想要插入数据的迭代器仍然指向原来的_start空间这个迭代器就变成了野指针再下一步对这个迭代器指向位置进行操作时就会非法访问所以需要在进行扩容操作是对于迭代器也进行相应的更新尽量避免失效问题。 4.erase() 原stl给出的模板中erase()是返回了一个迭代器指向删除元素的位置的下一个位置。 目的同insert()相同。 Q为什么指向的是操作位置的下一个位置 A因为删除操作本质上是对数据的覆盖这样一来从操作位置开始向后的数据向前挪动也相当于操作位置向后移动了一位指向了下一个位置。 图解 代码如下:
// 随机删除iterator erase(iterator pos){// 最小头删最大尾删assert(pos _start);assert(pos _finish);auto begin pos 1;while (begin ! _finish){*begin *(begin 1);begin;}// 删除一个元素_finish向前移动--_finish;// 返回的是删除元素的下一个元素return pos;}
需要注意的是erase()的迭代器失效问题 erase()的迭代器失效主要是因为迭代器的意义改变当然也有野指针的问题。 ps但是这个无法通过我们改变erase()实现去规避。 ①意义改变当数据向前挪动时这个迭代器已经不再是我们想要的迭代器了他一次性向后跳了两个位置。 ②野指针当数据向前挪动时迭代器可能跳过了_finish当第一次与_finish相遇时begin的操作还在继续进行从而继续向后移动宛如脱缰野马永远不可能再停下与_finish相遇才会结束。 给出三种验证的例子 均是删除给定数据中的偶数元素 1 2 3 4 5 - 迭代器意义改变但是刚好这个bug没有使结果出现问题 1 2 3 4 - 迭代器 1 2 4 5 - 4被跳过迭代器每次相当于向后移动2位未删除 图解 五、vector的reserve与resize
1.reserve() 改变的是容器的容量需要进行开辟空间、释放空间、拷贝数据的操作效率不是很高也正因为扩容的效率不高所以才有了_endofStorage和_finish去标识容量与元素个数。 代码如下
void reserve(size_t newCapacity){// 扩容valueType* tmp new valueType[newCapacity]();size_t sz size();// 如果有数据需拷贝到新空间if (_start){memcpy(tmp, _start, sizeof(valueType) * size());}// 释放旧空间delete[] _start;_start tmp;_finish _start sz;_endOfStorage _start newCapacity;}
需要注意的是memcpy()的浅拷贝问题 因为memcpy()进行的是位操作如果copy的是内置类型int、char等那么直接使用memcpy()会效率很高很方便但是牵扯到指针这会导致内存错误 当两个指针的内容相同那就意味着它们指向了同一块空间如果一个指针释放另一个指针仍对其进行操作就会使得内存发生错误。 改进版 使用for循环自己一个元素一个元素进行拷贝。 代码如下
void reserve(size_t newCapacity){// 扩容valueType* tmp new valueType[newCapacity]();size_t sz size();// 如果有数据需拷贝到新空间if (_start){//memcpy(tmp, _start, sizeof(valueType) * size());for (size_t i 0; i sz; i){tmp[i] _start[i];}}// 释放旧空间delete[] _start;_start tmp;_finish _start sz;_endOfStorage _start newCapacity;}
2.resize() 改变的是元素的个数size。 ①如果newSize比size小那么就发生了删除直接改变_finish即可但是不缩容以防后续操作频繁删除增容、频繁向操作系统申请、释放内存造成抖动。 ②如果newSize比size大那么就可能发生了扩容需检查。 1.若给出初始化的值那么根据给出的值进行初始化 2.若无给出的值默认是空在模板中是const vaueType val valueType()构造了空的对象进行缺省参数的赋值。 代码如下
void resize(size_t newSize, const valueType x valueType()){// newSize比size短截断// 但是容量不变if (_finish newSize _endOfStorage){_finish _start newSize;}// 长增长并初始化else{reserve(newSize);while (_finish ! _start newSize){*_finish x;_finish;}}}
六、vector类的基本成员函数
1.default构造 三个原生指针初始化为空指针即可。 代码如下
// 构造vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}
2.copy构造
1传统写法 传统写法就是自己一步一步实现深拷贝的过程。 代码如下
// copy构造// 传统写法vector(const vectorvalueType obj){_start new valueType[obj.size()];_finish _start obj.size();_endOfStorage _start obj.capacity();memcpy(_start, obj._start, obj.size() * sizeof(valueType));}
需要注意的仍然是memcpy()的浅拷贝 我们应该使用for循环去自己实现深拷贝避免内存问题。 改进版
// 传统写法vector(const vectorvalueType obj){_start new valueType[obj.size()];_finish _start obj.size();_endOfStorage _start obj.capacity();//memcpy(_start, obj._start, obj.size() * sizeof(valueType));for (size_t i 0; i size(); i){_start[i] obj._start[i];}}
2现代写法 使用tmp变量让其使用构造函数构造出我们想要copy的对象然后将tmp和我们将要copy的对象进行交换从而帮助我们实现copy构造。 swap(tmp, *this)这一点就是将*this中的垃圾扔给了tmptmp还把自己有用的数据全部交给了*this就好比是外卖员替你送了外卖还得帮你扔垃圾。 但是很明显的是已有的构造函数并不能根据传进来的obj对tmp进行构造。我们需要重载实现一个支持用迭代器区间的copy构造函数stl本来也支持这样的方式构造。见下一点 pscopy构造也是构造别忘了初始化 代码如下
// 现代写法//类模板的成员函数也可以变成函数模板vector(const vectorvalueType obj):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){vectorvalueType tmp(obj.begin(), obj.end());// “外卖员送饭又倒垃圾的例子”swap(tmp);}
3.用迭代器区间的copy构造函数 我们实现为了模板函数这一点是在套娃 本来就是类模板的成员函数其可以用函数模板去实现。 目的 其他的迭代器string、int、char等都可以通过迭代器去构造。 // 迭代器版的copy构造template class InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first ! last){this-push_back(*first);first;}}
4.析构 析构是释放空间因为三个指针指向的是同一段空间所以只需要释放_start。 然后将它们置为空。 psnew时候使用的[]所以delete也需要[]进行释放。 代码如下
// 析构~vector(){delete[] _start;_start _finish _endOfStorage nullptr;}
七、其他的一些函数
1.获取size 回想我们之前的结构 size就是_finish与_start之间的距离使用两个指针相减即可得到。 代码如下
size_t size() const{return _finish - _start;}
2.获取capacity 同size()。 代码如下
size_t capacity() const{return _endOfStorage - _start;}
ps但是需要注意的是这两个成员函数最好实现为const成员函数因为在copy构造与的default构造时传的参数均使用了const。常对象与非常对象都可以用const
3.访问元素 数组可以通过下标访问。 代码如下
const valueType operator[](size_t i){return _start[i];}
4.迭代器 - 使用范围for 实现为const原理同size()、capacity()。 代码如下
// 迭代器// 必须是begin与end同名才能使用范围foriterator begin() const{return _start;}iterator end() const{return _finish;}
5.赋值重载 赋值重载与copy构造总是很相像 ①赋值重载是相对于两个已经存在的对象之间的操作。 ②copy构造是相对于一个即将创建一个已经存在的对象之间的操作。 但是它们最终要达到的目标都是相同的让两个对象相等。 所以在实现过程上也大同小异。 实现赋值重载需要注意的点是 ①判断是否给自己赋值 ②需要传引用返回减少拷贝 ③传进来的函数参数需要是const的引用防止修改减少拷贝。 ④返回值是*this 1传统写法 与copy构造相同的是它也要实现释放旧空间、开辟新空间、拷贝数据。 // 传统写法vectorvalueType operator(const vectorvalueType obj){// 判断是否给自己赋值if (this obj){return *this;}delete[] _start;//_start (valueType*)calloc(obj.capacity(), sizeof(valueType));_start new valueType[obj.capacity()];_finish _start obj.size();_endOfStorage _start obj.capacity();memcpy(_start, obj._start, sizeof(obj) * obj.size());return *this;}
需要注意的仍然是memcpy()的浅拷贝 我们使用for循环自己进行深拷贝。 改进版
// 传统写法vectorvalueType operator(const vectorvalueType obj){// 判断是否给自己赋值if (this obj){return *this;}delete[] _start;//_start (valueType*)calloc(obj.capacity(), sizeof(valueType));_start new valueType[obj.capacity()];_finish _start obj.size();_endOfStorage _start obj.capacity();//memcpy(_start, obj._start, sizeof(obj) * obj.size());for (size_t i 0; i obj.size(); i){_start[i] obj._start[i];}return *this;}
2现代写法 这种写法很巧妙地使用了传值传参需要进行拷贝构造的特点利用这一点在传参的时候就可以深拷贝出来一个obj这样进行交换的时候就不会把原来的obj更改。 代码如下
/ 赋值重载 v2 v1// 现代写法vectorvalueType operator(vectorvalueType obj){swap(obj);return *this;}
6.swap() 由于copy构造与赋值重载都使用了交换所以将它实现为了函数。 代码如下
void swap(vectorvalueType tmp) {std::swap(tmp._start, _start);std::swap(tmp._finish, _finish);std::swap(tmp._endOfStorage, _endOfStorage);}
总结 vector的实现是对于stl源码的一次深入理解但是仍然没有学会alloc只学习了一部分自己模拟实现vector不在于造一个更好的轮子但是可以帮助我更好的了解它、使用它。
