目录
入坑rc车的我又来写文啦ヾ(≧▽≦*)o
首先，咱们搞清楚STL库是啥东西
One.快速排序(Sort):
1.Sort的基本用法:
2.Sort进阶用法（CMP）：
3.Sort对结构体(或者类)的排序：
Two.Map
Map简介:
定义：
举个栗子:
刷题时间!
题目：离散化基础
输入格式
输出格式
输入/输出例子1
题解:
Three.stack(栈)
栈的介绍：
栈的定义：
栈的成员函数：
Four.二分查找
美妙的函数：
1.lower_bound函数
2.upper_bound函数
3.binary_search：查找数组内某个元素是否出现。
再来一题！
题目：数组线段和M
输入格式
输出格式
输入/输出例子1
题解：
Six.list(链表)
常用操作函数：
list的定义
ヽ(￣ω￣(￣ω￣〃)ゝ今天就到这，大家再见！。
入坑rc车的我又来写文啦ヾ(≧▽≦*)o
要“深入探讨”的可以加我qq28562939
想必经常搞C++的人大概都听说过STL库吧(正好最近在研究)，其中最知名我就是我们的——sort快速排序了！
不了解的兄弟也没关系，
我们继续往下看。
难度逐次递增。
首先，咱们搞清楚STL库是啥东西
STL,学名Standard Template Library，一般我们称他为标准模板库，是一系列软件的统称。
从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map一大堆，STL也是算
法和其他一些组件的集合。比如说<algorithm>中sort函数、<string>中string类都
是STL的内容。
STL库还有很多内容，比如：向量（vector）、栈（stack）、队列（queue）、优先队列
（priority_queue）、链表（list）、集合（set）、映射（map）等容器；min、max、swap
、sort、lower_bound、upper_bound 等算法，有的甚至都没人知道。ㄟ( ▔, ▔ )ㄏ
One.快速排序(Sort):
众所周知，c++有各种正常排序和奇葩的排序，比如说冒泡排序，时间复杂度为N(O^2)，就很离谱
是不是，随便排一个100000的元素的数组就超时。
所以，咱们以后不用冒泡，用sort快排（弃暗投明）,时间复杂度为N*LogN，对一百万个数排序也不会超过1秒。
1.Sort的基本用法:
sort是STL自带的系统函数，它的格式是：
void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；
这里可以省略比较函数，他是默认从小到大排序的（升序排序）
#include<algorithm>#include<iostream>using namespace std;int main(){int a[]={3,5,2,6,9,3,5};sort(a,a+7);//7是数组的元素个数，这里a为数组的开头，a+7就等于排序到数组的第七个元素for(int i=0;i<6;i++)cout<<a[i]<<" ";}输出:
2 3 3 5 5 62.Sort进阶用法（CMP）：
void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；,没错又是他，这里我们发
现还有个比较函数没说，这个比较函数的作用就是可以自定义排序方式，比如降序排序。
定义：bool cmp(int x,int y).....，如果返回True那么x就排在y前面。
#include<algorithm>#include<iostream>using namespace std;bool cmp(int x,int y){if(x>y)return true;//降序return false;}int main(){int a[]={3,5,2,6,9,3,5};sort(a,a+7,cmp);//7是数组的元素个数for(int i=0;i<6;i++)cout<<a[i]<<" ";}输出：
9 6 5 5 3 33.Sort对结构体(或者类)的排序：
同学们进行干饭比赛，参赛队员分别为“法外狂徒张三”，“干饭者老八”以及王五同学，谁吃的更多谁就排在更前面，如果吃的一样多那么谁吃的老八汉堡多谁就排在更前面：
#include<algorithm>#include<iostream>using namespace std;struct ganfan{string name;int zongshu;int hanbao;};bool cmp(ganfan x,ganfan y){if(x.zongshu>y.zongshu)return true;else if(x.hanbao>y.hanbao&&x.zongshu==y.zongshu)//如果一样多那么比谁吃的汉堡多return false;}int main(){ganfan a[3];a[0].name="zhangsan";a[0].zongshu=200;a[0].hanbao=6;a[1].name="laoba";a[1].zongshu=170;a[1].hanbao=13;a[2].name="wangwu";a[2].zongshu=170;a[2].hanbao=10;sort(a,a+3,cmp);for(int i=0;i<3;i++)cout<<a[i].name<<" ";}输出：
wangwu laoba zhangsan我们可以看到，张三的干饭总数是最多的，所以排在最前面，老八和王五的干饭总数一样多，但是老八吃的汉堡更多些，所以老八排在王五前面。
Two.Map
Map简介:
map是STL的一个关联容器，它提供一对一的hash。
第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)；定义：
map<类型,类型> m;举个栗子:
记录每个人的名字的对应的爱好,张三喜欢吃汉堡：
#include<map>#include<iostream>using namespace std;int main(){map<string,string> m;m["张三"]="吃汉堡";cout<<"张三: "<<m["张三"]; }输出：
张三: 吃汉堡
刷题时间!
题目：离散化基础
在使用离散化方法编程时，通常要知道每个数排序后的编号(rank值)，相同的数对应同一个编号。
输入格式
第1行：一个整数N。 1<=N<=100000。
第2行：有N个整数，每个数都是int范围的。注意：可能有相同整数。
输出格式
依次输出每个数的排名。
输入/输出例子1
输入：
5
8 2 6 9 2
输出：
3 1 2 4 1
题解:
这题用Sort和Map就可以很容易解决:
#include<bits/stdc++.h>using namespace std;int N,a[100001],b[100001];map<int,int> m;int main(){ cin>>N; for(int i=0;i<N;i++) { cin>>a[i]; b[i]=a[i]; } sort(b,b+N);//将数组排序 int c=1;//排名 m[b[0]]=1;//因为数组经过排序，所以第1个元素肯定是第一 for(int i=1;i<N;i++) { if(b[i]!=b[i-1])//判断是否不与前一个数相等 { c++; m[b[i]]=c; } } for(int i=0;i<N;i++) if(m[a[i]]!=0) cout<<m[a[i]]<<" ";//按照原来的下标输出 return 0;}Three.stack(栈)
头文件:
#include<stack>stack好像还有个翻译叫“咸鱼”...嘿嘿。
栈的介绍：
栈就像一个盒子，可以放入或去除元素，但是个人类都知道，要把盒子底下的东西取出来，就必须先取出他上面的东西。
假如我们把1、2、3、4、5按顺序分别入栈：
——博主美丽的手绘
栈的定义：
stack<类型(可以不写)> st;或者stack st;很easy是不？
栈的成员函数：
| .empty() | 判断栈是否为空，空则返回true |
| .pop() | 移除栈顶元素 |
| .push(啥啥啥) | 在栈顶增加元素 |
| .size() | 返回栈中元素数目 |
| .top() | 返回栈顶元素 |
.empty() 判断栈是否为空。
stack st;if(st.empty())//如果是空那么执行下面代码 .......push(啥啥啥),在栈顶增加元素。
.top()，返回栈顶元素，记住是返回，要单独输出。
#include<stack>#include<iostream>using namespace std;stack<int> st;int main(){ st.push(5418); cout<<st.top();//输出栈顶元素 return 0;}输出5418。
.size(), 返回栈中元素数目。
#include<stack>#include<iostream>using namespace std;stack<int> st;int main(){ st.push(5418); cout<<st.size(); return 0;}输出1
.pop()，移除栈顶元素：
#include<stack>#include<iostream>using namespace std;stack<int> st;int main(){ st.push(1452); st.push(5418); st.pop(); cout<<st.top(); return 0;}输出1452。
简单不？
Four.二分查找
头文件：
#include <algorithm>美妙的函数：
1.lower_bound函数
对于有序容器，有序容器，有序容器（重要的事情说三遍）快速二分查找出第一个大于等于
指定数的位置（下标），如果没有找到，返回最后一个数据后面的位置。
对于数组，通常的格式为：
查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置(一般写数组名);
比如：
#include<algorithm>#include<iostream>using namespace std;int main() { int a[5] = { 1,2,3,3,8 }; //从 a 数组中找到第一个不小于 3 的元素 int index = lower_bound(a, a + 5, 3)-a;//查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置; if (index==5 ) cout << " not found! ";//index=5，也就是数组末尾的位置。 else cout << index; return 0;}输出2。
2.upper_bound函数
有一个类似lower_bound的函数upper_bound, 快速二分查找出第一个大于指定数的位置（下
标），如果没有找到，返回最后一个数据后面的位置。
举个栗子，啊......快没栗子了。(っ °Д °;)っ
#include<algorithm>#include<iostream>using namespace std;int main() { int a[5] = { 1,2,3,3,8 }; //从 a 数组中找到第一个大于 3 的元素 int index = upper_bound(a, a + 5, 3)-a; if (index==5 ) cout << " not found! "; else cout << index; return 0;}输出4.
3.binary_search：查找数组内某个元素是否出现。
void binary_search(数组首地址，结束地址，要查找的数)
返回值为bool类型，找到了返回true。
再来一题！
题目：数组线段和M
输入格式
第一行2个正整数N和M，N范围[1，1000000],M范围[1，10^9]。
第二行是N个正整数，每个数范围[1，1000]。
输出格式
一个整数。
输入/输出例子1
输入：
10 20
1 7 10 10 7 10 6 4 6 6
输出：
2
题解：
这题我是用前缀和的方法解的，因为数据较多，这样快一点,还能变成有序数列。
代码稍稍有点难，大家看着办吧：
#include<bits/stdc++.h>using namespace std;int N,M;int a[1000001];int main(){ cin>>N>>M; cin>>a[0]; for(int i=1;i<N;i++) { cin>>a[i]; a[i]+=a[i-1];//求前缀和数组 } int ans=0; int mubiao=M;//目标 for(;int index = lower_bound(a, a + N, mubiao)-a;) { if(index==N)//找不到了说明没有了 { break; } if(a[index]==M) { mubiao=a[index]+1; } else{ int fl=a[index]-M; int ind=lower_bound(a, a + N, fl)-a; if(a[ind]==fl) ans++; mubiao=a[index]+1;//目标加一，防止重复查找 } } cout<<ans; return 0;}思路是找一个比M大的数，如果能找到，那么求出这个数和M的差，再找这个差，如果能找到，那根据前缀和的定义这一串的和就等于M，然后把目标+1，防止重复查找。
Six.list(链表)
常用操作函数：
List.assign() 给list赋值
List.back() 返回最后一个元素
List.begin() 返回指向第一个元素的迭代器
List.clear() 删除所有元素
List.empty() 如果list是空的则返回true
List.end() 返回末尾的迭代器
List.erase() 删除一个元素
List.front() 返回第一个元素
List.get_allocator() 返回list的配置器
List.insert() 插入一个元素到list中
List.max_size() 返回list能容纳的最大元素数量
List.merge() 合并两个list
List.pop_back() 删除最后一个元素
List.pop_front() 删除第一个元素
List.push_back() 在list的末尾添加一个元素
List.push_front() 在list的头部添加一个元素
List.rbegin() 返回指向第一个元素的逆向迭代器
List.remove() 从list删除元素
List.remove_if() 按指定条件删除元素
List.rend() 指向list末尾的逆向迭代器
List.resize() 改变list的大小
List.reverse() 把list的元素倒转
List.size() 返回list中的元素个数
List.sort() 给list排序
List.splice() 合并两个list
List.swap() 交换两个list的内容
List.unique() 删除list中相邻重复的元素
list的定义
list<int> lst1; //创建一个空listlist<int> lst2(10); //创建一个含有10个元素的listlist<int> lst3(3,2); //创建含有3个元素2的listlist<int> lst4(lst2); //使用lst2初始化lst4list<int> lst5(lst2.begin(),lst2.end()); //同lst4部分内容与栈那篇差不多，我们不讲。
ヽ(￣ω￣(￣ω￣〃)ゝ今天就到这，大家再见！。