LCY算法培训-进阶班-第1讲（STL在竞赛中的应用）

本文最后更新于：December 3, 2021 pm

2021杭电ACM-LCY算法培训进阶班知识总结。STL在竞赛中的应用PPT内容整理。、、

知识目录

相关头文件

1
#include<bits/stdc++.h>//万能头文件

迭代器

1.队列(queue)

1）特点
1
2
3
1.先进先出(FIFO)
2.从队头删除元素
3.在队尾加入元素
2）常见操作
1
2
3
创建队列对象
queue<元素类型> 队列名;
queue<int> qq;
1
2
3
1.判断队列是否为空
队列名.empty();
qq.empty();
1
2
3
2.查询队列大小
队列名.size();
qq.size();
1
2
3
3.访问队首元素
队列名.front();
qq.front();
1
2
3
4.访问队尾元素
队列名.back();
qq.back();
1
2
3
5.加入元素(在队尾加入)
队列名.push(元素名);
qq.push();
1
2
3
6.删除元素(在队首删除)
队列名.pop();
qq.pop();
3）实例
1
2
3
4
5
6
7
8
9
10
int a,b,c,d;
queue<int> qq;
qq.push(1);
qq.push(3);
qq.push(4);
qq.pop();
a=qq.front();//a=1
b=qq.back();//b=3
c=qq.size();//c=2
d=qq.empty();//d=0

2.优先队列(priority_queue)

1）特点
1
2
3
4
1.在队尾加入元素
2.从队头删除元素
3.每次取出的是具有最高优先权的元素(不一定先进先出)
4.内部的本质是用堆实现的
2）常见操作
1
2
3
创建队列对象
priority_queue<元素类型> 队列名;
priority_queue<int> qq;
1
2
1.判断队列是否为空
队列名.empty();
1
2
2.查询队列大小
队列名.size();
1
2
3.返回优先权最高的元素
队列名.push();
1
2
4.加入元素
队列名.push();
1
2
5.删除元素(删除第一个元素)
队列名.pop();
1
2
6.访问最优元素
队列名.top();
3）实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int main(){
    priority_queue<int> q;
    int t,a=2,b=5,c=3;
    q.push(a); q.push(b); q.push(c);
    while(!q.empty()){
        t=q.top();
        q.pop();
        cout<<t<<endl;//printf("%d\n",t);
    }
    return 0;
}
//结果
5
3
2

3.栈(stack)

1）特点
1
2
3
1.先进后出(FILO)
2.从栈顶删除元素
3.从栈顶加入元素
2）常见操作
1
2
3
创建栈对象
stack<元素类型> 栈名;
stack<int> st;
1
2
1.判断栈是否为空
栈名.empty();
1
2
2.查询栈大小
栈名.size();
1
2
3.访问栈顶元素 //要先确保栈非空
栈名.top();
1
2
4.栈顶加入元素
栈名.push(元素名);
1
2
5.删除栈顶元素
栈名.pop();

说明

1
栈和队列一样，没有clear之类的函数，如果想要清空一个栈，需要循环调用出栈函数
3）实例
1
2
3
4
5
6
7
8
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop();
cout<<s.top()<<endl; //2
s.top()+=3;
cout<<s.top()<<endl; //5

4.向量，动态数组(vector)

