STL总结篇（参考自《算法竞赛入门经典》）

1. 排序与检索
2. 不定长数组：vector
3. 集合：set
4. 映射：map
5. 栈，队列与优先队列
6. 测试STL（略）
7. 应用

#include
using namespace std;

int a[]={10,0,2,5,6,7};

int main(){
    sort(a,a+6);
    for(int i=0;i<6;i++) cout<

sort使用数组元素默认的大小比较运算符进行排序，只有在需要按照特殊依据进行排序时才需要传入额外的比较函数。

sort数组的默认排序顺序是从小到大的，可以自定义一个compare函数来改变排序方式，也可以通过C++中的比较函数less,greater，这样就不需要我们自己家重新写比较函数了。

#include
using namespace std;

int a[]={10,0,2,5,6,7};

int cmp(int a,int b){
    return a>b;
}//从大到小

int main(){
    sort(a,a+6,cmp);
    //sort(a,a+6,greater());
    //sort(a,a+6,less());
    for(int i=0;i<6;i++) cout<

algorithm头文件中的sort可以给任意对象排序，排序对象可以存在一个普通数组里（sort(a,a+n)）也可以存在vector里（使用sort(v.begin(),v.end()调用）包括内置类型和自定义类型，前提是类型定义了“<”运算符。排序之后可以用lower_bound查找大于或者等于x的第一个位置。待排序、待查找的元素可以放在数组里，也可以放在vector里。

（还有一个unique函数课一删除有序数组中的重复元素）

vector就是个不定长数组，不仅如此，它把一些常用的操作封装在了vector类型内部。

例如，我们假设a是一个vector，vector a;

读取大小：a.size();

改变大小：a.resize();

向尾部添加元素：a.push_back();

删除最后一个元素：a.pop_back();

清空：a.clear();

测试是否为空：a.empty();

vector可以直接赋值，也可以作为函数的参数或者返回值，而无需像传递数组那样另外用一个变量指定元素个数。

vectora;
for(int i=0;i<10;++i){a.push_back(i);}
//
int a[6]={1,2,3,4,5,6};
vectorb;
vectorc(a,a+4);
for(vector::iterator it=c.begin();itb(a,a+4);
for(vector::iterator it=b.begin();it!=b.end();it++){cout<<*it<<"  ";}

集合和映射是两个常用的容器。set就是数学上的集合——每个元素最多只出现一次，和sort一样，自定义类型也可以构造set。定义在头文件里。

返回set容器第一个元素的迭代器  begin()

返回一个指向当前set末尾元素的下一位置的迭代器. end()

删除set容器中的所有的元素  clear()

判断set容器是否为空  empty()

返回当前set容器中的元素个数  size()

插入操作  intser()

查找set中某个键值出现的次数  count()

返回给定值值的定位器，若没找到则返回end()  find()

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于等于key_value的定位器

int main(){
     set s;
     s.insert(1);
     s.insert(2);
     s.insert(3);
     s.insert(1);
     cout < 
4.映射：map 
map就是从键（key）到值（value）的映射。定义在头文件
 
例如我们可以用一个mapmonth_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。
 
map与set二者都支持insert、find、remove、count等等操作，并且可以按照从小到大的顺序循环遍历其中的元素，map还提供了[]运算符，这让map可以像数组一样进行使用。
 
注意：没有良好的代码设计，是很难发挥出如map这种STL的优势的，如果没有想到相应的好的思路就很难使用map简化代码。
 
map mp;
mp.insert(pair(123,lvshun));

iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<second< 
5.栈，队列与优先队列 
栈 
栈即是符合后进先出规则的数据结构，有push和pop两种操作，push是将元素压入栈顶，而pop则是从栈顶将元素弹出。
 
栈定义在头文件中，可以用stack s的方式来声明一个栈。
 
 
 push() 元素入栈
 
pop() 元素出栈
 
top() 取栈顶元素（但不删除）
 
队列 
队列是符合先进先出原则的。
 

 STL队列定义在头文件中，可以用queue s;的方式声明一个队列。
 
push() 元素入队
 
pop() 元素出队
 
front() 取队首元素（但不删除）
 
优先队列 
优先队列是一种抽象的数据类型，行为有些像队列，但先进队列的额元素不是先进队列的元素，而是队列中优先级最高的元素，这样就可以允许类似于“急诊病人插队”这样的事情发生。
 
与队列一样也 定义在头文件里，用priority_queue pq; 来声明。
 
这个pq是iyige越小的整数优先级越低的优先队列，由于出队元素并不是最先进队的元素，出队的方法变为了top()；
 
自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小即可。（我们不难想到前面所述的sort）
 
在一些特殊的情况下，需要使用自定义方式比较优先级。
 
对于一些常见的优先队列，STL提供了更为简单的定义方法，例如越小的整数优先级越大的优先队列可以写成priority_queue > pq;注意 最后两个>>最好不要写在一起，有些编译器会认为是“>>”运算符。
 
7.应用 
原题链接：
 
J - Ginger的牧场 | SDUT OnlineJudge 
这是一道校选拔赛题，二分图板子，注意要使用map映射。
 
 
 
#include
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
typedef double db;
typedef pair PII;
typedef pair PLL;
typedef vector vi;
const int N=1005;
//
int e[N],h[N],ne[N],idx;
vector cows;
unmap(string,int) mp;
//int cow,cow_m;
int n,m,q;
int match[N];
bool st[N];
//
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(match[j]==0||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
signed main(){
    IOS;
    cin>>n>>m>>q;
    mem(h,-1);
    idx=0;
    while(q--){
        string a,b;
        cin>>a>>b;
        if(!mp.count(a)){
            mp[a]=++idx;
            cows.pb(mp[a]);
        }
        if(!mp.count(b)) mp[b]=++idx;
        add(mp[a],mp[b]);
    }
    int res=0;
    for(auto cow :cows){
        mem(st,false);
        if(find(cow)) res++;
    }
    cout< 
Problem - I - Codeforces
 
使用堆栈模拟
 


#include
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair PII;
typedef pair PLL;
typedef vector vi;
const int N=2e6+5;
//
int n;
string s;
int pre[N];
//
signed main(){
    IOS;
    
    cin>>n;
    cin>>s;
    stack a;
    mem(pre,0);
    int len = s.size();
    for(int i=0;i='0'&&s[i]<='9'){
            int x=0;
            while(s[i]>='0'&&s[i]<='9'){
                x=x*10+s[i]-'0';
                i++;
            }
            i--;
            if(a.empty()) a.push(x);
            else{
                pre[x]=a.top();
                a.push(x);
            }
        }
        else if(s[i]==')') a.pop();
    }
    for(int i=1;i 
（后续再更新 几个好题找不到了。。）
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！