L4 STL的使用

常用的函数

1. sort

• 左闭右开区间，从小到大排序
• 改写为从大到小排序

int cmp(int a, int b)
{
    return a>b;
}

sort(a, a+n, cmp);

• 给结构体排序

// struct_sort

#include <bits/stdc++.h>
using namespace std;

// 以分数为第一关键字，学号为第二关键字给学生排序

/* 写法一，写cmp函数

struct student
{
    int score, id;
}a[10];
 
bool cmp(student a, student b)
{
    if(a.score!=b.score) return a.score<b.score;
    return a.id<b.id;
}*/
 
// 写法二，在结构体中定义小于号（重载小于号）
 
struct student
{
    int score, id;

    // 写在里面要加一个 friend，先背下来
    friend bool operator < (student a, student b)
    {
        if(a.score!=b.score) return a.score<b.score;
        return a.id<b.id;
    }

}a[10];
/* 写在外面的写法
bool operator < (student a, student b)
{
    if(a.score!=b.score) return a.score<b.score;
    return a.id<b.id;
}*/
 
int main()
{
    a[0].score=100, a[0].id=1;
    a[1].score=100, a[1].id=2;
    a[2].score=90, a[2].id=3;
    a[3].score=50, a[3].id=4;
    a[4].score=80, a[4].id=5;
 
    //sort(a, a+5, cmp);
    sort(a, a+5);
 
    for(int i=0; i<5; i++)
        printf("%d %d\n", a[i].score, a[i].id);

    return 0;
}

2. pair

• 将两个数打包成一个

#include <bits/stdc++.h>
using namespace std;

//普通的函数返回值只能有一个，但用 pair 可以一次性返回两个值
pair<int, int> pr;
 
int main()
{
    // make_pair 是一个函数，会自动判断括号里的类型，打包成一个对应的 pair
    pr = make_pair(1, 2)  
     
    // pair 默认先按 first 比较，再按 second
    cout<<pr.first<<endl;<<pr.second<<endl;
 
    return 0;
}

STL 中的容器

1. vector

• 可以动态分配空间的（数组。。类似）

#include <bits/stdc++.h>
using namespace std;
 
vector<int> v;
 
int main()
{
    // 尾部压进元素
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
    v.push_back(5);
    v.push_back(4);
     
    // 尾部弹出元素
    v.pop_back();
     
    // 支持下标访问（随机访问）
    for(int i=0; i<v.size(); i++)
        cout<<v[i]<<endl;  
    
    // 排序
    sort(v.begin(), v.end());  // v.begin 和 v.end 类型是迭代器
     
    // 清空操作
    v.clear();
     
    return 0;
}

• 对结构体进行操作

// struct_vector

#include <bits/stdc++.h>
using namespace std;

struct student
{
    int score, id;
 
    // 构造函数：初始化一个 student 结构体的时候，会调用构造函数
    // 即和 struct 同名的函数
    student(int _id=0, int _score=0)
    {
        id=_id;
        score=_score;
    }
 
};
 
vector<student> v;
 
int main()
{
    v.push_back(student(1, 2));
    v.push_back(student(3, 4));
    v.push_back(student(3, 4));
    v.push_back(student(5, 6));
    v.push_back(student(6, 8));
 
    for(int i=0; i<v.size(); i++)
        cout<<v[i].score<<endl;
 
    return 0;
}

2. 栈 stack

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    stack<int> s;
 
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
   
    cout<<s.size()<<endl;
 
    while(!s.empty()){
        cout<<s.top();
        s.pop();
    }
 
    return 0;
}

3. 队列 queue

#include <bits/stdc++.h>
using namespace std;

int main()
{
    queue<int> s;
 
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
 
    cout<<s.size()<<endl;
 
    while(!s.empty()){
        cout<<s.front();
        s.pop();
    }
 
    return 0;
}

4. 双端队列 deque

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    deque<int> s;  // 单调队列多用 deque
 
    s.push_back(1);
    s.push_front(2);
    s.push_back(3);
    s.push_front(4);
 
    cout<<s.size()<<endl;

    while(!s.empty()){
        cout<<s.front();
        s.pop_front();
    }
 
    return 0;
}

5. 优先队列 priority_queue

• 优先队列是堆不是栈，是个可以插队的队列，默认从大到小排序

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    priority_queue<int> s;
    // 改成从小到大排
    // priority_queue<int, vector<int>, greater<int> > s;
 
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
 
    cout<<s.size()<<endl;
 
    while(!s.empty()){
        cout<<s.top();  // 弹出的是最大值
        s.pop();
    }

    return 0;
}

6. 有序集合 set

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    set<int> s;
 
    s.insert(1);
    s.insert(3);
    s.insert(5);
 
    cout<<s.size()<<endl;
 
    // 查询集合中有无某元素
    cout<<s.count(1)<<endl;
    cout<<s.count(2)<<endl;
    cout<<s.count(3)<<endl;
 
    // 迭代器输出
    for(set<int>::iterator it=s.begin(); it!=s.end(); it++)
        cout<<*it<<endl;
 
    return 0;
}

7. 有序键值对 map

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // 可以理解为广义数组
    map<string, int> score;  // 从 string 到 int 的映射
 
    score["a"] = 0;
    score["b"] = 100;
    score["c"] = -50;
     
    cout<<score["a"]<<endl;
    cout<<score["b"]<<endl;

    return 0;
}