【STL编程】【竞赛常用】【part 1】

标准模板库（Standard Template Library ，STL）从广义上讲分为算法（Algorithm）、容器（Container）及迭代器（Iterator）3类，包含很多的基本数据结构和基本算法。

标准C++语言中，STL被组织为下面的13个头文件：<algorithm> 、<deque>、<functional>、<vector>、<iterator>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>及<utiity>。

1. sort 排序算法

STL 里的 sort 排序算法在头文件 <algorithm> 中声明，采用的快速排序，可以保证时间复杂度为 $O(nlogn)$。比 C 语言中的 qsort 要好。

#include<bits/stdc++.h>
using namespace std;
void Print(int a[],int n){
    for (int i = 0; i < n;i++){
        cout << a[i] << " ";
    }
    cout << endl;
}
int main(){
    int a[] = {1, 5, 3, 2, 65, 2, 76};
    int len = sizeof(a) / sizeof(int);
    sort(a, a + len);
    Print(a, len);
    sort(a, a + len, greater<int>());//从大到小
    Print(a, len);
    return 0;
}

运行结果：
1 2 2 3 5 65 76
76 65 5 3 2 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

或者可以自己手写 cmp() 比较函数进行数组元素比较：

bool cmp(int a,int b){
    return a > b;
}
int main(){
    int a[] = {1, 5, 3, 2, 65, 2, 76};
    int len = sizeof(a) / sizeof(int);
    sort(a, a + len);
    Print(a, len);
    sort(a, a + len, cmp); //从大到小
    Print(a, len);
    return 0;
}

结果同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对字符排序：

#include<bits/stdc++.h>
using namespace std;
int main(){
    char a[11] = {"dfjksaldwq"};
    sort(a,a+10);
    for (int i = 0; i < 10;i++){
        cout << a[i];
    }
    cout << endl;
    sort(a, a + 10, greater<char>());
    for (int i = 0; i < 10;i++){
        cout << a[i];
    }
    cout << endl;
    return 0;
}

运行结果：
addfjklqsw
wsqlkjfdda
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对结构体的排序，其实就是写 cmp() 函数：

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

struct Node{
    int x, y;
} p[1001];

