算法竞赛中的STL

· · 个人记录

须知：本文是为普及/提高-的选手准备的，有些在OI中并没有什么用

ps:本蒟蒻第一次发日报，请大佬指教
pss:摘自HEU2020冬令营课件

目录

==========================================================

模板——template

还记得void*吗？

void*可以通过强制类型转换成为任意指针类型。

template的作用其实差不多，但是功能更加强大！

概括地说，template就是用一个自定义的类型名作为一个万能的类型

我们以一个函数为例：

int sum(int a,int b){return a+b;}

显然这个函数只能求int类型的两数相加。

那么能不能让这个函数变得“万能”？

有了模板，答案是肯定的！

template<typename temp>
temp sum(temp a,temp b){return a+b;}

这样我们就可以用它计算各种类型两数相加了。

在这里我们定义了一个temp的类型，叫做模板参数。当然temp可以换成别的东西。

这样函数就可以自动识别传入的变量的类型，然后按照这个类型返回。

有了template，我们可以写出很多方便的函数。

stl的绝大部分函数都是带模板的。

例如algorithm里的min函数(头文件里的函数都好丑qwq)

我们也可以定义多个模板参数：

template<typename T1,typename T2>

我们可以通过模板定义一个结构体：

template<typename T>struct point{T x,y;};

这样定义的时候就可以用point<int>p来申请一个x和y都是int的point变量。

很像STL的容器对不对？实际上，STL的大部分容器都采用了模板技术。

我们还可以像函数参数的初始化那样初始化模板参数：

template<typename T=int>struct point{T x,y;};

定义的时候就可以用point<>p了，此时p.x和p.y都是int类型的。

我们还可以在模板参数中填int等类型！

这样就可以用arr<233> b来申请一个内置长度为233的数组的变量啦。

C++11的array就是利用它实现的。

typename可以用class替换，但是此处的class与下面要讲的class类不同！

类——class

类class是一种封装的数据结构，类似于结构体struct，但略有不同。

例如： struct point{int x,y;};

对应的class是：

仅仅是加了一个public而已。

那么这个public有什么作用呢？

其实除了public，class中还有private和protect。

private表示函数或变量不能通过 变量.函数 进行访问，而只能在class中访问。

protect指函数或变量是受保护的。

以上在算法竞赛中基本用不到awa

用法的话可以看一下代码包里的bigint.h。

重载运算符——operator

重载运算符对于类和结构体都适用。

首先我们要知道带运算符的式子也是一个函数。

比如(int) a+b就可以看成一个返回值是int，两个参数分别是a和b的函数。

重载运算符就是给结构体定义一些这样的函数。

如果在类或结构体内部重载运算符则参数只有一个，是运算符左边的变量。

如果在结构体外重载则是两个参数，分别是左边和右边的变量。

其实这东西只要搞清楚参数和返回值就好办了。

还是这个结构体：

struct point{int x,y;};

在内部重载加号运算符就是

在外部重载则是

C++的输入输出

写在STL之前……(伪·STL)

C++I/O(in/out stream)

这个有什么好讲的呢……

首先你知道cin是什么吗？是函数吗？

当然不是，cin是istream类！ 重载了”<<“和”>>”运算符。

你可以把类(class)理解为复杂的结构体。

众所周知，这东西很慢……

但是有提速方法！

对于cin来说，只要加上这一句就能显著加速：

ios::sync_with_stdio(false);

意思是关闭与stdio的同步，也就是说，你不能再混用cin和scanf了……

速度优化显然(10^6个整数的读入与输出)：

(可还是不如scanf……)

对于cout来说，它的速度其实接近于printf； 拖慢其速度的主要因素是endl。

所以优化就是把endl换成’\n’。

C++I/O (file stream)

stream类也是支持文件操作的！

我们需要

#include<fstream>
ifstream fin(“输入文件名”);
ofstream fout(“输出文件名”);
…
fin.close();fout.close();

然后把cin、cout换成fin、fout即可。

这东西的优点是可以同时用cout、printf等进行屏幕输入输出，调试比较方便，还不会计入结果。

速度约等于取消同步的cin/cout。

可以多次调用fin.close()和fin.open(“in.txt”)来实现文件的反复读入。

甚至还有把两者结合到一块的fstream类：

fstream fs(“xxx.txt”);

实现了对文件的读入和输出！

即fs>>xx; fs<<“qwq”;

要注意的是写入时会清空原文件后再写入。

C++I/O (string stream)

“再恶心的读入也能用stringstream轻松解决！”——某dalao

#include<sstream> //……

定义： stringstream ss(s);

s是要作为流内容的字符串,就是把s作为读入内容, 然后就可以ss>>n了。

不懂就看个例题吧。

题目描述：给你一个序列，求序列最大值。

输入描述：输入有多行，每行是一个序列，每个整数间用’,’隔开。

输出描述：对于每行的序列，输出最大值。

样例输入：

1,3,6,2,5
22,33,55,11

样例输出：

6
55

(这不是水题么……)

看你读入怎么打

有了stringstream，这题就变得很简单！

然而一个重要的问题是……

这东西常数十分大……

具体有多大呢？ 还是刚才的题

比char数组慢了十几倍！

因此数据较大(>10^5)时不建议使用， sscanf()比这个稍快.

最后

关于STL

STL = Standard Template Library，标准模板库，惠普实验室开发的一系列软件的统称。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。
简单地说，STL就是给你做好一些容器、函数等乱七八糟的东西，让你直接使用。
O2优化可以大大提升STL的速度，但有些场合不开。

全文完

撒花~qwq