当前位置：首页 > news >正文

18. C++STL 4(vector的使用, 空间增长, 迭代器失效详解)

news 2024/11/30 20:27:57

⭐本篇重点：vector容器的使用详解

⭐本篇代码：c++学习/08.vector_test · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

一. vector的介绍

二. vector的使用

2.1 vector的定义 *

2.2 vector的迭代器和遍历

a operator[]访问

b vector迭代器的使用访问 *

c C++11 for循环

2.3 vector的容量操作和空间成长问题

a 容量操作:

b 空间增长问题 ***

2.4 vector的增删查改

三. 使用vector出现的迭代器失效问题 *

3.1 增容导致迭代器失效

3.2 erase导致迭代器失效

一. vector的介绍

vector的文档如下：vector - C++ Reference (cplusplus.com)

        1 vector就是一个可以动态增长的数组。和数组一样，可以使用[下标]来访问vector中存储的数据。

        2 vector动态分配数组来存储他的元素。每当插入新元素的时候，空间足够就会在数组尾部插入这个数据。如果空间不够，vector会重新分配一个容量更大的数组，然后将全部元素转移到这个新的数组中

        3 vector为了方便管理空间，每一次分配空间的时候都比实际要存储的空间要大一些。不同的系统和编译器增长的倍数有区别，一般都在1.5倍到2倍数

4 相对其他序列容器（list, deque, forward_list），vector访问数据的效率更高，在末尾插入删除数据效率高。在头部和中部插入删除数据由于要大量挪动数据，效率较低。

二. vector的使用

2.1 vector的定义 *

vector构造函数的列表如下: 标*表示重要

构造函数的声明	说明
vector(); *	一个简单的无参构造函数
vector(const vector& x); *	拷贝构造函数
vector(size_type n, const value_type& val = value_type())	构造并初始化为n个val
vector (InputIterator first, InputIterator last);	使用迭代器进行构造

赋值运算符

vector& operator=(const vector& x)

使用x这个容器去赋值

2.2 vector的迭代器和遍历

vector有三种遍历方式

a operator[]访问

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{//{}内部的数据可以看成为一个vectorvector<int> arr1 = { 1,5,9,7,5,3,4,6,8,2 };vector<int> arr2(arr1);	//使用拷贝构造函数构造vector//1. []访问遍历，可以读写数据		arr1.size()可以获取arr1中元素的大小for (int i = 0; i < arr1.size(); i++){cout << arr1[i] << " ";}cout << endl;//访问arr2for (int i = 0; i < arr1.size(); i++){cout << arr1[i] << " ";}cout << endl;return 0;
}

运行结果如下

b vector迭代器的使用访问 *

可以通过begin/end获取vector的迭代器

iterator	解释
begin()	获取第一个数据位置 iterator/ const_iterator
end()	获取最后一个数据位置 iterator/ const_iterator
rbegin()	获取最后一个数据位置 reverse_iterator
rend()	获取第一个数据位置的 reverse_iterator

迭代遍历如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{//{}内部的数据可以看成为一个vectorvector<int> arr = { 1,5,9,7,5,3,4,6,8,2 };//2.迭代器正向访问vector<int>::iterator it = arr.begin();while (it != arr.end()){cout << *it << " ";it++; //获取下一个位置的迭代器}cout << endl;//迭代器逆向访问vector<int>::reverse_iterator rit = arr.rbegin();while (rit != arr.rend()){cout << *rit << " ";rit++;}return 0;
}

运行结果:

当然:我们还能通过迭代器修改数据

c C++11 for循环

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{//{}内部的数据可以看成为一个vectorvector<int> arr = { 1,5,9,7,5,3,4,6,8,2 };//C++ 11 for循环for (const auto& e : arr)cout << e << " ";cout << endl;return 0;
}

运行结果

这种for循环的本质也是通过迭代器实现的!

2.3 vector的容量操作和空间成长问题

a 容量操作:

操作	说明
size()	获取这个vector的元素大小
capacity()	获取这个vectro的最大容量
empty()	判断这个vector是否为空
resize(size_type n) resize(size_type n, value_type& val)	将vector的size更改为 n 将vector的size更改为 n, 值为 val
reserve(size_type n)	将的vector的capacity更改为 n

b 空间增长问题 ***

vector为了方便管理空间,每次开辟的空间都比实际的容量要多并且不同的编译器和系统下,容量增长的倍数是不一样的. 一般是1.5倍到 2倍数

经过测试,我发现在VS2022中. 容量增长的倍数是1.5倍

在Linux (cent os) 中容量增长是2倍

测试代码和结果如下:

