苏州建行网站,亚马逊雨林面积有多大,网站推广优化联系方式,网站的大量图片存储格式CSTL之vector 1.vector基本介绍2.vector重要接口2.1.构造函数2.2.迭代器2.3.空间2.3.1.resize2.3.2.capacity 2.4.增删查找 3.迭代器失效4.迭代器分类 #x1f31f;#x1f31f;hello#xff0c;各位读者大大们你们好呀#x1f31f;#x1f31f; #x1f680;#x1f68… CSTL之vector 1.vector基本介绍2.vector重要接口2.1.构造函数2.2.迭代器2.3.空间2.3.1.resize2.3.2.capacity 2.4.增删查找 3.迭代器失效4.迭代器分类 hello各位读者大大们你们好呀 系列专栏【C的学习】 本篇内容vector基本介绍vector重要接口构造函数迭代器空间增删查改迭代器失效迭代器分类 ⬆⬆⬆⬆上一篇CIO流 作者简介轩情吖请多多指教( •̀֊•́ ) ̖́- 1.vector基本介绍 ① 在我们C语言中有数组C中因此也设计了array来代替C语言中的数组但是它有一个缺点就是array是静态空间一旦配置了空间就无法改变这就让使用者非常麻烦。但是vector就不一样它是动态空间一旦底层空间不足就会自动扩容压根不需要担心空间不足而造成问题。 ②vector扩容当新元素插入进来时发现内存不足这个时候就会先扩容开辟新的空间并不是原地扩容因为可能后面没有内存然后把原来的数据拷贝过去再进行插入然后把旧的空间给释放掉。并且我们扩容的空间基本上是以倍数来增长的保证后续再有元素插入时不需要扩容导致效率低下。 ③vector支持随机访问即像数组一样[ ]来访问非常高效同时在末尾删除和末尾插入元素非常高效这得益于它的结构。但是其他的位置进行操作效率就会比较低下没有list好 2.vector重要接口
☞vector参考文档
2.1.构造函数 对于任何容器首先看的肯定是构造函数 讲一下其中比较重要的 vector构造函数vector()默认构造函数vector(const vector)拷贝构造vector(size_type n,const value_typeval)构造n个valvector(InputIterator first, InputIterator last使用迭代器构造
#include vector
#include iostream
using namespace std;
int main()
{vectorint v1;//默认构造int arr[10] { 1,2,3,4,5,6,7,8,9,10 };vectorint v2(arr, arr 10);//使用迭代器来构造for (auto e : v2){cout e ;}cout endl;vectorint v3(2, 10);//构造2个为10的元素for (auto e : v3){cout e ;}vectorint v4(v3);//拷贝构造return 0;
}2.2.迭代器 我们来看一下迭代器迭代器就是迭代器是一种访问容器内元素的对象它提供了一种方法来顺序访问容器中的各个元素而不需要了解容器的内部工作原理。 vector迭代器iterator/reverse_iteratorbeginend正向迭代器rbeginrend反向迭代器
#include iostream
#include vector
using namespace std;
int main()
{int arr[10] { 1,2,3,4,5,6,7,8,9,10 };vectorint v(arr, arr 10);//使用迭代器//正向迭代器vectorint::iterator it v.begin();while (it ! v.end())//end是最后一个元素的下一个位置{cout *it ;//像指针一样使用it;}cout endl;//反向迭代器vectorint::reverse_iterator rit v.rbegin();while (rit ! v.rend()){cout *rit ;//像指针一样使用rit;//这里是而不是--因为已经说明是反向迭代器就该使用}return 0;
}2.3.空间
vector空间size_type size() const;获取数据个数size_type capacity() const;获取vector的容量大小bool empty() const;vector是否为空void reserve (size_type n);提前开辟空间只会改变vector的capacity,能够缓解vector增容代价问题void resize (size_type n, value_type val value_type());改变vector的size可以变大也可以变小
#include iostream
#include vector
using namespace std;
int main()
{vectorint v;//emptyif (v.empty()){cout empty endl;}cout ------------------ endl;//sizev.push_back(10);v.push_back(10);v.push_back(10);cout v.size() endl;cout ------------------ endl;//capacitycout v.capacity() endl;cout ------------------ endl;//reversev.reserve(10);//提前扩容到能存放10个元素的空间cout v.size() endl;//3不会改变cout v.capacity() endl;//10cout ------------------ endl;//resizev.resize(20);cout v.size() endl;//20改变size元素为默认值cout v.capacity() endl;//20return 0;
}2.3.1.resize 其中我们的resize还有其他的功能可以缩小空间以及设定自己想要的元素resize在开空间的同时还会进行初始化影响size 具体演示见下面 #include iostream
#include vector
using namespace std;
int main()
{vectorint v;v.push_back(10);v.push_back(11);v.push_back(12);v.push_back(13);v.push_back(14);cout size:v.size() endl;for (auto e : v){cout e ;}cout endl;cout --------------------- endl;v.resize(3);cout size: v.size() endl;for (auto e : v){cout e ;}cout endl;cout --------------------- endl;v.resize(10,33);//把7个元素都设置为33cout size: v.size() endl;for (auto e : v){cout e ;}cout endl;cout --------------------- endl;return 0;
}2.3.2.capacity 我们这边再详细讨论一下capacity这个成员函数我们想一下我们的vector的扩容是按照什么来的呢需要空间就扩容一个个扩容我们来看一下下面的一段代码分别在windows和Linux下展示 #include iostream
#include vector
using namespace std;
int main()
{vectorint v;size_t cap v.capacity();cout initital capacity: cap endl;for (int i 0; i 100; i){v.push_back(i);if (cap ! v.capacity()){cap v.capacity();cout capacity changed: cap endl;}} return 0;
}windows: Linux: capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。 我们还要注意下它的效率问题如果我们提前知道需要多少空间就可以提前扩容来保证一次的开辟空间来避免多次扩容的效率低下 #include iostream
#include vector
using namespace std;
int main()
{vectorint v;v.reserve(100);//提前开辟好空间防止一遍遍的扩容造成效率低下for (int i 0; i 100; i){v.push_back(i);}cout v.capacity() endl;//100return 0;
}2.4.增删查找
vector增删查改void push_back (const value_type val);尾插void pop_back();尾删InputIterator find (InputIterator first, InputIterator last, const T val);这是算法中的查找iterator insert (iterator position, const value_type val);在position前插入元素void insert (iterator position, size_type n, const value_type val);在position位置前插入n个valiterator erase (iterator position);删除position位置的元素iterator erase (const_iterator first, const_iterator last);删除迭代器范围的元素void swap (vector x);交换两个vectorreference operator[] (size_type n);像数组一样的访问
#include iostream
#include vector
#include algorithm
using namespace std;
int main()
{vectorint v(2, 10);v.push_back(11);//尾插v.push_back(12);v.push_back(13);v.push_back(14);cout initiatl element:;for (auto e : v){cout e ;}cout endl;cout ------------------------------------------------------ endl;v.pop_back();//尾删cout after pop_back():;for (auto e : v){cout e ;}cout endl;cout ------------------------------------------------------ endl;v.insert(v.begin(), 9);//在第一个元素前的位置插入一个9cout after insert(v.begin(),9):;for (auto e : v){cout e ;}cout endl;cout ------------------------------------------------------ endl;//find erasevectorint::iterator itfind(v.begin(), v.end(),12);//查找元素为12的位置if (it ! v.end()){//如果返回的迭代器为end()说明没找到v.erase(it);}cout after erase(it):;for (auto e : v){cout e ;}cout endl;cout ------------------------------------------------------ endl;//operator[]for (int i 0; i v.size(); i){v[i] i;//operator[]的返回值是引用}cout after change element through operator[]:;for (auto e : v){cout e ;}cout endl;cout ------------------------------------------------------ endl;return 0;
}3.迭代器失效 接下来我们要谈谈迭代器失效的问题了这个如果不了解底层的话就会很容易掉进坑里面 首先我们先讲insert导致的迭代器失效 在我们使用insert的时候如果空间不足了那我们的vector就会自动帮我们扩容但是扩容常常需要经历三个步骤开辟新的空间;移动元素到新空间释放原来的空间。我们vector底层的实现的迭代器本身就是指针只不过是typedef了一下。仔细想想问题就来了当我们插入后有概率空间不足扩容后原本的迭代器指针就是野指针了没有指向新空间 //!!!!error code
#include iostream
#include vector
using namespace std;
int main()
{vectorint v;v.push_back(11);v.push_back(12);v.push_back(13);v.push_back(14);cout v.capacity() endl;//接下来再插入就会扩容 vectorint::iterator it v.begin();v.insert(it, 10);cout v.capacity() endl;cout *it endl;return 0;
}上述代码就演示了这个情况使用一块已经被释放的空间造成的后果是程序崩溃我们仅仅演示了一下insert造成的结果其实其他会造成扩容的函数如resizereversepush_back都会造成迭代器失效同时从另一个角度来说我们所传入的迭代器position所指向的内容已经不是我们想要的了这也是迭代器失效的一种情况因此insert以后我们认为迭代器已经失效不能再使用 下一种情况是erase思考一下erase会扩容吗答案是并不会只是删除元素所以说就没问题了不不不仔细思考一下我的迭代器此时指向最后一个元素如果我erase了一个元素呢我们底层的_finish指针就会–那此时的迭代器就相等于是指向无效空间 //!!!!!error code
#include iostream
using namespace std;
#include vector
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
}可以运行一下上面的代码分别在Linux和Windows下在Windows下会崩溃但是在Linux可以运行这不得不说VS的检查非常严erase后的迭代器是不允许使用的但是g的就会宽很多当删除3后元素4会往前移动pos的位置还是有效的 接下来就看一下下面这个代码 #include iostream
#include vector
using namespace std;
int main()
{vectorint v{1,2,3,4,5};//删除偶数vectorint::iterator it v.begin();while (it ! v.end()){if ((*it) % 2 0){v.erase(it);}it;}for (auto e : v){cout e ;}cout endl;return 0;
}首先对于环境而言是一样的在VS下会崩溃而Linux下能正常运行 我们来分析一下这个代码 可以发现我们的it很巧合的把偶数元素删除了同时也正好落到了_finish使用空间的尾end()也判断循环结束了我们接下里对代码稍作修改如下 #include iostream
#include vector
using namespace std;
int main()
{vectorint v{ 1,2,3,4};//删除偶数vectorint::iterator it v.begin();while (it ! v.end()){if ((*it) % 2 0){v.erase(it);}it;}for (auto e : v){cout e ;}cout endl;return 0;
}我们的元素的数量变为只有四个接下来再看一下它的执行逻辑 通过上面的图可以发现我们的it直接和_finishend()直接错过了这样即使是Linux也无能为力了 直接发生段错误 从上述的例子中可以看到SGI STL中迭代器失效后代码并不一定会崩溃但是运行结果肯定不对如果it不在begin和end范围内肯定会崩溃的。 因此我们的insert和erase函数都会返回一个迭代器来供我们使用我们修正一下上面的代码 #include iostream
#include vector
using namespace std;
int main()
{vectorint v{ 1,2,3,4};//删除偶数vectorint::iterator it v.begin();while (it ! v.end()){if ((*it) % 2 0){itv.erase(it);//接受迭代器返回的迭代器是it传入时的位置}else{it;}}for (auto e : v){cout e ;}cout endl;return 0;
}我们的string其实也是一样的道理只是对于string我们很少用迭代器 我们对str进行了提前扩容造成了野指针问题我们的string使用失效的迭代器也会崩溃 4.迭代器分类 在我们使用算法函数时有些函数需要特定的迭代器像我们的vector的迭代器本质就是原生指针因此它是一个随机迭代器我们可以看一下侯捷大佬的《STL源码剖析》里对迭代器的分类 我们Forward迭代器就是单向迭代器它是只支持重载的迭代器Bidrectional迭代器是双向迭代器它支持和–而我们的Random是随机迭代器它支持和–也支持和-同样支持[ ] 理论上来讲模板语法上可以传任何类型参数但是内部使用迭代器是有要求 CSTL之vector的知识大概就讲到这里啦博主后续会继续更新更多C的相关知识干货满满如果觉得博主写的还不错的话希望各位小伙伴不要吝啬手中的三连哦你们的支持是博主坚持创作的动力
