【STL】 vector

#include <vector>

连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

构造

vector<类型> arr(长度, [初值])

时间复杂度：O(n)

常用的一维和二维数组构造示例，高维也是一样的（就是会有点长）。

vector<int> arr;         // 构造int数组
vector<int> arr(100);    // 构造初始长100的int数组
vector<int> arr(100, 1); // 构造初始长100的int数组，初值为1

vector<vector<int>> mat(100, vector<int> ());       // 构造初始100行，不指定列数的二维数组
vector<vector<int>> mat(100, vector<int> (666, -1)) // 构造初始100行，初始666列的二维数组，初值为-1

构造二维数组的奇葩写法，千万别用：

vector<int> arr[100];         // 正确，构造初始100行，不指定列数的二维数组，可用于链式前向星存图
vector<int> arr[100](100, 1); // 语法错误！
vector<int> arr(100, 1)[100]; // 语法错误！
vector<int> arr[100] {{100, 1}, 这里省略98个 ,{100, 1}}; // 正确但奇葩，使用列表初始化

尾接 & 尾删

• .push_back(元素)：在 vector 尾接一个元素，数组长度 +1+1.
• .pop_back()：删除 vector 尾部的一个元素，数组长度 −1

// init: arr = []
arr.push_back(1);
// after: arr = [1]
arr.push_back(2);
// after: arr = [1, 2]
arr.pop_back();
// after: arr = [1]
arr.pop_back();
// after: arr = []

中括号运算符

和一般数组一样的作用

时间复杂度：O(1)

获取长度

.size()

获取当前 vector 的长度

时间复杂度：O(1)

清空

.clear()

清空 vector

时间复杂度：O(n)

判空

.empty()

如果是空返回 true 反之返回 false.

时间复杂度：O(1)

改变长度

.resize(新长度, [默认值])

修改 vector 的长度

• 如果是缩短，则删除多余的值
• 如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）

时间复杂度：O(n)

总结：

初始化：vector<int> result(nums.size(), 0);
1.push_back   将数据放入vector中
2.pop_back    去掉末尾元素
3.at                得到对应下标的元素
4.begin           得到数组头的指针
5.end             得到数组的最后一个单元+1的指针
6．front         返回数组第一个元素
7.back           返回最后一个元素
8.max_size     得到vector最大可以是多大
9.capacity       当前vector分配的大小
10.size           当前使用数据的大小
11.resize         改变当前使用数据的大小，如果它比当前使用的大，则填充默认值
12.reserve      改变当前vecotr所分配空间的大小
13.erase         删除指针指向的数据项
14.clear          清空当前的vector
15.rbegin        将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend          将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty        判断vector是否为空
18.swap         与另一个vector交换数据

vector<int>::iterator 迭代器名;     常用于遍历vector

注意事项

提前指定长度

如果长度已经确定，那么应当直接在构造函数指定长度，而不是一个一个 .push_back(). 因为 vector 额外内存耗尽后的重分配是有时间开销的，直接指定长度就不会出现重分配了。

// 优化前: 522ms
vector<int> a;
for (int i = 0; i < 1e8; i++)
    a.push_back(i);
// 优化后: 259ms
vector<int> a(1e8);
for (int i = 0; i < a.size(); i++)
    a[i] = i;

遍历操作：

迭代器介绍：
迭代器是一种检查容器内元素并遍历元素的数据类型。c++更趋向于使用迭代器而不是下标操作，因为标准库为每一种标准容器（如vector）定义了一种迭代器类型，而只有少数容器（如vector）支持下标操作访问容器元素。

为何需要迭代器？

很多数据结构并不是线性的（例如红黑树），对于非线性数据结构，下标是无意义的。无法使用下标来遍历整个数据结构。

迭代器的作用就是定义某个数据结构的遍历方式，通过迭代器的增减，代表遍历到的位置，通过迭代器便能成功遍历非线性结构了。

例如，set 的实现是红黑树，我们是没法用下标来访问元素的。但是通过迭代器，我们就能遍历 set 中的元素了：

迭代器变量：

vector<int>::iterator iter

遍历：

    // 创建空的 vector 容器
    std::vector<int> vec{1, 2, 3};

    // 遍历打印 vector 容器的内容 
    for (int i = 0; i < vec.size(); i++) {
        std::cout << vec[i] << ' ';
    }
    std::cout << std::endl;

    // 通过迭代器遍历数组
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;

关于vector<pair<int,int> >

power.emplace_back(make_pair(1,1));
power.emplace_back(2,2);

	//遍历输出
	for(int i=0;i<power.size();i++){
		cout<<power[i].first<<","<<power[i].second<<endl;
	}

	//使用迭代器也可以遍历输出
	vector<pair<int,int> > ::iterator iter; //访问vector
	for(iter=power.begin();iter!=power.end();iter++)
	{
	 	cout<<iter->first<<","<<iter->second<<endl;
	}