1)向量的定义
1
2
vector<元素类型> 向量名;
vector<int> a;
2）向量初始化
1
2
3
vector<int> abc;//初始化一个size为0的vector，也是最常用的
vector<int> abc(10);//初始化了10个默认值为0的元素
vector<int> abc(10,1);//初始化了10个值为1的元素
3）向量的常见操作
1
2
1.取向量首元素的迭代器
向量名.begin();
1
2
2.取向量尾元素下一地址
向量名.end();//不是最后一个元素，而是最后一个元素的下一个位置。begin和end可以理解成区间中的前闭后开，即[a.begin,a.end),这个区间包括了向量a中的全部元素
1
2
3.取向量首元素的值
向量名.front();
1
2
4.取向量尾元素的值
向量名.back();
1
2
5.下标形式访问
int a=向量名[t];//类似普通数组的访问操作，其中t可以为任何数，但不能超出向量中实际的个数
1
2
6.往尾部添加一个元素
向量名.push_back(值);//最常见操作
1
2
7.删除尾部第一个元素
向量名.pop_back();
1
2
8.判断向量是否为空
向量名.empty();
1
2
9.求向量中元素的个数
向量名.size();//实际元素的个数，不是容量
1
2
10.翻转向量
reverse(a.begin() , a.end());//a为向量名
4）向量的经典应用
1
2
3
4
5
6
7
1.邻接表
struct edge{int from,to,value;}
const int maxn=1e5;
vector<edge> Map[maxn];//一维向量相当于二维数组
若用普通二维数组存邻接表，会造成极大浪费(超内存)
//初始化，clear函数是清空向量，不是变成0
for(int i=0;i<maxn;++i) Map[i].clear();

5.集合(set)

数学上的集合的三个特征
1
2
3
1.确定性(任一元素必须是确定属于或不属于某个集合)
2.互异性(集合中的元素互不相同)
3.无序性(集合中的元素没有先后之分)
1）特点
1
set的含义就是集合，是一个有序的，没有相同元素的容器，且里面的元素都是排序好的，支持插入，删除，查找等操作，所有的操作都是严格在logn时间内完成，效率非常高
2）常见操作
1
2
1.set的声明
set<int> s;
1
2
2.set的清空
s.clear();
1
2
3.插入一个元素x
s.insert(x);//如果集合中之前没有此元素，则成功插入并自动排序，否则不插入
1
2
4.查询有否元素x
int hav = s.count(x); //有则返回1，无则返回0
1
2
5.查找x并返回迭代器
set<int>::iterator it = s.find(x);
1
2
6.判断是否为空集
bool isempty = s.empty();//若为空集则返回真，否则返回假
1
2
7.求集合元素个数
int n = s.size();
1
2
8.删除元素x
s.erase(x);
3）用法注意
1
2
3
4
5
6
7
8
9
1.set最主要用途：自动去重并按升序排序
2.如若对set中的元素降序排序，则
set声明
    set<int,greater<int> > st;
迭代器也随之改变
    set<int,greater<int> >::iterator it;
如若int类型改为结构体时，排序就在结构体中加载小于符号
3.set只能通过迭代器(iterator)访问
4.set不支持 it < st.end() 的写法，可写成 it != st.end()

6.string类

1）string对象的声明
1
2
1.string str;
2.string strl="qwertyuui";
2）求string对象的长度
1
2
3
string strTest="test";
1. strTest.length(); //结果为4
2. strTest.size(); //结果为4
3）string对象的连接
1
可以使用+和+=运算符对string对象执行字符串的连接操作(还有append成员函数实现字符串连接，忽略之)
4）string对象的比较
1
可以用 <、<=、==、!=、>=、> 运算符比较string对象(还有compare成员函数用于比较字符串，忽略之)
5）求string对象的字串
1
2
3
4
5
substr 成员函数可以用于求字串(n,m)
调用时，如果省略m或者m超过了字符串的长度，则求出来的字串就是从下标n开始一直到字符串结束的部分
string s1="this is ok";
1.string s2=s1.substr(2,4); //s2="is i"
2.s2=s1.substr(2);// s2="is is ok"
6）插入字符串
1
2
3
4
5
insert 成员函数可以在string对象中插入另一个字符串，返回值为对象自身的引用
string s1("Limitless"), s2("00");
1. s1.insert(2,"123"); //"Li123mitless"
2. s1.insert(3,s2); //s1="Li10023mitless"
3. s1.insert(3,5,'x');//s1="Li1xxxxx0023mitless"
7）删除字串
1
2
3
4
erase 成员函数可以删除string对象中的字串，返回值为对象自身的引用
string s1("Real Steel");
1. s1.erase(1,3);//s1="R Steel"
2. s1.erase(5);//s1="R Ste"
8）交换两个string对象的内容
1
2
3
swap成员函数可以交换两个string对象的内容
string s1("West"),s2("East");
s1.swap(s2);//s1="East",s2="West"
9）字符串的查找操作
1
2
3
4
5
6
string str="The apple thinks apple is delicious"; //长度34
string key="apple";
1. int pos1=str.find(key);//4
    s.find(str),查找字符串str在当前字符串s中第一次出现的位置
