用卫生纸做的礼物街网站,模板建站合同,怎么快速提升网站权重,怎么做同城网站#x1f307;个人主页#xff1a;_麦麦_ #x1f4da;今日小句#xff1a;快乐的方式有很多种#xff0c;第一种便是见到你。 目录
一、前言
二、vector的介绍及使用
2.1 vector的介绍
2.2 vector的使用
2.2.1 vector的定义#xff08;构造函数#xff09;
2.2.2… 个人主页_麦麦_ 今日小句快乐的方式有很多种第一种便是见到你。 目录
一、前言
二、vector的介绍及使用
2.1 vector的介绍
2.2 vector的使用
2.2.1 vector的定义构造函数
2.2.2 vector迭代器的使用 2.2.3 vector 空间增长问题
2.2.3vector增删查改
2.2.4 vector迭代器失效问题
三、vector的模拟实现
3.1成员变量与构造函数
3.2 insert与reverse
3.3 析构函数
3.4 【】的重载
3.5 insert
3.5 erase
3.6 pop_back 3.7 resize
3.8 其他构造
3.9 赋值重载
四、全部代码
五、结语 一、前言 今天为大家带来vector的介绍和模拟实现文章若有不足之处欢迎大家给出指正 二、vector的介绍及使用
2.1 vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3. 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是 一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4. vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5. 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增 长。 6. 与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list 统一的迭代器和引用更好。 2.2 vector的使用
2.2.1 vector的定义构造函数
construct构造函数声明接口说明vector()无参构造vector(size_type n, const value_type val value_type()) 构造并初始化n个val vector(const vector x)拷贝构造vector((InputIterator first, InputIterator last)使用迭代器进行初始化构造
2.2.2 vector迭代器的使用
ieterator的使用接口说明beginend获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置 的iterator/const_iteratorrbeginrend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的 reverse_iterator 对于正向迭代器来言通过begin和end获得的区间是一个左闭右开的区间也就是end所返回的迭代器指向的vector的最后一位有效数据的下一位 对于反向迭代器我们知道通过它我们能够反向的遍历vector这个容器但是它的实现并不只是简单地将正向迭代器头尾进行交换通过上图我们也能够发现具体的原因和实现我们会在下面的模拟实现为大家娓娓道来。 2.2.3 vector 空间增长问题
容量空间接口说明size 获取数据个数 capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector的capacity 首先我们要知道的是对于vector的这个容器当我们在进行插入数据并不需要手动扩容因为它会自动的根据容器中_size和_capacity两者的比较来判断在插入数据前容器是否已满如果已满就会将该容器扩容但具体的扩容大下则是根据不同的编译环境有着不同的实现有的是按照1.5倍_capacity来进行扩容有的则是按照2倍_capacity来进行扩容。 其次除了vector自行的扩容会对vector的容量进行改变它还提供了两个与容器大小有关的接口resize和reserve来供我们使用。对于前者按字面意义来说就是改变vector的_size。当我们使用这个函数的时候大抵会面对三种种情况1.输入量容量 2.有效数据输入量容量 3.输入量有效数据。 对于第一种情况编译器便会对当前容器进行扩容的操作。而对于第二情况由于当前容器的capacity能够满足我们对size的需求就会在当前有效数据后填补我们所输入的数据至size。最后一种情况的下由于我们输入的size小于有效数据那么我们便要减小有效数据的数量至输入的_size。 最后呢是reserve这一个接口。它最主要的作用就是能够帮助我们开辟空间以减少容器的不断扩容需要注意的一点是当我们的输入容量小于目前容量时一般情况下编译器并不会将多余的容量的进行释放。这是因为当我们释放空间的时候只能释放一整块空间而不能释放一块空间的一小部分。否则代价会极大。 psreserve负责开辟空间而resize在开空间的同时还会进行初始化影响size 2.2.3vector增删查改
vector增删查改接口说明push_back尾插pop_back尾删find查找注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[]像数组一样访问
2.2.4 vector迭代器失效问题 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了 封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器 程序可能会崩溃)。 对于vector可能会导致其迭代器失效的操作有 ①会引起其底层空间改变的操作都可能使迭代器失效比如resize、reserve、insert、assign、push_back等 ②指定位置元素的删除操作-erase。erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。 注与vector类似string在插入扩容操作erase之后迭代器也会失效 #include iostream
using namespace std;
#include vector//底层空间改变引起的迭代器失效
void text_1()
{vectorint v(10, 5);auto it v.begin();//将有效元素个数增加到150个多出的位置用2来填充操作期间底层会扩容//v.resize(150, 2);//reserve的做优就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变//v.reserve(150);//插入元素期间可能引起扩容而导致原空间被释放//v.push_back(8);//v.insert(v.begin(), 8);//给vector重新赋值可能会引起的层容量改变v.assign(150, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。*/while (it ! v.end()){cout *it;it;}cout endl;
}//使用erase导致的迭代器失效
void text_2()
{vectorint v {1,2,3,4,5};auto it find(v.begin(), v.end(), 4);v.erase(it);cout *it endl;}int main()
{//text_1();text_2();return 0;
}
三、vector的模拟实现
3.1成员变量与构造函数 当我们最开始了解一个容器的时候最先研究的就是它的成员变量与构造函数所以当我们在模拟实现的时候自然也是从此开始着手。 首先是vector的成员变量它的成员变量可是与string是不一样的string是一个char*的指针加上size和capacity而vector的则是由三个迭代器组成分别是指向起始位置有效数据的下一位存储的最大容量。 然后是构造函数我们会模拟实现常见的三种构造函数分别是无参的构造n个值的构造以及一段迭代器区间构造。至于其中涉及的函数会在下面具体介绍 代码如下 namespace mine
{template class Tclass vector{typedef T* iterator;typedef const T* const_iterator;public:vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}vector(size_t n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}private:iterator _startnullptr;iterator _finishnullptr;iterator _endofstoragenullptr;};} 3.2 insert与reverse 在能够能够成功创建出一个vector对象接下来就是实现数据的插入了 我们先来实现最简单的尾插。 在进行数据的尾插之前我们第一步要做的就是检查当前容器的容量如果容量已满那么我们就需要对当前的容器进行扩容也就是reverse的操作。 具体代码如下 void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];size_t i 0;while (i ! size()){tmp[i] _start[i];i;}delete[] _start;/* if (_start){memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}*/_start tmp;_finish tmp sz;_endofstorage tmp n;}}void push_back(const T x){//扩容if (_finish _endofstorage){size_t newcapacity (_start nullptr ? 4 : 2 * (_finish - _start));reserve(newcapacity);}//插入数据*_finish x;_finish;}3.3 析构函数 对于vector的析构函数我们只需要将申请的空间释放并将成员变量定义为空指针即可具体代码如下 ~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;}}3.4 【】的重载 对于vector来说它也重载了【】操作符我们只需对_start迭代器进行处理即可得到我们想要的数据。 具体代码如下 T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}
3.5 insert 由于vector的存储空间是连续的因此当我们进行数据插入的时候尾插的效率是最高的当然有时我们也不可避免的会遇到头插或者在中间插入数据的情况。于是便提供了insert的这个接口。 在本节中我们实现的是在指定位置位置插入一个有效数据那么在实现这个成员函数的时候倘若一不小心就会碰到我们在前面讲过的迭代器失效的问题。为什么会迭代器失效呢因为当我们在进行数据的插入时如果容器内的数据已满就需要进行扩容的操作那么扩容之后传进来的迭代器位置就有可能并不指向容器位置因而导致了迭代器失效。那么为了解决这个问题当我们在扩容之后就需要重新对传进来的迭代器进行一个重新的赋值保证其仍指向容器的数据。为了做到这一点我们需要的便是在进行扩容之间先记录pos迭代器的相对位置。 具体实现如下 void insert(iterator pos ,const T x){assert(pos _start pos_endofstorage);size_t dis pos - _start;//扩容if (_finish _endofstorage){size_t newcapacity (_start nullptr ? 4 : 2 * (_finish - _start));reserve(newcapacity);//避免pos迭代器失效pos _start dis;}//插入数据{size_t len _finish-pos;T* end _finish;//挪动数据while (end pos){*(end 1) *end;--end;}//插入数据*pos x;_finish;}
3.5 erase 在实现完vector的插入和尾插后那么当我们想要删除某些数据的时候就要用到erase这个函数了在这面我们实现的仅仅是简单地删除指定位置的一个有效数据。 对于erase而言也会面临的pos迭代器失效的问题当我们删除的是尾部最后一个数据的时候那么面对这样的情况我们的解决方法就是给erase函数增加一个返回值返回值是指向删除数据的下一个数据的迭代器那么当我们在使用这个函数的时候只要去接受这个返回值来对pos进行更新就不会出现迭代器失效的问题了。 具体代码如下 iterator erase(iterator pos){assert(pos _start pos _finish);iterator tmp pos 1;while (tmp ! _finish){*(tmp - 1) *tmp;tmp;}--_finish;return pos;}
3.6 pop_back 在实现完erase后尾删的话我们只需要复用这个函数即可对尾部的迭代器进行--即可实现尾删的功能。 具体代码如下 void pop_back(){erase(end()-1);} 3.7 resize 在实现完reverse之后紧随其后的就是resize。在前面我们已经提到了在对vector进行resize的时候我们会面临三种情况1.输入量容量 2.有效数据输入量容量 3.输入量有效数据。 对于第一种情况编译器便会对当前容器进行扩容的操作。而对于第二情况由于当前容器的capacity能够满足我们对size的需求就会在当前有效数据后填补我们所输入的数据至size。最后一种情况的下由于我们输入的size小于有效数据那么我们便要减小有效数据的数量至输入的_size。 具体实现如下 void resize(size_t n, const T val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}
3.8 其他构造 在前面较为基础的构造之外接下来我们来实现vector的其他构造。 首先是拷贝构造一种是传统的写法就是开好空间后利用memcpy将另一个对象拷贝过去另一种则是复用尾插将数据一个个插入进去。对于前者的话会存在一个浅拷贝的问题vector中存储的是内置类型的话memcpy是没有问题的但是如果是自定义类型的话就会存在一个浅拷贝的问题这是由于memcpy是按字节进行拷贝的为了解决这个问题我们在进行扩容的的时候就不能再使用memcpy的方式来拷贝数据而是通过赋值的方式来调用自定义类型的赋值重载这样就实现了深拷贝。 然后是n个值来初始化vector思路大致就是复用我们已经写好的resize就可以了 最后就是用一段迭代器区间来初始化vector实现起来主要就是在用一个类模板不过在实际当我们在使用n个值来初始化vector的时候会出现匹配的歧义它会与迭代器的这个构造更加匹配因此面对匹配歧义这个问题我们可以再重载一个n个值来初始化的构造函数只需要将前面的类型修改为int即可。 具体代码如下 //传统写法vector(const vector v){_start new T[v.capacity()];_finish _start v.size();_endofstorage _start v.capacity();size_t n 0;while (n ! size()){*(_start n) *(v.begin() n);n;}}//复用写法vector(const vector v){reserve(v.capacity());for (auto e : v){push_back(e);}}vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}
3.9 赋值重载 在实现vector的赋值重载我们依旧可以采取像前面string的类似方法通过与形参交换成员变量来达到赋值拷贝的效果。 具体代码如下 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage,v._endofstorage);}vectorT operator( vectorT v){swap(v);return *this;}
四、全部代码
#pragma once
#include assert.hnamespace mine
{template class Tclass vector{typedef T* iterator;typedef const T* const_iterator;public:vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];size_t i 0;while (i ! size()){tmp[i] _start[i];i;}delete[] _start;/* if (_start){memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}*/_start tmp;_finish tmp sz;_endofstorage tmp n;}}void push_back(const T x){//扩容if (_finish _endofstorage){size_t newcapacity (_start nullptr ? 4 : 2 * (_finish - _start));reserve(newcapacity);}//插入数据*_finish x;_finish;}void insert(iterator pos ,const T x){assert(pos _start pos_endofstorage);size_t dis pos - _start;//扩容if (_finish _endofstorage){size_t newcapacity (_start nullptr ? 4 : 2 * (_finish - _start));reserve(newcapacity);//避免pos迭代器失效pos _start dis;}//插入数据{size_t len _finish-pos;T* end _finish;//挪动数据while (end pos){*(end 1) *end;--end;}//插入数据*pos x;_finish;}}iterator erase(iterator pos){assert(pos _start pos _finish);iterator tmp pos 1;while (tmp ! _finish){*(tmp - 1) *tmp;tmp;}--_finish;return pos;}void pop_back(){erase(end()-1);}void resize(size_t n, const T val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}//传统写法/* vector(const vector v){_start new T[v.capacity()];_finish _start v.size();_endofstorage _start v.capacity();size_t n 0;while (n ! size()){*(_start n) *(v.begin() n);n;}}*///复用写法vector(const vector v){reserve(v.capacity());for (auto e : v){push_back(e);}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage,v._endofstorage);}vectorT operator( vectorT v){swap(v);return *this;}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;}}private:iterator _startnullptr;iterator _finishnullptr;iterator _endofstoragenullptr;};void print(const vectorint v){for (auto e : v){cout e ;}cout endl;}
}
五、结语 到此为止关于vector的讲解就告一段落了至于其他的内容小伙伴们敬请期待呀 关注我 _麦麦_分享更多干货_麦麦_-CSDN博客 大家的「关注❤️ 点赞 收藏⭐」就是我创作的最大动力谢谢大家的支持我们下期见