vector容量增长倍数经过测试在Windows下(VS2022)中是1.5倍

#include <iostream>
#include <vector>
using namespace std;int main()
{int capacity = 0;vector<int> arr;//不断插入数据并计算其容量，观察容量变化for (int i = 0; i < 100; i++){if (capacity != arr.capacity()){capacity = arr.capacity();cout << capacity << " ";}arr.push_back(i);}return 0;
}

运行结果如下:

可以看到容量的增长倍数是1.5倍

在VS2022查找vector的push_back源码, 可以看到下面这段代码

在Linux测试的结果如下:

vector每一次插入数据的时候,如果size < capacity 就会直接在后面插入数据.

如果size > capacity 那么vector就会重新开辟一份更大的空间,将原来是数据全部拷贝到新的空间中, 再去插入数据 .

测试代码:

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> arr;arr.push_back(1);printf("%p\n", &arr[0]); //1个数据打印arr[0]的地址arr.push_back(1);arr.push_back(1);arr.push_back(1);arr.push_back(1);printf("%p\n", &arr[0]); //5个数据打印arr[0]的地址return 0;
}

运行结果如下：可以看到其地址发生了改变

这说明, vector如果频繁的去push_back就会不断拷贝复制,导致效率降低

为了解决这种问题:我们使用vector的时候最好提前预估需要使用的容量, 并且使用resize或者reverse去设置好容量

2.4 vector的增删查改

学习STL容器基本都要掌握容器的增删查改和底层设计

vector常用增删插改如下:

容量操作	说明
push_back()	在vector尾部插入一个数据
pop_back()	在vector尾部删除一个数据
find()	在vector中查找一个数据,返回迭代器这个是STL算法提供的, vector内部没有
insert()	在输入的pos位置前面插入一个数据
erase()	在输入的pos位置删除一个数据
swap()	交换两个元素
operator[]	像数组一样可以访问和修改指定下标的元素

测试代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;void print(const vector<int>& arr)
{for (const auto& e : arr)cout << e << " ";cout << endl;
}int main()
{//增删查改vector<int> arr;arr.push_back(1); //1arr.push_back(2); //1 2 arr.pop_back();	  //1arr.push_back(3); //1 3arr.push_back(4); //1 3 4print(arr);		//结果应该为： 1 3 4auto pos = find(arr.begin(), arr.end(), 3);arr.insert(pos, 5);	//在3的前面插入5  1 5 3 4pos = find(arr.begin(), arr.end(), 4);arr.erase(pos);	//删除pos位置的4print(arr);	//结果应该为： 1 5 3return 0;
}

测试结果如下:

三. 使用vector出现的迭代器失效问题 *

3.1 增容导致迭代器失效

先看一份代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{vector<int> arr = { 1,2,3,4,5 };auto it = arr.begin();arr.push_back(6);arr.push_back(7);while (it != arr.end()){cout << *it << " ";it++;}return 0;
}

这份代码看着好像没啥问题,但是在运行之后去报错了!

经过调试之后,发现是迭代器非法访问

调试过程如下:

经过调试知道和vector增容的机制可以知道:

设置好一个迭代器后,vector如果发生了增容. 就会销毁旧空间,开辟新空间

而it仍然指向旧的空间, 这个一来*it就会非法访问.

所以我们使用push_back,insert,reverse,resize这些接口的时候.

要注意调用这些接口之前的迭代器不可使用.

调用接口之后要重新定义迭代器进行使用

3.2 erase导致迭代器失效

同样先看一份代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{//我们想要删除arr中的偶数vector<int> arr = { 1,2,3,4,5,6 };auto it = arr.begin();while (it != arr.end()){if ((*it) % 2 == 0){arr.erase(it);}it++;}for (const auto& e : arr)cout << e << " ";cout << endl;return 0;
}

我们想要删除偶数,运行的时候却崩溃了

经过简单分析:在我们删除数据之后，it就失效了

因为删除it之后，it指向的位置就不对了

可以看到报错

一般来说：我们解决迭代器失效的方法是对迭代器重新赋值

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>	//使用vector需要的头文件
using namespace std;int main()
{//我们想要删除arr中的偶数vector<int> arr = { 1,2,3,4,5,6 };auto it = arr.begin();while (it != arr.end()){if ((*it) % 2 == 0){//对迭代器重新赋值，erase删除数据后会返回删除数据后面一个数据的迭代器。//重新赋值之后就不会出错了！it = arr.erase(it);}else{it++; //为奇数，直接it增加}}for (const auto& e : arr)cout << e << " ";cout << endl;return 0;
}