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

前言

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

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


初始约定

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

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

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

就像下图:

5jEGTp.png

但值得一提的是,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的全排列如下图

kZFptO.png

代码如下:

#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;

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

未完待续