2. int pos2=str.find(key,10);//17
    s.find(str,pos),查找字符串str在当前字符串s的[pos,end]中第一次出现的位置，即从pos开始到字符串的最后，str第一次出现的位置
10）用STL算法操作string对象
1
2
3
4
5
6
7
string s("afgcbed");
sort(s.begin(),s,end());
cout<<s<<endl;//输出abcdefg
next_permutation(s.begin(),s,end());
cout<<s<<endl;//输出abcdegf
reverse(s.begin(),s,end());
cout<<s<<endl;//fgedcba
11）String其他有用函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1. 截取子串
       s.substr(pos, n)    截取s中从pos开始（包括0）的n个字符的子串，并返回
       s.substr(pos)        截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回
2. 替换子串
       s.replace(pos, n, s1)    用s1替换s中从pos开始（包括0）的n个字符的子串
3. 查找子串
       s.find(s1)         查找s中第一次出现s1的位置，并返回（包括0）
       s.rfind(s1)        查找s中最后次出现s1的位置，并返回（包括0）
       s.find_first_of(s1)       查找在s1中任意一个字符在s中第一次出现的位置，并返回（包括0）
       s.find_last_of(s1)       查找在s1中任意一个字符在s中最后一次出现的位置，并返回（包括0）
       s.fin_first_not_of(s1)         查找s中第一个不属于s1中的字符的位置，并返回（包括0）
       s.fin_last_not_of(s1)         查找s中最后一个不属于s1中的字符的位置，并返回（包括0）
       
4.string转换成char*字符串
1) .data();
如：
string str="abc";
char*p=(char*)str.data();

2) .c_str();
如：
string str="adcd";
char *p=(char*)str.c_str();

7.映射(map)

1）特点
1
2
map是一个键值对(key/value)容器，对于迭代器来说，可以修改value，而不能修改key。Map会根据key自动排序
map类型通常可理解为关联数组：可使用键作为下标来获取一个值。关联的本质在于：元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取
2）常见操作
1
2
1.map的定义
map<int,string> m;//定义一个空map m;
1
2
2.返回m中键值等于k的元素的个数(1或0)
m.count(k);
1
2
3.查找元素
m.find(k);//存在则返回指向该元素的迭代器，否则返回结束地址end()
1
2
4.删除元素
m.erase(k);//删除m中键为k的元素，返回删除元素的个数(1或0)
1
2
5.删除迭代器指向的元素
m.erase(p);//从m中删除迭代器p所指向的元素
1
2
6.插入元素
m.insert(e);//e是一个用在m上的value_type类型的值(一个pair)。如果键e.first不在m中，则插入一个值为e.second的新元素；如果该键在m中已存在，那么不进行任何操作
1
2
7.清空元素
m.clear();//清空m

8.STL中的算法

1）全排序(next_permutation)
1
2
3
4
5
6
7
通常用于生成序列的全排列
int a[]={1,2,3};
do{
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
}while(next_permutation(a,a+3))
1.若当前调用排序已经达到最大字典序，比如321，则函数返回false;
2.修改函数的参数，比如(a,a+2),则可以只对部分长度全排列
1
2
3
4
next_permutation是如何生成序列的全排列？
1.从最右边开始，两两比较相邻的元素，直至找到右边比左边大的一对，左边那个就是将要被替换的，再从最右边开始找比这个元素大的第一个，交换他们两个.
2.交换之后，翻转交换元素的后面的所有元素
3.比如：1 3 4 6 5 2 => 1 3 5 6 4 2 => 1 3 5 2 4 6
2021杭电ACM-LCY算法培训进阶班

本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/3325278709.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！