C++ STL容器
课堂学习
一、stack(栈)
stack是一种后进先出(LIFO)的数据结构,只允许在容器的一端进行插入和删除操作。
常用函数
push()
: 将元素压入栈顶pop()
: 弹出栈顶元素(不返回该元素)top()
: 返回栈顶元素(不弹出)empty()
: 判断栈是否为空size()
: 返回栈中元素数量
示例代码
#include <iostream>
#include <stack>using namespace std;int main() {
stack<int> s;// 压入元素
s.push(10);
s.push(20);
s.push(30);// 查看栈顶元素
cout << "栈顶元素: " << s.top() << endl;// 输出30// 弹出元素
s.pop();
cout << "弹出后栈顶元素: " << s.top() << endl;// 输出20// 栈大小
cout << "栈大小: " << s.size() << endl;// 输出2// 判断栈是否为空
if (!s.empty()) {
cout << "栈不为空" << endl;
}return 0;
}
二、queue(队列)
基本介绍
queue是一种先进先出(FIFO)的数据结构,只允许在容器的一端插入元素,在另一端删除元素。
常用函数
push()
: 在队尾插入元素pop()
: 删除队首元素(不返回该元素)front()
: 返回队首元素back()
: 返回队尾元素empty()
: 判断队列是否为空size()
: 返回队列中元素数量
示例代码
#include <iostream>
#include <queue>using namespace std;int main() {
queue<string> q;// 入队
q.push("Alice");
q.push("Bob");
q.push("Charlie");// 查看队首和队尾
cout << "队首: " << q.front() << endl;// 输出Alice
cout << "队尾: " << q.back() << endl;// 输出Charlie// 出队
q.pop();
cout << "出队后队首: " << q.front() << endl;// 输出Bob// 队列大小
cout << "队列大小: " << q.size() << endl;// 输出2// 判断队列是否为空
if (!q.empty()) {
cout << "队列不为空" << endl;
}return 0;
}
三、vector(动态数组)
基本介绍
vector是可以动态改变大小的数组,支持随机访问,在尾部插入和删除效率高。
常用函数
push_back()
: 在尾部插入元素pop_back()
: 删除尾部元素size()
: 返回元素数量empty()
: 判断是否为空operator[]
或at()
: 访问指定位置元素front()
: 返回首元素back()
: 返回尾元素begin()
: 返回指向首元素的迭代器end()
: 返回指向尾后位置的迭代器insert()
: 在指定位置插入元素erase()
: 删除指定位置或范围的元素clear()
: 清空所有元素resize()
: 改变vector大小reserve()
: 预留存储空间
示例代码
#include <iostream>
#include <vector>using namespace std;int main() {
vector<int> v = {1, 2, 3};// 尾部插入
v.push_back(4);
v.push_back(5);// 访问元素
cout << "第二个元素: " << v[1] << endl;// 输出2
cout << "第三个元素: " << v.at(2) << endl;// 输出3// 遍历vector
cout << "vector元素: ";
for (int num : v) {
cout << num << " ";
}
cout << endl;// 输出1 2 3 4 5// 删除尾部元素
v.pop_back();
cout << "删除后尾部元素: " << v.back() << endl;// 输出4// 插入元素
v.insert(v.begin() + 2, 10);// 在第三个位置插入10
cout << "插入后vector: ";
for (int num : v) {
cout << num << " ";
}
cout << endl;// 输出1 2 10 3 4// 删除元素
v.erase(v.begin() + 1);// 删除第二个元素
cout << "删除后vector: ";
for (int num : v) {
cout << num << " ";
}
cout << endl;// 输出1 10 3 4// 大小和容量
cout << "大小: " << v.size() << ", 容量: " << v.capacity() << endl;return 0;
}
四、竞赛常用扩展容器
1. priority_queue(优先队列)
基本介绍
priority_queue是一个优先级队列,默认情况下元素按从大到小排列(大顶堆)。
常用函数
与queue类似,但top()
返回的是优先级最高的元素。
示例代码
#include <iostream>
#include <queue>using namespace std;int main() {
// 默认大顶堆
priority_queue<int> pq;pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);while (!pq.empty()) {
cout << pq.top() << " ";// 输出50 30 20 10
pq.pop();
}
cout << endl;// 小顶堆
priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(50);
min_pq.push(20);while (!min_pq.empty()) {
cout << min_pq.top() << " ";// 输出10 20 30 50
min_pq.pop();
}return 0;
}
2. deque(双端队列)
基本介绍
deque支持在两端高效插入和删除元素,同时支持随机访问。
常用函数
除了vector的操作外,还增加了:
push_front()
: 在头部插入元素pop_front()
: 删除头部元素
示例代码
#include <iostream>
#include <deque>using namespace std;int main() {
deque<int> dq = {2, 3, 4};// 两端操作
dq.push_front(1);// 头部插入
dq.push_back(5);// 尾部插入cout << "双端队列: ";
for (int num : dq) {
cout << num << " ";// 输出1 2 3 4 5
}
cout << endl;dq.pop_front();// 删除头部
dq.pop_back();// 删除尾部cout << "操作后双端队列: ";
for (int num : dq) {
cout << num << " ";// 输出2 3 4
}return 0;
}
3. set/multiset
基本介绍
set是有序不重复集合,multiset是有序可重复集合,基于红黑树实现。
常用函数
insert()
: 插入元素erase()
: 删除元素find()
: 查找元素count()
: 统计元素出现次数lower_bound()
: 返回第一个不小于给定值的迭代器upper_bound()
: 返回第一个大于给定值的迭代器
示例代码
#include <iostream>
#include <set>using namespace std;int main() {
set<int> s;// 插入元素
s.insert(30);
s.insert(10);
s.insert(20);
s.insert(10);// 重复元素不会被插入// 遍历set
cout << "set元素: ";
for (int num : s) {
cout << num << " ";// 输出10 20 30
}
cout << endl;// 查找元素
if (s.find(20) != s.end()) {
cout << "20在set中" << endl;
}// multiset允许重复
multiset<int> ms;
ms.insert(10);
ms.insert(10);
cout << "10出现次数: " << ms.count(10) << endl;// 输出2return 0;
}
4. map/multimap
基本介绍
map是键值对的有序集合,键唯一;multimap允许键重复。
常用函数
与set类似,但操作的是键值对。
示例代码
#include <iostream>
#include <map>
#include <string>using namespace std;int main() {
map<string, int> score;// 插入键值对
score["Alice"] = 90;
score["Bob"] = 85;
score["Charlie"] = 95;// 遍历map
cout << "成绩单:" << endl;
for (auto& p : score) {
cout << p.first << ": " << p.second << endl;
}// 查找元素
if (score.find("Bob") != score.end()) {
cout << "Bob的成绩: " << score["Bob"] << endl;
}// 使用count检查键是否存在
cout << "David存在吗? " << (score.count("David") ? "是" : "否") << endl;return 0;
}
5. unordered_set/unordered_map
基本介绍
基于哈希表的无序集合和映射,查找效率更高但不保持元素顺序。
常用函数
与set/map类似,但不支持lower_bound()
和upper_bound()
。
示例代码
#include <iostream>
#include <unordered_map>
#include <string>using namespace std;int main() {
unordered_map<string, int> word_count;
word_count["hello"] = 3;
word_count["world"] = 2;
word_count["cpp"] = 5;// 遍历unordered_map (顺序不确定)
cout << "单词计数:" << endl;
for (auto& p : word_count) {
cout << p.first << ": " << p.second << endl;
}// 查找效率高
cout << "hello出现次数: " << word_count["hello"] << endl;return 0;
}
6. bitset
基本介绍
固定大小的位序列,用于高效处理二进制位操作。
常用函数
set()
: 设置位reset()
: 清除位flip()
: 翻转位test()
: 访问位count()
: 统计置1的位数any()
: 判断是否有位被置1none()
: 判断是否所有位都是0
示例代码
#include <iostream>
#include <bitset>using namespace std;int main() {
bitset<8> bs;// 8位,全0bs.set(2);// 第2位置1
bs.set(5);// 第5位置1cout << "bitset: " << bs << endl;// 输出00100100// 访问位
cout << "第2位: " << bs.test(2) << endl;// 输出1// 翻转所有位
bs.flip();
cout << "翻转后: " << bs << endl;// 输出11011011// 统计1的个数
cout << "1的个数: " << bs.count() << endl;return 0;
}
课堂训练
2857 小括号问题
描述
假设表达式中只允许包含一种括号:圆括号,需要成对出现。即(( ))或(( )( ))等为正确的格式,(( )或 ( ))或(((均为不正确的格式。
给定一串括号输入(换行作为结束符),检测格式是否正确,若正确输出YES;错误输出NO。
(括号数量≤100)
输入描述
无
输出描述
无
样例输入 1
(())
样例输出 1
YES
#include<bits/stdc++.h>
using namespace std;
int main() {char a[101];cin >> a;stack<char> s; int len = strlen(a);for (int i = 0; i < len; i++) {if (a[i] == '(') {s.push(a[i]);} else {if (!s.empty() && s.top() == '(') {s.pop(); } else {cout << "NO";return 0;}}}if (s.empty()) {cout << "YES";} else {cout << "NO";}return 0;
}
1628 排队问题
描述
有 n 个人排队,每个人有一个编号 i( 1 ≤ i ≤ n ),从左往右“ 1,2,1,2,…”报数,报到“ 1 ”的人出列,数到“ 2 ”的人立即占到队伍的最右端。报数过程反复进行,直到 n 个人都出列为止。已知 n个人原来的顺序,请写出他们的出列顺序。
输入描述
第一行为 n( n≤100 ),第二行为 n 个编号 i( 1≤i≤n),且 i 不会重复。
输出描述
一行,为他们的出列编号。
样例输入 1
8
1 2 3 4 5 6 7 8
样例输出 1
1 3 5 7 2 6 4 8
样例输入 2
4
2 5 1 3
样例输出 2
2 1 5 3
#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int main(){int n,num;cin>>n;int a[n+5];for(int i=1;i<=n;i++){cin>>a[i];q.push(a[i]);}int k=1;while(q.empty()!=1){if(k%2==1){cout<<q.front()<<' ';q.pop();}else{q.push(q.front());q.pop();}k++;}
}
3307 去掉重复数字
描述
有n个数字组成一组序列,现在要求删除重复出现的数字,使每个数字x只出现一次,输出删除重复数字后数组的新长度。
注意:用vector存储序列。
输入描述
两行,第一行表示序列中数字个数n(1 < n ≤ 106)。
第二行,n个数字,每个数字之间空格分隔(1<x ≤ 1018)。
输出描述
一行,表示删除重复数字后数组的新长度。
样例输入 1
7
0 1 3 1 3 6 1234567890
样例输出 1
5
#include <bits/stdc++.h>
using namespace std;
vector<long long> v;
int main() {int n;cin>>n;long long m;for(int i=1;i<=n;i++){cin>>m;v.push_back(m);}sort(v.begin(),v.end());int ans=1;for(int i=0;i<=v.size()-2;i++){if(v[i]!=v[i+1])ans++;}cout<<ans;return 0;
}
6988 出栈序列
描述
有5个不同的整数,按读入顺序入栈,再给一个可能的出栈顺序,请你编写一个程序检查出栈顺序是否合理,如果不合理请输出“no”,如果合理,请输出“yes”。
输入描述
第一行输入5个整数,表示顺序入栈的数字。
第二行输入5个整数,表示可能出栈的数字顺序。
输出描述
一行字符串,“no”或者“yes”。
样例输入 1
3 6 2 5 4
2 6 3 5 4
样例输出 1
yes
#include<bits/stdc++.h>
using namespace std;
stack<int>s;
int a[5],b[5];
int main(){for(int i=0;i<5;i++){cin>>a[i];}for(int i=0;i<5;i++){cin>>b[i];}int num=0;for(int i=0;i<5;i++){s.push(a[i]);while(!s.empty()&&s.top()==b[num]){s.pop();num++;}}if(s.empty()){cout<<"yes";}else{cout<<"no";}return 0;
}