搬运自以前在luogu上写的文章
UpdateLog
- Ver3 增加
C++XX的景象，增加C++11on 4.2 - Ver2 简化
zvector加入Part3模板的好处 and Part4模板带来的问题on 3.15 - Ver1 ini on 3.10
模板是C++程序员绝佳的武器，特别是结合了多重继承与运算符重载之后。C++的标准函数库提供的许多有用的函数大多结合了模板的概念，如STL以及iostream。——Wikipedia
前置知识点：OO(面向对象)入门(可能?)
Part-1 C++98的景象
C没有参数多态，我们在C++加上去吧。
Roger that，那么具体怎么实现呢？我们要继承C的静态语言特性，不能在运行期生成类型啊（类似Java）
OK，我们搞出来了一个叫模板的东西，现在只需在要添加参数多态的函数或者类前加上这个
template <参数列表>
参数列表类似定义函数中在括号里填的东西，其中参数列表中可以填放的叫参数包，参数包分为放类型的类型参数 和放值的非类型参数两种。
然后调用时在函数或者类后面紧跟着加上尖括号包着的形参列表调用函数，编译器就生成对应的类型即可。
对于修饰函数的模板，我们叫他函数模板，修饰类的模板我们叫他类模板。
不错，目前加入这个特性就够了，Over。
Part0 Introduce
模板能干啥?
比如我们有个函数有很多种用法，但是他们的差异就是改改类型，我们就可以使用模板一次定义(std::max)。
又比如我们有个数据结构需要支持不同的数据类型，我们就可以使用模板一次定义这个数据结构(std::vector)。
还比如我们有个类需要预先设置大小，我们就可以用模板来写(std::bitset)。
更可以干一些更NB的事情，比如利用模板特化递归定义类型。
Part1 模板函数-类型参数
我们在看其他大佬写的代码里常常有这么两个函数
template<class T>
bool cmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>
bool cmin(T &a,T b){return a>b?a=b,1:0;}
//调用举例
int a=1,b=2;
double da=1.0,db=1.1;
cout << cmax(a,214) << endl;//a被赋值成了214
cout << cmin(da,db) << endl;//da没有赋值
输出
1
0
这个template<class T>，class表明后面需要跟类型名称，调用这个函数时C++会根据传入变量类型自动推断这个T的类型并带入原定义生成相应函数。
拿上述函数举例，C++编译器自动帮我们生成了如下函数。
bool cmax(int &a,int b){return a<b?a=b,1:0;}
bool cmin(double &a,double b){return a>b?a=b,1:0;}
除了大佬常写的这两个函数，在STL里的函数几乎全部都是这种模板函数，比如我们常见的max和min在stl中的定义。
template< class T >
const T& max( const T& a, const T& b );
template< class T >
const T& min( const T& a, const T& b );
使用模板函数时一定要注意以下三点
- 在传入值为void时需使用时指定类型
template<class T>
T empty(){return T();}
//调用
empty<int>();
- 在编译器生成对应的函数时一个T只能对应一个类型
//接上述cmax
int a=1;long long b=100;
cmax(a,b);
//报错，因为a,b不同类型，但是在定义中时一个类型(这和不用模板不一样，不用模板允许传入一个允许强制转换的类型)
//改cmax如下即可通过编译
template<class T1,class T2>
bool cmax(T1 &a,T2 b){return a<b?a=b,1:0;}
template作用域为它的下一行，如下一行是一个函数，它就作用于这个函数；如下一行是个类，他就作用于类
Part2.1 模板类-类型模板
原理同上，不过这回不能由编译器自动推断了，需要自己给出类型，下面给出代码(【模板】树状数组 2)
#include <bits/stdc++.h>
#define ri register int
using namespace std;
#define N 6000
template<class T>
inline T lowbit(T i){return i&(-i);}
template<class T>
struct BT{
T *a;int size;
BT(int n){
size=n;
a=new int[n+3];
memset(a,0,sizeof(int)*(n+2));
}
~BT(){delete []a;}
void add(int i,T v){
while (i<=size) a[i]+=v,i+=lowbit(i);
}
T sum(int i){
T ans=0;
while (i) ans+=a[i],i-=lowbit(i);
return ans;
}
};
int b[500000];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",b+i);
for (int i=n;i>=1;i--) b[i]-=b[i-1];
BT<int> a(n+3);
for (int i=1;i<=n;i++) a.add(i,b[i]);
for (int i=1;i<=m;i++){
int opt;
scanf("%d",&opt);
if (opt==1){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
a.add(l,k);
a.add(r+1,-k);
}else{
int w;
scanf("%d",&w);
printf("%d\n",a.sum(w));
}
}
}
这也暗示着BT<int>和BT<double>不是一种类型
std::vector,std::map，std::stack这些也是利用模板实现的
下面给出笔者实现的简化版vector(【模板】普通平衡树200ms)，使用同std::vector
具体实现细节可以跳过，仅查看代码大意即可。
#ifndef IT
#define IT unsigned long long
#endif
template<class T>
class zvector{
private:
T *begin_;
IT size_,capacity_;
public:
inline void reverse(const IT new_capacity){
if (new_capacity>=capacity_){
while(new_capacity>=capacity_)
capacity_=capacity_<<1;
T *new_begin=new T[capacity_];
memmove(new_begin,begin_,size_*sizeof(T));
delete[] begin_;
begin_=new_begin;
}
}
inline zvector(const zvector<T> &src){
size_=src.size_;
capacity_=src.capacity_;
begin_=new T[capacity_];
memmove(begin_,src.begin_,sizeof(T)*size_);
}
inline zvector(){
size_=0;
capacity_=1;
begin_=new T[1];
}
inline zvector<T>& operator=(const zvector<T> &src){
reverse(src.size_);
size_=src.size_;
memmove(begin_,src.begin_,sizeof(T)*size_);
}
~zvector(){delete[] begin_;}
inline T* begin(){return begin_;}
inline T* end(){return begin_+size_;}
inline IT size(){return size_;}
inline bool empty(){return size_==0;}
inline T& operator[](const IT i){return begin_[i];}
inline T& front(){return begin_[0];}
inline T& back(){return begin_[size_-1];}
template<class T2>
inline void fill(const T2 ch){
if (sizeof(T2)==1){
memset(begin_,ch,sizeof(T)*size_);
}else{
for (int i=0;i!=size_;i++)
begin_[i]=ch;
}
}
inline void push_back(const T a){
reverse(size_+1);
begin_[size_++]=a;
}
inline void pop(const IT count=1){size_-=count;}
inline void clear(){size_=0;}
inline void resize(const IT new_size,const char ch=0x00){
reverse(new_size);
if (new_size>size_){
memset(begin_+size_,
ch,
sizeof(T)*(new_size-size_));
}
size_=new_size;
}
inline void erase(const IT index){
memmove(begin_+index,
begin_+index+1,
(size_-index)*sizeof(T));
--size_;
}
inline void insert(const IT index,const T a){
reverse(size_+1);
memmove(begin_+index+1,
begin_+index,
(size-index)*sizeof(T));
begin_[index]=a;
++size_;
}
};
Part2.2 模板类-非类型模板
简单来说就是T可以放值了，仅仅把原先的class变成T的类型即可，Wait，C++认为something<1>和something<2>是两个不同的类型。
而且something<value>里的value必须是常量（其实也不难理解，C++编译器需在编译时生成相应的汇编语言，它不能把value提前算出来，也不能把value能取的值全都取到编译）。
笔者搞出来了个方便取余的MOD结构体，值得注意的是成员函数也可以加模板，规则同上述函数模板。
template<long long m>
struct MOD{
template<class T>
inline T& operator=(T &a){a%=m;return a;}
template<class T>
inline T operator|(const T a){return a%m;}
};
MOD<100ll> o;
int main(){
int a=35621,b=1235;
o=a*=b;
a=o|b*b;
}
std::bitset就是属于非类型模板
Part2.3 模板类-模板特化以及其扩展
什么是模板特化呢?
对于某些类型，我们需要不同与其他类型的实现方式，就可以另外写关于这类型的实现(std::vector<bool>)。
上述是针对类型模板来说的，值模板也是一样。
单说这个似乎在OI中没什么用的样子，我们结合一段笔者写的【模板】线段树 2的神奇代码来看，笔者相信看完这段神奇代码您对线段树的理解会加深一个层次。
#include <bits/stdc++.h>
using namespace std;
template<class T>
struct mll{//取模结构体
T mod;
mll(){}
void set(T a){mod=a;}
template<class T1>
inline T1& operator=(T1 &a){a%=mod;return a;}
template<class T1>
inline T1 operator|(const T1 a){return a%mod;}
};
mll<long long> mod;
#define IT int
template<class T,int count>
struct tree{
tree<T,count-1> ch[2];
/*
出现了！tree<T,count>里包含了tree<T,count-1>
那么tree<T,count-1>里肯定也包含了tree<T,count-2>
这到哪儿停止呢？答案是之后对tree<T,0>进行了特化，使其不包含tree<T,-1>成为单个节点
所以对于任意count>=0都有对应的tree<T,count>的实现
那么不难看出，这是一颗count+1层的满二叉树，底层节点数为(1<<count)，而这个结构正是编译器自动帮我们维护的
*/
#define mid (1ll<<(count-1))
#define tot (1ll<<(count))
T fadd,fsum,fmul;
inline tree(){fadd=fsum=0;fmul=1;}//初始化
//析构靠编译器自动实现
inline void dadd(const T nadd){//处理当前节点的加法操作
mod=fadd+=nadd;
mod=fsum+=mod|nadd*tot;
}
inline void dmul(const T nmul){//处理当前节点的乘法操作
mod=fadd*=nmul;
mod=fmul*=nmul;
mod=fsum*=nmul;
}
inline void pushdown(){//标记下传
ch[0].dmul(fmul);
ch[1].dmul(fmul);
ch[0].dadd(fadd);
ch[1].dadd(fadd);
fadd=0;fmul=1;
}
inline void pushup(){//从两个子树更新sum
mod=fsum=ch[0].fsum+ch[1].fsum;
}
inline void add(IT l,IT r,const T nadd){//区间加法操作
if (l<=1&&tot<=r)//包含该区间
dadd(nadd);
else{
pushdown();
if (l<=mid) ch[0].add(l,r,nadd);//左子树大小为mid
if (r>mid) ch[1].add(l-mid,r-mid,nadd);//借鉴了ranktree的思路，写成这样可以正确处理右子树的区间偏移量问题
pushup();
}
}
inline void mul(IT l,IT r,const T nmul){//区间乘法操作
if (l<=1&&tot<=r)
dmul(nmul);
else{
pushdown();
if (l<=mid) ch[0].mul(l,r,nmul);
if (r>mid) ch[1].mul(l-mid,r-mid,nmul);
pushup();
}
}//发现了mul和add的相似之处了吗?
inline T sum(IT l,IT r){//区间求和
if (l<=1&&tot<=r) return fsum;//包含该区间
pushdown();//下传标记
T ans=0;
if (l<=mid) mod=ans+=ch[0].sum(l,r);
if (r>mid) mod=ans+=ch[1].sum(l-mid,r-mid);
//不更改值，可以无需pushup()
return ans;
}//发现了sum，mul和add的相似之处了吗?
};
template<class T>
struct tree<T,0>{//特化tree<T,0>，即单个节点
/*
注意，上面tree<T,count>的实现对于子树有要求，它要求tree<T,0>有fsum的成员变量和很多东西，不妨就把单个节点的值写成fsum。（你也可以写个get函数，不过笔者偏爱这个方案，它能进一步揭示线段树的本质）
*/
T fsum;
inline tree(){fsum=0;}
inline void dmul(const T nmul){mod=fsum*=nmul;}
inline void dadd(const T nadd){mod=fsum+=nadd;}
inline void add(IT l,IT r,const T nadd){mod=fsum+=nadd;}
inline void mul(IT l,IT r,const T nmul){mod=fsum*=nmul;}
inline T sum(IT l,IT r){return fsum;}
};
tree<long long,17> a;//17层，能够容纳[1,2^17=131072]区间
int main(){
int n,m,mm;
scanf("%d%d%d",&n,&m,&mm);
mod.set(mm);
for (int i=1;i<=n;i++){
long long w;
scanf("%lld",&w);
a.add(i,i,w);
}
for (int i=1;i<=m;i++){
long long opt,l,r,s;
scanf("%lld%lld%lld",&opt,&l,&r);
if (opt==1){
scanf("%lld",&s);
mod=s;//取模
a.mul(l,r,s);
}else if (opt==2){
scanf("%lld",&s);
mod=s;//取模
a.add(l,r,s);
}else{
printf("%lld\n",a.sum(l,r));
}
}
}
跑得慢(2879ms)的很大一部分原因是因为没有O(n)的初始化
类模板的类型模板和非类型模板对于函数同样有效
Part3 C++11时的风景
对于C++98的模板，大家说说有什么可以在将来的C++11标准中加上去的特性。
template <参数列表>
我们要向函数学习一个，参数包怎么不能支持不定参数呢？
还是要提高自己的姿势水平，参数包怎么不能支持默认值呢？
这个参数为什么不能是没带模板的类呢？我们需要一个容器，不需要对它指定参数。
说的有理（好像找不到什么反驳的理由），我们加上吧。
使编译器按照C++11标准编译你的代码需要添加编译命令-std=c++11
DevCpp可以在工具-编译选项-代码生成/优化-代码生成-语言标准(-std)中选择ISO C++11
Part4.1 不定参数模板
不定参数？那这个就带来很多问题了。
怎么使用呢？C++11告诉我们按照类模板写，然后在前面加上...，template<class ...T>就是一个不定参数模板。
怎么获取不定参数呢？C++11告诉我们一种方法，可以按照Part2.3递归调用，顺带还要特化空函数。
下文利用不定参数模板搞了个方便快速读入的函数
void readint(){}//特化
template<class T1,class ...T2>//T2表示一个不定参数模板，接受很多不同类型
void readint(T1 &i,T2&... rest){//T2&表示对于T2里每一个类型添加&修饰符，就是起到一个加上引用的例子
i=0;rc c;bool f=false;
while (!isdigit(c=getchar())) f=c=='-';
do i=(i<<3)+(i<<1)+c-'0'; while (isdigit(c=getchar()));
if (f) i=-i;
readint(rest...);
}
int main(){//然后就可以这样调用了
int a=23;short b=1;long long c=-23599;unsigned d=3638;
readint(a,b,c,d);
/*
编译器生成
readint(int&,short&,long long&,unsigned&)
readint(short&,long long&,unsigned&)
readint(long long&,unsigned&)
readint(unsigned&)
*/
cout << a << endl << b << endl << c << endl << d;
}
思考
template<class ...T1,class ...T2>这样的模板存在吗？
存在
template<class ...T1,class ...T2>
void a(T1*... a,T2... b){}
int w;
a(&w,124);
编译器能认得出来就可以了。
Part4.2 默认值模板
像函数一样添加默认值即可。需要符合无歧义，下面以快速输出为例。
template<class T>
void putint(T a){
if (a<0) putchar('-'),a=-a;
if (a>9) putint(a/10);
putchar(a%10+'0');
}
template<const char split=' '>
void putint(){}
template<const char split=' ',class T,class ...Args>
void putint(T nxt,Args... rest){
putint(nxt);
if (split!=-1) putchar(split);
putint<split>(rest...);
}
int main(){
putint(1,2,3,4,5,6);putchar('\n');
putint<'\n'>(-1,25,9,60,0);
}
Part4.3 模板模板参数
好像在OI中用处不大的样子，找不到比较好的例子（太菜了）。
简单介绍一下，就是说可以传入不指定模板的类型，常见于对容器的二次封装（本人更喜欢继承+重载一点）
template<class T,template<typename U,typename Allocator=allocator<U> > class Container>
class pc:public Container<pair<T,int> >{};
int main(){
pc<long,vector> a;//pc<long,vector>等价于vector<pair<long,int> >
a.push_back(make_pair(124,12));
}
Part5.1 模板的好处
- 简化代码
- 能更好地封装容器了
更工业
Part5.2 模板带来的问题
- 编译速度缓慢
编译器OS：来一个something1<something2>就得生成一个类型，还可能有几种模板嵌套，上文的递归定义更是消耗资源，时至今日还是卡OJ的一种方法。
- 编译错误信息冗长
编译器OS：来一个something1<something2>就得带入原定义检查语法错误，如果something1<T>原定义里调用了T.be()但是带入的something2没定义be()，我怎么知道是something1错了orsomething2错了orsomething1<something2>错了，万一something1又用了其他的模板，只好都报一遍了。
- 生成的程序太大了
编译器OS:来一个something1<something2>就得生成对应汇编码，再怼上上述情况，不大不行啊。
- 不开O2常数大
其实相对STL自己写模板常数不算大了，毕竟又不会有深层封装的情况。s
End
Thanks STL，cppreference.com，Typora
Written by z3475@foxmail.com