C++标准模板库（STL）——vector的使用

1、 标准模板库中的vector

vector介绍文档

• std::vector是C++标准库中的动态数组容器，它可以像数组一样随机访问，同时又能根据元素数量动态调整大小，本质上就是数据结构中的顺序表
• vector和string高度相似，不过vector能够储存任意类型的数据，而string主要储存字符串
• 使用vector类时必须包含#include 头文件

接下来我会粗略地介绍vector类一些常用成员，同时为了讲解方便，本文先以储存int类型为例介绍常用接口，如果大家想了解更多，可以点开上面的链接查阅

vector的使用和string非常相似，所以本文将减少文字说明，多用代码介绍
string的使用

2、 vector的构造函数

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	/默认构造，创建空的vector
	vector<int> v1;

	/构造并初始化，创建10个3
	vector<int> v2(10, 3);
	/如果只写数量，默认初始化为0
	vector<int> v3(5);

	/通过迭代器区间初始化[begin,end)
	int arr[] = { 1,2,3,4,5 };
	vector<int> v4(arr, arr + 5);

	/拷贝构造
	vector<int> v5(v2);

	/初始化列表构造（C++11）
	vector<int> v6 = { 1,1,1,1,1 };
	return 0;
}

3、 vector中iterator的使用

iterator迭代器是C++容器的“通用访问接口”，所以vector使用iterator与string类似，都是通过begin和end遍历容器元素，使用算法

1. begin，返回指向字符串首字符的迭代器，是正向遍历字符的起始位置
2. end，返回指向字符串最后一个字符的下一个位置的迭代器，是正向遍历的结束标记，迭代器的范围为[begin,end)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	vector<int> v1 = { 1,2,3,4,5 };

	/用迭代器的begin，end遍历
	for (auto it = v1.begin(); it != v1.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	/用迭代器配合算法
	//降序排序
	/范围for 底层就是调用迭代器
	sort(v1.begin(), v1.end(), greater<int>());
	for (int it : v1)
	{
		cout << it << " ";
	}
	cout << endl;
	return 0;
}

4、 vector的容量空间操作

1） size

返回容器当前的元素个数

2） resize

主动改变容器元素的个数（改变size，可以增加/缩减）

3） capacity

返回容器当前已分配的内存能够容纳的元素个数（当前最多能存放的元素个数），vs下capacity是按1.5倍增长的，g++是按2 倍增长的。

4） empty

检测容器是否为空

5） reserve

请求修改容器的容量（改变capacity，不能缩小）

int main()
{
	vector<int> v1;
	cout << v1.size() << " " << v1.capacity() << endl;

	/初始化
	v1 = { 1,2,3,4,5 };
	cout << v1.size() << " " << v1.capacity() << endl;

	/将v1的size缩短为3
	v1.resize(3);
	cout << v1.size() << " " << v1.capacity() << endl;

	/将v1的size扩大为7，多出来的4个空间用2填充
	v1.resize(7, 2);
	cout << v1.size() << " " << v1.capacity() << endl;

	/请求扩容为100（capacity）
	v1.reserve(100);
	cout << v1.size() << " " << v1.capacity() << endl;
	
	return 0;
}

5、 vector增删改查

1) operator[]

返回容器中的第n个元素，可以像数组一样访问
const修饰后只能读取，不能修改

int main()
{
	/可以访问修改
	vector<int> v1 = { 1,2,3,4,5 };
	v1[1] = 9;
	cout << v1[1] << endl;/输出：9

	/只能访问
	const vector<int> v2 = { 1,2,3,4 };
	/v2[1] = 9;/“v2”: 不能给常量赋值
	cout << v2[1];/输出：2
	return 0;
}

2) push_back

在vector尾部添加一个元素

3）pop_back

删除vector的最后一个元素

4）insert

在指定位置插入元素

5) erase

在指定位置删除元素

6）swap

交换两个容器的内容

int main()
{
	vector<int> v1 = { 1,2,3 };

	/尾插
	/v1 = { 1,2,3,4 };
	v1.push_back(4);

	/尾删
	/v1 = { 1,2,3 };
	v1.pop_back();

	/在下标1处插入5
	/v1 = { 1,5,2,3 };
	v1.insert(v1.begin() + 1, 5);

	/删除下标2的元素
	/v1 = { 1,5,3 };
	v1.erase(v1.begin() + 2);

	/交换v1，v2的元素
	/v1={10,20,30 }；
	/v2={ 1,5,3 };
	vector<int> v2 = { 10,20,30 };
	v1.swap(v2);

	return 0;
}

7） 语法find(不是vector的接口)

• 在迭代器区间 [first, last) 中查找值为 val 的元素，返回指向该元素的迭代器；若未找到，返回容器的结束位置
• 使用时要包含头文件#include

