把STL放在心底，永远都有惊喜
——《Tonight Forever》

前言

或许你会问我为什么要再写一篇STL，因为之前的STL转载自Herself32’s Blog，并非作者亲笔所写，所以作者在自己学完STL后自己又写了一篇。

鸣谢 Menci & Herself32在STL学习中给我的帮助。

初始约定

在STL中，很多时候会出现(begin , end)

这表示一段数组上的区间：从begin 到 end

其中，begin为开头，end为结尾。

就像下图：

但值得一提的是，begin在这个区间内，但end不在。

迭代器

在讲迭代器之前，我们先看看百度百科对于迭代器的解释：

迭代器（iterator）有时又称游标（cursor）是程序设计的软件设计模式，可在容器（container，例如链表或阵列）上遍访的接口，设计人员无需关心容器的内容。
——百度百科

emm……

这是什么鬼玩意……

不看了……

其实，迭代器就是一个用来指示容器中元素位置的数据，就像数组的下标，可以指示某一个元素在数组中的位置。

迭代器分为5种，分别是：

输入迭代器（ps.可以拿来读取）

输出迭代器（ps.可以拿来写入）

前向迭代器（ps.可以拿来读取与写入，同时还可以向前移动，但一次只能移动一个位置）

双向迭代器（ps.可以拿来读取与写入，同时还可以向前后两个方向移动，但一次只能移动一个位置）

随机访问迭代器（ps.可以拿来读取与写入，同时还可以向前后两个方向移动，一次可移动多个位置）

其中，我们数组的下标就是一个随机访问迭代器，所有的指针也都是随机访问迭代器。

Algorithm库

依稀记得

在$NOIP2018$前一秒

我还没背下来这个头文件

但这个头文件里真的有许多好用的模板。

下面就来看看吧

MAX & MIN

求两个数里较大值与较小值的函数

包含在algorithm库中(ps.有的编译器下iostream库中也可以)

可以返回两个值的较大值或较小值。

模板如下：

#include<algorithm>
max(a , b);
min(a , b);

时间复杂度为$O(1)$

MAX_element & MIN_element

这两个函数可以求一个区间内的最大值与最小值

相当于上面两个函数的升级版

同样，包含在algorithm库中。

模板如下：

#include<algorithm>
max_element(begin , end);
min_element(begin , end);

时间复杂度为$O(n)$

Swap

这个函数用于交换两个变量的值

模板如下：

#include<algorithm>
swap(a , b);

时间复杂度为$O(1)$

Fill

这个函数用于向一个区间内填充指定的值

模板如下：

#include<algorithm>
fill(begin , end , value);

其中，value为填充的值。

时间复杂度为$O(n)$

补充：

或许你觉得memset(数组名， 0 ， sizeof(数组名))有同样的效果，

但是

它们的本质是不一样的。

fill函数是把数组中的每一个元素填充为指定的数值，

而memset是逐字节填充。

因此

memset在填充较大的数值时很容易出锅……

而fill不会。

（ps.整段翻译成人话就是大部分情况下用fill就好啦 QvQ）

Random_shuffle

这个函数可以把一个给定区间的值全部随机排列。

~~可以拿来写猴排~~

~~也可以#define sort random_suffle~~

咳咳

下面是模板：

#include<algorithm>
random_shuffle(begin , end);

时间复杂度为$O(n)$

Sort

在STL里最常用的函数应该就是它了

它可以把一段区间内的元素进行升序排序

如果是不稳定排序，他会用类似于快速排序的方法实现

稳定排序则是使用归并排序实现

代码如下：

#include<algorithm>
sort(begin , end);

时间复杂度保证为$O(n log n)$

比手写排序快多啦QvQ

补充：

不知道你看到了吗

sort是进行升序排序

那么

降序排序怎么办呢？

~~直接反着调用不就行了……~~

Unique

这个函数可以把一个升序排序后的区间里重复的元素去除

使用前一定别忘了排序

代码如下：

#include<algorithm>
unique(begin , end);

时间复杂度为$O(n)$

Next_permutation

全排列函数

就是可以输出一个区间范围内所有元素的所有排列方法。

比如说

1 ，2 ，3 ，4的全排列如下图

代码如下：

#include<iostream>
#include<algorithm>
int a[4] = {1 , 2 , 3 , 4};
do{
    for(int i = 0; i < 4; i++){
        cout << a[i] << endl;;
    }
}while(next_permutation(a, a + 4));
return 0;