当前位置: 首页 > ai >正文

C++ STL容器

课堂学习

一、stack(栈)

stack是一种后进先出(LIFO)的数据结构,只允许在容器的一端进行插入和删除操作。

常用函数

  1. push(): 将元素压入栈顶
  2. pop(): 弹出栈顶元素(不返回该元素)
  3. top(): 返回栈顶元素(不弹出)
  4. empty(): 判断栈是否为空
  5. 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)的数据结构,只允许在容器的一端插入元素,在另一端删除元素。

常用函数

  1. push(): 在队尾插入元素
  2. pop(): 删除队首元素(不返回该元素)
  3. front(): 返回队首元素
  4. back(): 返回队尾元素
  5. empty(): 判断队列是否为空
  6. 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是可以动态改变大小的数组,支持随机访问,在尾部插入和删除效率高。

常用函数

  1. push_back(): 在尾部插入元素
  2. pop_back(): 删除尾部元素
  3. size(): 返回元素数量
  4. empty(): 判断是否为空
  5. operator[]at(): 访问指定位置元素
  6. front(): 返回首元素
  7. back(): 返回尾元素
  8. begin(): 返回指向首元素的迭代器
  9. end(): 返回指向尾后位置的迭代器
  10. insert(): 在指定位置插入元素
  11. erase(): 删除指定位置或范围的元素
  12. clear(): 清空所有元素
  13. resize(): 改变vector大小
  14. 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(): 判断是否有位被置1
  • none(): 判断是否所有位都是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;
}
http://www.xdnf.cn/news/15791.html

相关文章:

  • 金融大前端中的 AI 应用:智能投资顾问与风险评估
  • 【Nature Communications】GaN外延层中位错辅助的电子和空穴输运
  • 0401聚类-机器学习-人工智能
  • nvm、npm、pnpm、cnpm、yarn
  • 《深入C++多态机制:从虚函数表到运行时类型识别》​
  • 数据并表技术全面指南:从基础JOIN到分布式数据融合
  • Spring Boot 自动装配用法
  • Materials Studio学习笔记(二十九)——尿素的几何优化
  • 树同构(Tree Isomorphism)
  • [特殊字符] 小程序 vs 智能体:下一代应用开发,谁主沉浮?
  • 【Java项目安全基石】登录认证实战:Session/Token/JWT用户校验机制深度解析
  • 基于自定义数据集微调SigLIP2-分类任务
  • PDF 编辑器:多文件合并 拆分 旋转 顺序随便调 加水印 密码锁 页码背景
  • [学习] 深入理解傅里叶变换:从时域到频域的桥梁
  • vscode环境下c++的常用快捷键和插件
  • 嵌入式通信DQ单总线协议及UART(一)
  • Linux练习二
  • 鸿蒙蓝牙通信
  • [AI风堇]基于ChatGPT3.5+科大讯飞录音转文字API+GPT-SOVITS的模拟情感实时语音对话项目
  • 字节跳动开源Seed-X 7B多语言翻译模型:28语种全覆盖,性能超越GPT-4、Gemini-2.5与Claude-3.5
  • 关于Vuex
  • GeoPandas 城市规划:Python 空间数据初学者指南
  • 零基础 “入坑” Java--- 十二、抽象类和接口
  • ndexedDB 与 LocalStorage:全面对比分析
  • aosp15实现SurfaceFlinger的dump输出带上Layer详细信息踩坑笔记
  • EP01:【Python 第一弹】基础入门知识
  • Vue rem回顾
  • 文档表格标题跑到表格下方,或标题跟表格空隔太大如何处理
  • Java无服务架构新范式:Spring Native与AWS Lambda冷启动深度优化
  • Flutter基础(前端教程①⑤-API请求转化为模型列成列表展示实战)