int cmp(Node a,Node b){
    if(a.x!=b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n;++i){
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + 1 + n, cmp);
    for (int i = 1; i <= n;++i){
        cout << p[i].x << " " << p[i].y << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. stable_sort 稳定排序

stable_sort 和 sort 的区别在于前者排序后可以使用原来的“相同”的值在序列中的相对位置不变，例如初始序列中有两个元素 A 和 B 的值相等，且 A 在 B 前，排序后 A 仍在 B 前 ，这种排序称为稳定排序。

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

struct stu{
  int id;
  string name;
  int score;
};

bool comByscore(stu s1, stu s2){
  return s1.score < s2.score ? 1 : 0;
}

bool comByid(stu s1, stu s2){
  return s1.id > s2.id ? 1 : 0;
}

int main(){
    vector<stu> v;
    struct stu master;
    master.id = 3;
    master.name = "clare";
    master.score = 60;
    v.push_back(master);
    master.id = 2;
    master.name = "Liqiang";
    master.score = 99;
    v.push_back(master);
    master.id = 1;
    master.name = "qiangYi";
    master.score = 88;
    v.push_back(master);
    stable_sort(v.begin(), v.end(), comByscore); //按分数排序
    for (int i = 0; i < v.size(); i++)
        cout << v[i].id << ' ' << v[i].name << ' ' << v[i].score << endl;
    stable_sort(v.begin(), v.end(), comByid); //按学号逆排序
    for (int i = 0; i < v.size(); i++)
        cout << v[i].id << ' ' << v[i].name << ' ' << v[i].score << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3 clare 60
1 qiangYi 88
2 Liqiang 99
3 clare 60
2 Liqiang 99
1 qiangYi 88
1
2
3
4
5
6

3. 排列组合关系算法

next_permutation() 按照字典序产生排列，并且是从数组中当前的字典序开始依次增大直至最大字典序。
prev_permutation() 按照字典序产生排列，并且是从数组中当前的字典序开始依次减小直至最小字典序。

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

void print(int a[]){
    for (int i = 0; i < 5; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main(){
    int a[] = {1, 2, 6, 7, 9};
    //产生所有下一组合，时间复杂度为n!,速度较慢
    while (next_permutation(a, a + 5)) //下一组合
        print(a);
    int b[] = {5, 4, 3, 2, 1};
    while (prev_permutation(b, b + 5)) //上一组合
        print(b);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

结果：

1 2 6 9 7 
1 2 7 6 9
1 2 7 9 6
1 2 9 6 7
...
9 7 6 2 1

5 4 3 1 2
5 4 2 3 1
5 4 2 1 3
...
1 2 3 4 5
1
2
3
4
5
6
7
8
9
10
11
12

4. lower_bound/upper_bound

lower_bound(起始地址 first，结束地址last，要查找的数值val):在first 和 last 中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素地址。如果区间内所有元素都小于 val，则返回last的地址，且last的地址是越界的。
upper_bound(起始地址first，结束地址last，要查找的数值val):在first和last中的前闭后开区间进行二分查找，返回大于val 的第一个元素地址。如果val大于区间内所有元素，则返回last的地址，且last的地址是越界的。
特别注意:lower_bound/upper_bound二分查找的区间必须为有序序列，如图所示：

升序数组使用lower_bound/upper_bound：

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

int main(){
    int a[] = {1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
    cout << lower_bound(a, a + 10, 0) - a << endl; //输出下标0
    cout << lower_bound(a, a + 10, 1) - a << endl; //输出下标0
    cout << lower_bound(a, a + 10, 3) - a << endl; //输出下标4
    cout << lower_bound(a, a + 10, 4) - a << endl; //输出下标7
    cout << lower_bound(a, a + 10, 5) - a << endl; //输出下标10

    cout << upper_bound(a, a + 10, 0) - a << endl; //输出下标0
    cout << upper_bound(a, a + 10, 1) - a << endl; //输出下标2
    cout << upper_bound(a, a + 10, 3) - a << endl; //输出下标7
    cout << upper_bound(a, a + 10, 4) - a << endl; //输出下标10
    cout << upper_bound(a, a + 10, 5) - a << endl; //输出下标10
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

降序数组直接使用lower_bound/upper_bound：是错误的：

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

int main(){
    int a[] = {4, 4, 3, 3, 2, 2, 1, 1};
    cout << lower_bound(a, a + 8, 4) - a << endl; // 输出 8
    cout << upper_bound(a, a + 8, 4) - a << endl; // 输出 8
    cout << lower_bound(a, a + 8, 1) - a << endl; // 输出 0
    cout << upper_bound(a, a + 8, 1) - a << endl; // 输出 0
    cout << lower_bound(a, a + 8, 3) - a << endl; // 输出 8
    cout << upper_bound(a, a + 8, 3) - a << endl; // 输出 8
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这是因为 lower_bound / upper_bound 默认二分查找的区间是升序序列。以查找数值 4 为例，第一步从中间开始，取中间值 a [(0+8)/2] = a [4]=2，比 4 小，于是继续向更大的值靠近，向哪边靠近呢，右边，因为它以为序列是升序的，这显然是错误的。

所以，在降序序列要注意以下两点。

(1) lower_bound 的正确写法为 lower_bound ( first , last , val , greater<int>() )，或类似于 sort 排序，使用自定义比较函数。若 val 在序列中，则返回 val 第一次出现的位置，否则返回第一个插入 val 不影响原序列顺序的位置。

(2) upper_bound 的正确写法为 upper_bound ( first , last , val , greater<int>() )，或类似于 sort 排序，使用自定义比较函数。若 val 在序列中，则返回第一个小于 val 的位置，否则返回第一个插入 val 不影响原序列顺序的位置。

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

int main(){
    int a[] = {4, 4, 3, 3, 2, 2, 1, 1};
    cout << lower_bound(a, a + 8, 0, greater<int>()) - a << endl; // 输出 8
    cout << lower_bound(a, a + 8, 4, greater<int>()) - a << endl; // 输出 0
    cout << lower_bound(a, a + 8, 1, greater<int>()) - a << endl; // 输出 6
    cout << lower_bound(a, a + 8, 3, greater<int>()) - a << endl; // 输出 2
    cout << lower_bound(a, a + 8, 5, greater<int>()) - a << endl; // 输出 2

    cout << upper_bound(a, a + 8, 0, greater<int>()) - a << endl; // 输出 8
    cout << upper_bound(a, a + 8, 4, greater<int>()) - a << endl; // 输出 2
    cout << upper_bound(a, a + 8, 1, greater<int>()) - a << endl; // 输出 8
    cout << upper_bound(a, a + 8, 3, greater<int>()) - a << endl; // 输出 4
    cout << upper_bound(a, a + 8, 5, greater<int>()) - a << endl; // 输出 4
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

STL 中还有一个二分查找函数 binary_search(first,last,val)，用法类似于 lower_bound / upper_bound ，但它只能判断 val 是否在 first 和 last 的有序区间内存在 ，如果存在返回 true ，否则返回 false 。

int a[] = {4, 4, 3, 3, 2, 2, 1, 1};
cout << binary_search(a, a + 8, 2, greater<int>()) << endl; 
//输出 1
1
2
3

5. vector 向量容器

可以代替数组a[]，常用的操作如下所示：

（1）数组的方式访问 vector

(*￣(oo)￣)：

• 对于容器 c ，表达式 c.front() 等价于 *c.begin()。
• 对于非空容器 c ，表达式 c.back() 等价于 *std::prev(c.end()) 。

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

int main(){
    vector<int> v;   //定义了一个存放int类型的vector容器
    v.reserve(30);   //调整数据空间大小
    v.push_back(20); //尾端插入新元素
    v.push_back(26);
    v.push_back(12);
    v.push_back(52);
    v.insert(v.begin(), 2);            // begin()为vector头部,在此处插入2
    v.insert(v.end(), 43);             // end()为vector尾部，在此处插入43
    v.insert(v.begin() + 2, 15);       //在第2个元素前插入15
    v.erase(v.begin() + 1);            //删除第2个元素
    v.erase(v.begin(), v.begin() + 2); //删除前三个元素
    v.pop_back();                      //删除末尾的一个元素
    for (int i = 0; i < v.size(); ++i) // size()为v中元素个数
        cout << v[i] << ' ';
    cout << "\n 首元素为:" << v.front() << '\n'; //首元素引用
    cout << "末元素为:" << v.back() << '\n';     //末元素引用
    reverse(v.begin(), v.end());                 //反转整个vector元素
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << ' ';
    v.clear();                                    //全部清空元素
    cout << "\n v是否为空:" << v.empty() << '\n'; //判断是否为空
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（2）结构体容器的vector

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

struct stu{
    int x, y;
};

int main(){
    int j;
    vector<stu> v1; //结构体容器
    vector<stu> v2;
    struct stu a = {1, 2};
    struct stu b = {2, 3};
    struct stu c = {4, 5};
    v1.push_back(a);
    v1.push_back(b);
    v1.push_back(c);
    v2.push_back(c);
    v2.push_back(b);
    v2.push_back(a);
    swap(v1, v2);                       //两结构体元素交换
    for (int i = 0; i < v1.size(); i++) //输出v1所有元素
        cout << v1[i].x << " " << v1[i].y << endl;
    cout << "\n";
    for (int i = 0; i < v2.size(); i++) //输出v2所有元素
        cout << v2[i].x << " " << v2[i].y << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

结果：

4 5
2 3
1 2

1 2
2 3
4 5
1
2
3
4
5
6
7

（3）迭代器访问 vector

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

int main(){
    int j;
    vector<int> v;
    v.reserve(30); //调整数据空间大小
    for (int i = 0; i < 10; i++)
        v.push_back(i);                    //尾端插入新元素
    vector<int>::iterator i;               //定义vector的迭代器i
    for (i = v.begin(); i != v.end(); i++) //迭代器遍历
        cout << *i << " ";
    cout << "\n v中的元素个数:" << v.size() << '\n'; //元素实际个数
    reverse(v.begin(), v.end());                     //反转
    for (i = v.begin(); i != v.end(); i++)           //迭代器遍历
        cout << *i << " ";
    v.clear();                                    //全部清空元素
    cout << "\n v是否为空:" << v.empty() << '\n'; //判断是否为空
    return 0;
}
/*
0 1 2 3 4 5 6 7 8 9 
 v中的元素个数:10
9 8 7 6 5 4 3 2 1 0
 v是否为空:1
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

【part 2】【part3】敬请期待！！

6. pair 容器

7. set 集合容器

8. multiset 多重集合容器

9. map 映射容器

10. multimap 多重映射容器

11. list 双向链表容器

12. stack 堆栈容器

13. queue 队列容器

14. deque 双端队列容器

15. priority_queue 优先队列容器