C++STL之vector（超详细）

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：vector基本介绍；vector重要接口：构造函数；迭代器；空间；增删查改；迭代器失效；迭代器分类
⬆⬆⬆⬆上一篇：C++IO流
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

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_type&val)	构造n个val
vector(InputIterator first, InputIterator last）	使用迭代器构造

#include <vector>
#include <iostream>
using namespace std;
int main()
{vector<int> v1;//默认构造int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };vector<int> v2(arr, arr + 10);//使用迭代器来构造for (auto& e : v2){cout << e << " ";}cout << endl;vector<int> v3(2, 10);//构造2个为10的元素for (auto& e : v3){cout << e <<" ";}vector<int> v4(v3);//拷贝构造return 0;
}

2.2.迭代器

我们来看一下迭代器，迭代器就是迭代器是一种访问容器内元素的对象，它提供了一种方法来顺序访问容器中的各个元素，而不需要了解容器的内部工作原理。

vector	迭代器iterator/reverse_iterator
begin+end	正向迭代器
rbegin+rend	反向迭代器

#include <iostream>
#include <vector>
using namespace std;
int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };vector<int> v(arr, arr + 10);//使用迭代器//正向迭代器vector<int>::iterator it = v.begin();while (it != v.end())//end是最后一个元素的下一个位置{cout << *it <<' ';//像指针一样使用it++;}cout << endl;//反向迭代器vector<int>::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()
{vector<int> 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()
{vector<int> 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()
{vector<int> 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版本STL，g++是SGI版本STL。

我们还要注意下它的效率问题，如果我们提前知道需要多少空间，就可以提前扩容来保证一次的开辟空间，来避免多次扩容的效率低下

#include <iostream>
#include  <vector>
using namespace std;
int main()
{vector<int> 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个val
iterator erase (iterator position);	删除position位置的元素
iterator erase (const_iterator first, const_iterator last);	删除迭代器范围的元素
void swap (vector& x);	交换两个vector
reference operator[] (size_type n);	像数组一样的访问

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{vector<int> 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 && erasevector<int>::iterator it=find(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()
{vector<int> v;v.push_back(11);v.push_back(12);v.push_back(13);v.push_back(14);cout << v.capacity() << endl;//接下来再插入就会扩容	vector<int>::iterator it = v.begin();v.insert(it, 10);cout << v.capacity() << endl;cout << *it << endl;return 0;
}

上述代码就演示了这个情况，使用一块已经被释放的空间，造成的后果是程序崩溃，我们仅仅演示了一下insert造成的结果，其实其他会造成扩容的函数如resize，reverse，push_back都会造成迭代器失效，同时从另一个角度来说，我们所传入的迭代器position所指向的内容已经不是我们想要的了，这也是迭代器失效的一种情况，因此insert以后我们认为迭代器已经失效，不能再使用

下一种情况是erase，思考一下？erase会扩容吗？答案是并不会，只是删除元素，所以说就没问题了？不不不，仔细思考一下，我的迭代器此时指向最后一个元素，如果我erase了一个元素呢，我们底层的_finish指针就会–，那此时的迭代器就相等于是指向无效空间

//!!!!!error code
#include <iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::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()
{vector<int> v{1,2,3,4,5};//删除偶数vector<int>::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()
{vector<int> v{ 1,2,3,4};//删除偶数vector<int>::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直接和_finish（end()）直接错过了，这样即使是Linux也无能为力了

直接发生段错误

从上述的例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。
因此我们的insert和erase函数都会返回一个迭代器来供我们使用，我们修正一下上面的代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v{ 1,2,3,4};//删除偶数vector<int>::iterator it = v.begin();while (it != v.end()){if ((*it) % 2 == 0){it=v.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是随机迭代器，它支持++和–，也支持+和-，同样支持[ ]
理论上来讲，模板语法上可以传任何类型参数，但是内部使用迭代器是有要求

🌸🌸C++STL之vector的知识大概就讲到这里啦，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