写在开头
-
博客中算法的代码部分基本以C++来写，还未学到的同学可以花几分钟先大概了解一下
-
博客中所有算法的介绍分为知识点的部分以及对应算法题部分。
-
本文主要会介绍常用的STL容器（概念、适用环境、操作）以及STL中的几个实用算法。
STL（Standard Template Library）是C++的标准模板库，很多竞赛常用的数据结构、算法在STL中都有，熟练掌握能极大简化编程。
一、容器
STL的容器分为两类
①顺序式/序列容器（底层主要采用向量和链表）
②关联式/关联容器（底层主要采用平衡二叉搜索树结构）
有些操作是这些容器通用的
x.begin();//返回容器首个元素的迭代器
x.end();//*返回容器尾元素的后一个位置的迭代器
x.size();//返回容器元素数量
x.empty;//判断容器是否为空
x.clear();//删除所有元素，仅map、set、vector
接下来先具体介绍这两类中几种常见的容器。
1. 顺序式容器
顺序式容器主要包括vector、list、deque、queue、priority_queue、stack等
这里先具体介绍vector、stack以及queue。
1.1 vector——向量
vector向量是动态数组（可变长数组）：在运行时能根据需要自动改变数组大小。
支持随机访问，v[]
常用操作
/*1.定义vector<type>v */
#include <bits/stdc++.h>//万能头，包含<vector>
vector <int> v;
/*2.添加、插入*/
v.push_back(i);//加入至尾部
v.insert(v.begin() + i, value);//加入至v[i]
/*3.访问*/
//支持随机访问遍历
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
//迭代器遍历
for(auto it = vi.begin();it!=vi.end();it++)
cout<<*it<<' '<<endl;
/*4.删除*/
//弹出尾部
v.pop_back();
//删除某个迭代器的元素
auto it = v.find(value)
v.erase(it)
//*删除所有 v.clear();
v.erase (iterator first, iterator end)//*删除迭代器区间
题型
适合少量插入删除的题目（底层是连续空间的数组，不宜频繁移动）
经典题型：约瑟夫问题
拓展
思考频繁的插入删除的题目该如何做？
1.2 stack——栈
栈是一种先进后出的容器。（可以理解为泡腾片的拿入拿出）
栈顶添加，栈顶弹出
常用操作
/*1.定义stack<type> s */
#include <bits/stdc++.h>//万能头，包含<stack>
stack <int> s;
/*2.添加*/
s.push(key);//入栈至栈顶
/*3.访问*/
s.top();//只能访问栈顶
/*4.删除*/
s.pop()//只能弹出栈顶
题型
栈的题目特征比较明显：题意有先进后出意思即可
经典题型：模拟栈、反转字符串
逆波兰/后缀表达式
DFS
- hdu 1062 "Text Reverse"
- hdu 1237 "简单计算器"
拓展
由于栈要用空间存储，深度太大，会出现溢出，推荐手工写栈。
1.3 queue——队列
queue是一种先入先出的容器。
队尾添加，队首弹出
常用操作
/*1.定义queue <typename> q; */
#include <bits/stdc++.h>//万能头，包含<queue>
queue <int> q;
/*2.添加*/
q.push(key);//入队至队尾
/*3.访问*/
q.front();//访问队首
q.back();//访问队尾
/*4.删除*/
q.pop()//只能弹出队首
题型
队列的题目特征比较明显：题意有先进先出的意思即可
经典题型：模拟队列
BFS
- hdu 1702 "ACboy needs your help again"
2.关联式容器
关联式容器主要包括set、map、multiset、multimap。
这里先具体介绍set以及map。
2.1 set
set是一个自动实现无重且按一定规则排序的集合
常用操作
/*1.定义set <typename> s; */
#include <bits/stdc++.h>//万能头，包含<queue>
set <int> s;
/*2.添加*/
s.insert(value);//插入元素进集合（自动去重）
/*3.访问*/
//迭代器访问
for(auto it=s.begin();it!=s.end();it++){
cout<<*it<<endl;
}
/*4.删除*/
//删除某值
s.erase(value);
//删除某迭代器
s.erase(iterator it);
//删除某迭代器区间
s.erase (iterator first, iterator end);
/*5.查找*/
//查找值为value的迭代器find(value)
auto it=s.find(value);
//查找set中是否含有value
if(s.find(value) != s.end())
//可使用upper_bound()、lower_bound()等
题型
hdu 2094 "产生冠军"
2.2 map
map是一个无重有序的不同类型之间映射的集合
是一组键值对的组合，按键排序，键和值可以是任意的类型。
常用操作
/* 定义 map<typename1,typename2> mp; */
map<string, int> mp;
/* 添加 */
mp.insert(make_pair("haha",1));
mp("haha") = 1;
/* 访问键it->first 访问值it->second */
for(auto it=mp.begin();it!=mp.end();it++)
cout<<it->first<<" "<<it->second<<endl;
/* 查找 */
//查找键为key的迭代器
auto it = mp.find('a');
//可使用upper_bound()、lower_bound()等
/* 删除 */
//删除某个迭代器
mp.erase(iterator it)；
//删除所有
mp.clear()
题型
二、常用算法
1. lower_bound()、upper_bound()
lower_bound()、upper_bound()可以分别求出以数组中或容器中当前元素为下界/上界的下一个元素
但是前提是数组或容器本身已经是有序的！！【已排序的数组 或map以及set】
lower_bound(first, end, val)//找到有序容器或数组中第一个大于等于val的位置
upper_bound(first, end, val)//找到有序容器或数组中第一个小于等于val的位置
//first、end可以是容器的迭代器，或者数组的地址
2. next_permulation（）
next_permulation()——生成比当前数组/字符串排列大的下一个排列
next_permulation(a,a+n);//根据数组a的排列找出下一个比它排列大的数组，并更新a
next_permulation(s.begin(),s.end());//根据字符串s的排列找出下一个比它排列大的字符串，并更新s
3.sort()
sort()——可以实现对数、字符串、二元组pair、结构体甚至STL容器的排序
默认升序排序，可自定义排序规则
此处先简要介绍对基本类型以及字符串的排序
/* 整型数组的排序 */
int a[N];
for(int i = 0; i < n; i++) cin << a[i];
sort(a, a + n);//对数组a[0]-a[n-1]的元素升序排序！（左开右闭）
/* 字符串对字符的排序 */
string a;
//scanf("%s", &a[0]);//用scanf()输入只需要a[0]首地址
cin >> a;
sort(a.begin(), a.end());
printf("%s",a.c_str());//不能用cout输出字符串
以上都是sort(a, b)的形式，默认以升序排序
自定义排序规则，需要在使用sort时添加自定义的比较函数cmp()
/* 对整型 */
sort(a, a+n, cmp);
//默认升序
bool cmp(int a,int b)
return a<b;
//降序
bool cmp(int a,int b)
return a>b;
/* 对字符串 */
sort(a.begin(), a.end(), cmp)
//默认升序
bool cmp(char a,char b)
return a<b;
//降序
bool cmp(char a,char b)
return a>b;