#include<algorithm>
int main()
{
	vector<int> v = { 1,2,3,4 };

	/查找2
	auto it = find(v.begin(), v.end(), 2);
	if (it != v.end())
	{
		cout << "找到了" << *it << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
	return 0;
}

6、 迭代器失效问题

• 迭代器的底层是一个指针，或者是对指针进行了封装，比如vector的迭代器就是原生态指针T*。
• 所以迭代器失效，其实就是迭代器底层对应指针指向的空间被销毁了，使用这一块已经被释放的空间，就会导致程序崩溃

1） 插入元素导致失效

插入时触发扩容导致的失效

当插入元素后size>capacity时，空间不足，vector就会触发扩容。系统会分配一块更大的空间（按原容量的1.5或2倍扩充），并将原数据拷贝到新空间，释放旧空间。此时所有的迭代器、指针、引用都会失效，因为它们指向的内存已经被释放了

int main()
{
	vector<int> v1 = { 1,2,3,4 };

	/手动将空间容量设置为4
	/此时capacity=4，size=4
	v1.reserve(4);

	/让it等于v1首元素的迭代器
	auto it=v1.begin();

	/此时尾插，原空间已经满了，必须要扩容
	/旧空间被释放掉了，但it还指向旧空间
	/解引用it,就是访问野指针，程序会崩溃
	v1.push_back(5);
	/   *it = 1;

	return 0;

}

插入时未触发扩容导致的失效

如果插入数据空间还够用，没有触发扩容，那么只有插入位置以及后面的迭代器失效

int main()
{
	vector<int> v = { 1,2,3,4 };
	
	/手动将空间容量设置为20，保证空间够用，避免扩容
	v.reserve(20);
	
	/it1指向1，it2指向2
	auto it1 = v.begin();
	auto it2 = v.begin() + 1;

	/在数据2的位置插入数字5，（2345）都向后移动一位
	/原内存数据被更换
	v.insert(v.begin() + 1, 5);

	/it1未改变，还能用
	 *it1=1;
	/it2失效，原内存地址储存2，现在储存5
	/ *it2 = 2;
	return 0;
}

2） 删除元素导致失效

• erase删除pos指向的元素，pos以及pos之后的迭代器失效（元素往前移动导致地址变化），和插入未扩容情况类似
• pop_back删除尾元素，只有最后一个元素的迭代器失效

int main()
{
	vector<int> v = { 1,2,3,4 };

	/让it1指向结尾迭代器，尾删后，it1失效，解引用报错
	/it2不被波及，仍有效
	auto it1 = v.end();
	auto it2 = v.begin() + 1;
	v.pop_back();
	/  *it1;
	*it2;

	/此时删掉数字2，元素变为{1，3，4}
	/it2失效，*it2报错
	v.erase(v.begin() + 1);
	/ *it2;
	return 0;
}

3） 调整容器大小（resize）导致失效

resize(n),会改变size

• 当n>size时，需要插入新元素，和第一条pop_push插入元素导致迭代器失效同理。如果插入需要扩容，所有迭代器失效；如果未扩容，新增元素的迭代器失效
• 当n<size时，需要删除尾部元素，和第二条的pop_back同理,被删除的元素以及end的迭代器失效

4） 交换容器（swap）

swap(v1,v2)会交换数据信息，迭代器不会失效，但是导致双方的迭代器会互相指向，v1的迭代器指向v2的数据，v2的迭代器指向v1的数据

int main()
{
	vector<int> v1 = { 1,2 };
	vector<int> v2 = { 3,4 };
	auto it1 = v1.begin();/指向原v1
	auto it2 = v2.begin();/指向原v2

	/迭代器指向的内存地址，就相当于房子
	/v1,v2交换了房子,{1，2}房子现在属于v2,{3,4}房子现在属于v1
	/在之前的赋值中，it1，it2都是指向房子，所有即使房子主人换了
	/房子里的东西并没有改变，因此还是输出 1 3
	/迭代器的值没有变，但是归属权变了
	swap(v1, v2);
	cout << *it1 << endl;//1
	cout << *it2 << endl;//3

	/现在让it3,it4 通过各自的主人来指向房子，此时v1的房子是{3，4}
	/v2的房子是{1，2}，所以输出3，1
	/由此可见迭代器只在乎房子本身，只关心房子里面有什么，并不关心主人是谁
	auto it3 = v1.begin();
	auto it4 = v2.begin();
	cout << *it3 << endl;//3
	cout << *it4 << endl;//1
	
	return 0;
}

5） 清空容器导致失效（clear）

clear会删除所有元素，导致所有迭代器都失效

6） 解决迭代器失效

插入删除数据后导致当前迭代器失效的，要及时更新迭代器，做到在使用前，对迭代器重新赋值

int main()
{
	vector<int> v1 = { 1,2,3,4 };
	/指向2
	auto it1 = v1.begin() + 1;
	/插入8后，it1失效
	v1.insert(it1, 8);
	/重新获取迭代器，现在it1指向9，有效
	it1 = v1.begin() + 1;

	auto it2 = v1.begin() + 1;
	/删除9,导致此时it2失效
	/v1.erase(it2);
	/ *it2;

	/正确做法，用erase的返回值更新it2
	it2= v1.erase(it2);
	*it2;
	return 0;
}