標題：C++ template(模板) 初探

作者：z3475

鏈接：z3475.blog.luogu.org/c-

本文詳細地講解了C++template（模板）的用途。

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
",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
",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(
);
putint<
>(-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 模板的好處

  1. 簡化代碼
  2. 能更好地封裝容器了
  3. 更工業

Part5.2 模板帶來的問題

  1. 編譯速度緩慢

編譯器OS：來一個something1<something2>就得生成一個類型，還可能有幾種模板嵌套，上文的遞歸定義更是消耗資源，時至今日還是卡OJ的一種方法。

  1. 編譯錯誤信息冗長

編譯器OS：來一個something1<something2>就得帶入原定義檢查語法錯誤，如果something1<T>原定義裏調用了T.be()但是帶入的something2沒定義be()，我怎麼知道是something1錯了orsomething2錯了orsomething1<something2>錯了，萬一something1又用了其他的模板，只好都報一遍了。

  1. 生成的程序太大了

編譯器OS:來一個something1<something2>就得生成對應彙編碼，再懟上上述情況，不大不行啊。

  1. 不開O2常數大

其實相對STL自己寫模板常數不算大了，畢竟又不會有深層封裝的情況。s

End

Thanks STL，cppreference.com，Typora

Written by z3475

搬運者: 知乎@方舟 Minecraft玩家｜「醉後不知天在水，滿船清夢壓星河。」

本文一切權利歸原作者所有，已獲得轉載許可/按原作者要求註明轉載鏈接。如有不足之處，歡迎指正！請給?我的Telegram發消息。

「知乎搬運申明」

「微信支付?」二維碼

推薦閱讀：

相關文章