信息奥赛｜STL｜vector
vector 简介 🚀
vector 是标准模板库（STL）中的一种 动态数组 容器，存储同一种特定类型的元素。
vector 支持通过索引进行快速随机访问元素，随机存取任何元素都能在常数时间完成，在尾端增删元素时具有较佳的性能。
vector 详解 ☘️
vector 头文件
#include <vector> 🍉PS：竞赛中建议直接使用万能头文件
#include<bits/stdc++.h>
vector 初始化
vector<int> v; //初始化vector v
vector<int>::iterator it; //初始化vector的迭代器 it
vector<int> v[5]; //初始化一个二维的vectorvector 添加元素
for (int i = 0; i < n; ++i) {
cin >> tmp;
v.push_back(tmp); //vector通过push_back()的方式，向尾部添加元素
}vector 元素访问
单个元素访问
访问首部元素
cout << "首部元素为：" << v.front() << endl; //v.front()返回首部元素值 cout << "首部元素为：" << *v.begin() << endl; //v.begin()返回首部元素地址 cout << "首部元素为：" << v[0] << endl; //vector支持下标随机访问访问第
k(1<=k<=v.size())个元素cout << "第k个元素为：" << *(v.begin() + k - 1) << endl; cout << "第k个元素为：" << v[k - 1] << endl;🍉PS：
vector支持 随机访问（仅有vector和string支持随机访问），可以用(it + k)的方式改变迭代器的值；其他容器不支持随机访问，仅能用it++/it--的方式改变迭代器的值访问末尾元素
cout << "末尾元素为：" << *(--v.end()) << endl; //v.end()返回末尾元素的后一个位置 cout << "末尾元素为：" << v[v.size() - 1] << endl; //v的下标范围是[0,v.size()-1]🍉PS1：
vector没有v.back()方法来访问末尾元素；但是有v.front()方法来访问首部元素🍉PS2：
vector中的end()方法返回的是末尾元素的下一个位置的地址，故--v.end()返回末尾元素的地址，*(--v.end())返回末尾元素值。（🤔思考：*(v.end()--)能否输出末尾元素的值）
整体元素遍历
迭代器遍历
for (it = v.begin(); it != v.end(); it++) { cout << *it << " "; } cout << endl;下标法遍历
for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl;智能指针遍历（熟练后推荐）
for (auto t: v) { cout << t << " "; } cout << endl;
vector 元素查找（不推荐）
vector 可以通过使用 find() 函数来查找某个元素，若找到，则返回当前元素的迭代器；若找不到，返回 v.end()。
find() 函数查找 vector 中元素的时间复杂度为 $O(N)$ 。（不推荐 😵💫）
而 set、map 等容器自带 find() 方法，查找的时间复杂度仅为 $O(logN)$ （推荐 ✅）
it = find(v.begin(), v.end(), tmp);
if (it != v.end()) {
cout << "当前vector中存在该元素" << endl;
} else {
cout << "当前vector中不存在该元素" << endl;
}vector 排序
元素为 int 类型
升序
sort(v.begin(),v.end());降序
使用
greater<int>()sort(v.begin(),v.end(),greater<int>());自定义排序参数
cmpbool cmp(int a,int b){ //定义cmp参数，比较int类型 return a>b; } sort(v.begin(),v,end(),cmp);
🍉PS：当元素为结构体时，直接定义结构体数组，然后用
sort()对结构体数组排序即可。
vector 反转
reverse(v.begin(), v.end()) //使用reverse函数反转当前vectorvector 常用方法函数
常用方法函数概览
| 方法 | 功能描述 | 时间复杂符 |
|---|---|---|
v.push_back(element) |
在末尾添加一个元素 | $O(1)$ |
v.pop_back() |
删除末尾元素 | $O(1)$ |
v.front() |
返回第一个元素值 | $O(1)$ |
v.size() |
返回当前 vector 中元素数量 |
$O(1)$ |
v.begin() |
返回首元素的迭代器（地址） | $O(1)$ |
v.end() |
返回 末尾元素后一个位置 的迭代器（地址） | $O(1)$ |
v.clear() |
清空当前 vector |
$O(N)$ |
v.empty() |
判断当前 vector 是否为空，为空返回真，反之返回假 |
$O(1)$ |
v.erase(it + k -1) |
删除第 k 个元素，it = v.begin() |
/ |
部分常用方法函数详解
v.push_back(element)
v.push_back(100); //将元素100插入vector末尾v.pop_back()
v.pop_back(); //删除当前末尾元素v.begin() / v.end()
vector<int>::iterator it;
for(it = v.begin();it!=v.end();it++){ //经常用于遍历vector
cout<<*it<<" "
}
cout<<endl;v.empty()
if(!v.empty()) ... //如果当前vector非空v.clear()
v.clear(); //清空当前vector🍉 PS：容器和容器适配器不同，
stack,queue等容器适配器不支持 clear() 方法，只能用 逐个出栈/队 的方式清空。
vector OI 案例 🧑🏻💻
OI 案例1
【题目描述】
实现一个线性表: 参照 sq_delete 函数，对一个 $n$ 不超过 $1024$ 的线性表进行删除操作。
【输入】
第一行有一个整数 $n$，表示线性表的大小，第二行有 $n$ 个整数，分别是 list1, list2 … listn 。
第三行有一个整数 $q$，表示 $q$ 次删除操作，接下来 $q$ 行，每行有一个整数 $k$，表示删除线性表中第 $k$ 个元素。
(输入有多组测试数据，以 EOF 结束）
【输出】
对于每次删除操作输出一行，如果 $k$ 不合法，输出 $-1$, 否则输出删除的元素。
【输入样例】
5
3 2 1 5 4
3
5
5
2【输出样例】
4
-1
2【题目分析】
本题使用 STL 容器，可以很大程度上简化代码。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
int n, q, tmp, id;
vector<int> v;
vector<int>::iterator it;
int main() {
while (cin >> n) {
v.clear(); //题目有多组样例，必须添加本行代码清空上一个v，否则会出错
for (int i = 0; i < n; ++i) {
cin >> tmp;
v.push_back(tmp);
}
cin >> q;
while (q--) {
cin >> id;
if (id < 1 || id > v.size()) {
cout << -1 << endl;
} else {
it = v.begin();
cout << *(it + id - 1)<<endl; //vector 支持随机访问
v.erase(it + id - 1);
}
}
}
return 0;
}
