常用STL容器
约 792 字大约 3 分钟
2025-03-18
vector
引入
我们都学习过数组和链表:
在使用数组时,我们可以利用下标快速访问数组中的元素,但是数组的长度固定。
在使用链表时,我们可以改变长度,但是不能便利地访问元素。
接下来,我们将学习一种新的容器,它兼具了数组和链表的特性。
定义
定义一个vector,你可以在里面放各种数据类型。
注意
需要添加vector头文件
vector<int> a;
vector<double> b;
struct T {};
vector<T> c;上面的定义中,并没有设置容器的大小,我们可以通过以下几种方式来控制容器的大小
int n = 5;
vector<int> a(n, 1); // 设置大小为 5 ,并初始化值为1,若不添加默认为0
vector<int> b = {2, 0, 0, 6, 0, 9, 1, 7};
// 可以用 size() 得到容器的大小
cout << a.size() << ' ' << b.size() << endl;
// 输出 5 8
// 可以用 resize() 改变容器大小
b.resize(2);
for (auto x : b) cout << x << ' ';
cout << endl;
// 输出 2 0注意
区分vector<int> a(n)与vector<int> a[n]。一个vector容器就可以作为一个数组。 而vector<int> a[n]相当于是vector的数组,由多个vector组成。
用作数组
vector可以当作数组使用,我们可以进行下标访问。
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 可以用这两种方法定义二维数组
auto b = vector(4, vector<int>(5));
vector<vector<int>> c(5, vector<int>(4));用作链表
vector可以当作链表使用,我们可以在链表头和尾插入元素。
vector<int> a;
for (int i = 1; i <= 5; i++) a.push_back(i);
// 我们在此进行下标访问,说明其同时具有链表和数组的特性
for (int i = 0; i < 5; i++) cout << a[i] << ' ';
cout << endl;
// 输出 1 2 3 4 5混合使用
vector<int> a = {1, 2, 3, 4};
// 在末尾追加元素
a.push_back(5);
for (auto x : a) cout << x << ' ';
cout << endl;
// 输出 1 2 3 4 5总结
vector的基础用法大致为以上这些(当然它还有很多其他很好用的功能)。
queue & stack
注意
需要添加queue&stack头文件
stack
后进先出
stack<int> s;
for (int i = 1; i <= 5; i++) {
s.push(i);
}
// 如果栈不为空,则循环继续
while (!s.empty()) {
int x = s.top();
s.pop();
cout << x << ' ';
}
// 输出 5 4 3 2 1queue
先进先出
queue<int> q;
for (int i = 1; i <= 5; i++) {
q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();
cout << x << ' ';
}
// 输出 1 2 3 4 5priority_queue
队首元素总是最大的
priority_queue<int> q;
vector<int> a = {1, 5, 3, 2, 4, 7};
for (auto x : a) {
q.push(x);
}
while (!q.empty()) {
int x = q.top();
cout << x << ' ';
q.pop();
}
// 输出 7 5 4 3 2 1队首元素总是最小的
priority_queue<int, vector<int>, greater<int>> q;拓展:常用算法
注意
需要添加algorithm头文件
sort
基于快速排序的混合排序(堆排序,插入排序),性能相当出色。
vector<int> a = {1, 5, 3, 2, 4, 7};
sort(a.begin(), a.end());
for (auto x : a) cout << x << ' ';
// 输出 1 2 3 4 5 7
sort(a.begin(), a.end(), greater<int>());
for (auto x : a) cout << x << ' ';
// 输出 7 5 4 3 2 1