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

Source

⭐本篇重点: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()
{
	//{}内部的数据可以看成为一个vector
	vector<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;

	//访问arr2
	for (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()
{
	//{}内部的数据可以看成为一个vector
	vector<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()
{
	//{}内部的数据可以看成为一个vector
	vector<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); //1
	arr.push_back(2); //1 2 
	arr.pop_back();	  //1

	arr.push_back(3); //1 3
	arr.push_back(4); //1 3 4
	print(arr);		//结果应该为: 1 3 4

	auto pos = find(arr.begin(), arr.end(), 3);
	arr.insert(pos, 5);	//在3的前面插入5  1 5 3 4
	pos = find(arr.begin(), arr.end(), 4);
	arr.erase(pos);	//删除pos位置的4
	print(arr);	//结果应该为: 1 5 3

	return 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;
}