C++模板学习笔记

一个有趣的东西：实现一个函数print, 输入一个数组, 输出数组的各个维度长度。

eg.
int a[2], b[3][4], c[5][6][7];
print(a);   //(2, 4)
print(b);   //(3, 16) (4, 4)
print(c);   //(5, 168) (6, 28) (7, 4)

template<typename T>
void print(const T &A) {
    printf("
");
}
template<typename T, int N>
void print(const T (&A)[N]) {
    printf("(%d, %d) ", N, sizeof(A[0]));
    print(A[0]);
}

View Code

学习版块

https://github.com/wuye9036/CppTemplateTutorial 空明流转

typename与class

在 C++ Template 中很多地方都用到了 typename 与 class 这两个关键字，而且好像可以替换，是不是这两个关键字完全一样呢?
相信学习 C++ 的人对 class 这个关键字都非常明白，class 用于定义类，在模板引入 c++ 后，最初定义模板的方法为：
template<class T>......
这里 class 关键字表明T是一个类型，后来为了避免 class 在这两个地方的使用可能给人带来混淆，所以引入了 typename 这个关键字，它的作用同
class 一样表明后面的符号为一个类型，这样在定义模板的时候就可以使用下面的方式了：
template<typename
T>......
在模板定义语法中关键字 class 与 typename 的作用完全一样。
typename 难道仅仅在模板定义中起作用吗？其实不是这样，typename 另外一个作用为：使用嵌套依赖类型(nested depended name)，如下所示：
class MyArray 
{ 
    public：
    typedef int LengthType;
.....
}

template<class T>
void MyMethod( T myarr ) 
{ 
    typedef typename T::LengthType LengthType; 
    LengthType length = myarr.GetLength; 
}
这个时候 typename 的作用就是告诉 c++ 编译器，typename 后面的字符串为一个类型名称，而不是成员函数或者成员变量，这个时候如果前面没有
typename，编译器没有任何办法知道 T::LengthType 是一个类型还是一个成员名称(静态数据成员或者静态函数)，所以编译不能够通过。

View Code

eg1.

 1 template <typename T> struct X {};
 2 template <typename T> struct Y
 3 {
 4     // X可以查找到原型；
 5     // X<T>是一个依赖性名称，模板定义阶段并不管X<T>是不是正确的。
 6     typedef X<T> ReboundType;
 7     
 8     // X可以查找到原型；
 9     // X<T>是一个依赖性名称，X<T>::MemberType也是一个依赖性名称；
10     // 所以模板声明时也不会管X模板里面有没有MemberType这回事。
11     typedef typename X<T>::MemberType MemberType2;
12     
13     // UnknownType 不是一个依赖性名称
14     // 而且这个名字在当前作用域中不存在，所以直接报错。
15     // typedef UnknownType MemberType3;    
16 
17     void foo()
18     {
19         X<T> instance0;
20         typename X<T>::MemberType instance1;
21     }
22 };

View Code

eg2.

 1 struct A;
 2 template <typename T> struct B;
 3 template <typename T> struct X {
 4     typedef X<T> _A; // 编译器当然知道 X<T> 是一个类型。
 5     typedef X    _B; // X 等价于 X<T> 的缩写
 6     typedef T    _C; // T 不是一个类型还玩毛
 7     
 8     // ！！！注意我要变形了！！！
 9     class Y {
10         typedef X<T>     _D;          // X 的内部，既然外部高枕无忧，内部更不用说了
11         typedef X<T>::Y  _E;          // 嗯，这里也没问题，编译器知道Y就是当前的类型，
12                                       // 这里在VS2015上会有错，需要添加 typename，
13                                       // Clang 上顺利通过。
14         typedef typename X<T*>::Y _F; // 这个居然要加 typename！
15                                       // 因为，X<T*>和X<T>不一样哦，
16                                       // 它可能会在实例化的时候被别的偏特化给抢过去实现了。
17     };
18     
19     typedef A _G;                   // 嗯，没问题，A在外面声明啦
20     typedef B<T> _H;                // B<T>也是一个类型
21     typedef typename B<T>::type _I; // 嗯，因为不知道B<T>::type的信息，
22                                     // 所以需要typename
23     //typedef B<int>::type _J;        // B<int> 不依赖模板参数，
24                                     // 所以编译器直接就实例化（instantiate）了
25                                     // 但是这个时候，B并没有被实现，所以就出错了
26 };

View Code

自己的理解：什么时候需要typename？如果编译器无法判断当前名称代表的是类型还是实例的时候，需要用typename来表示指代类型。如果遇到T::size_type * p; 无法知道是乘法运算还是定义指针。这时候，当我们希望通知编译器一个名字表示类型时，必须用关键字typename，而不是class。则为typename T::size_type *p;

============================分割线============================

引用折叠

引用折叠只能应用于间接创建的引用的引用，如类型别名或模板参数。

& &&，&& &，& &折叠后都是左值引用&; && &&折叠后是右值引用&&。

模板实参推断与引用

其中i是int，ci是const int.

template<typename T> void f1(T&); // 实参必须是左值，const属性得到保持

f1(i); //T是int

f1(ci); //T是const int

f1(5); //error, 必须是左值

template<typename T> void f2(const T&); //可以接受右值

f2(i);

f2(ci);

f2(5); //以上T均为int

template<typename T> void f3(T&&); //实参为左值，T为左值引用；实参为const左值，T为const左值引用；实参为右值，T为右值引用

f3(i); //T是int&

f3(ci); //T是const int&

f3(5); //T是int&&

T&&，对应的const属性和左值/右值属性将得到保持。T&&可以实现转发，保持转发参数的所有性质，包括const和左右值。

移动与完美转发

std::move 如下.

/// remove_reference
template<typename _Tp>
struct remove_reference
{ typedef _Tp   type; };

template<typename _Tp>
struct remove_reference<_Tp&>
{ typedef _Tp   type; };

template<typename _Tp>
struct remove_reference<_Tp&&>
{ typedef _Tp   type; };

template <typename T>
typename remove_reference<T>::type&& move(T&& t) {
    return static_cast<typename remove_reference<T>::type&&>(t);
}

std::forward.

template <typename T>
T&& forward(typename remove_reference<T>::type& param) 
{
    return static_cast<T&&>(param);    
}

eg.

template<typename T>
void foo(T&& fparam)
{
    std::forward<T>(fprams);    
}

int i = 7;
foo(i);//T为int&，std::forward<T>(fprams)的类型为int & &&，折叠后为int &
foo(47);//T为int, std::forward<T>(fprams)的类型为int &&

//通过完美转发，可以简化代码，其中m_var1和m_var2是全局变量
void set(const string & var1, const string & var2) {
    //拷贝赋值
    m_var1 = var1;
    m_var2 = var2;
}
void set(string && var1, string && var2){
    //移动赋值
    m_var1 = std::move(var1);//move不能省略，具名变量都被当作左值
    m_var2 = std::move(var2);
}
//以上两个函数可以用以下函数代替
template<typename T1, typename T2>
void set(T1 && var1, T2 && var2){
    m_var1 = std::forward<T1>(var1);
    m_var2 = std::forward<T2>(var2);
}
//注：forward常用于template函数中，必须要多带一个参数forward<T>

可变参数函数模板(variadic function template)

主要使用了包扩展(pack expansion)的方式, 即"...", 把一个模式(pattern)扩展为包中每一个元素(element)的形式;

可变参数函数模板, 常使用递归(recursive)进行处理包(pack)参数,

需要一个非可变参数(nonvariadic)函数模板,结束递归, 当最后一次调用时, 调用非可变参数版本, 则递归结束;

还需要一个绑定(bing)的参数, 处理包(pack)中的一些元素, 通过递归,顺次处理包中的元素;

包扩展可以应用于各种形式, 如

函数的模板参数, 例如: templae<typename... Args> 扩展后即 template<typename Args1, typename Args2, typename Args3>

函数的参数模板, 例如: cosnt Args&... rest 扩展后即const Args& rest1, const Args& rest2, const Args& rest3

函数的形参, 例如: rest... 扩展后即rest1, rest2, rest3

函数模板, 例如: debug_rep(rest)...扩展后即debug_rep(rest1), debug_rep(rest2), debug_rep(rest3) //debug_rep是模板函数名

eg.

 1 #include <iostream>  
 2 #include <sstream>  
 3   
 4 using namespace std;  
 5   
 6 //返回bug信息  
 7 template <typename T> 
 8 std::string debug_rep (const T& t)  
 9 {  
10     std::ostringstream ret;  
11     ret << t;  
12     return ret.str();  
13 }  
14   
15 //非可变参数模板  
16 template<typename T>  
17 std::ostream &print(std::ostream &os, const T &t)  
18 {  
19     //std::cout << "This is nonvariadic function! ";  
20     return os << t;  
21 }  
22   
23 //可变参数模板, "..."是包扩展(Pack Expansion)  
24 template <typename T, typename... Args>  
25 std::ostream &print(std::ostream &os, const T &t, const Args&... rest)  
26 {  
27     os << t << ", ";  
28     return print(os, rest...);  
29 }  
30   
31 //函数模板的包扩展  
32 template <typename... Args>  
33 std::ostream &errorMsg(std::ostream &os, const Args&... rest)  
34 {  
35     return print(os, debug_rep(rest)...); //使用模板的包扩展  
36 }  
37   
38 int main()  
39 {  
40     int i(10); std::string s("girls");  
41     //print(std::cout, i, s, 42);  
42     errorMsg(std::cout, i, s, 10, "ladies");  
43   
44     return 0;  
45 }

C++11中的tuple就是可变参数类模板，在github找到了一份实现代码。(这个人好像还实现了好多别的东西，比如红黑树，堆排序，哈希表)

 1 #include <iostream>
 2 
 3 template<typename ... Types> class Tuple;
 4 template<> class Tuple<> {};
 5 template<typename First, typename ... Rest>
 6 class Tuple<First, Rest...>: private Tuple<Rest...> {
 7   First Member;
 8  public:
 9   Tuple(const First& first, const Rest& ... rest):
10       Tuple<Rest...>(rest...), Member(first) {}
11   
12   const First& Head() const {
13     return Member;
14   }
15   
16   const Tuple<Rest...>& Tail() const {
17     return *this;
18   }
19 };
20 
21 
22 // As a return value of Get<>(Tuple) method is not a reference,
23 // in order to make it available to return POD types.
24 
25 template<size_t I, class T>
26 struct TupleElement;
27 
28 template<size_t I, class Head, class ... Rest>
29 struct TupleElement<I, Tuple<Head, Rest...> >:
30     public TupleElement<I - 1, Tuple<Rest...> > {
31   static typename TupleElement<I, Tuple<Head, Rest...> >::Type
32       Get(const Tuple<Head, Rest...>& t) {
33     return TupleElement<I - 1, Tuple<Rest...> >::Get(t.Tail());
34   }
35 };
36  
37 template<class Head, class ... Rest>
38 struct TupleElement<0, Tuple<Head, Rest...> > {
39   typedef Head Type;
40   static typename TupleElement<0, Tuple<Head, Rest...> >::Type
41       Get(const Tuple<Head, Rest...>& t) {
42     return t.Head();
43   }
44 };
45 
46 template<size_t Pos, class Head, class ... Rest>
47 typename TupleElement<Pos, Tuple<Head, Rest...> >::Type
48     Get(const Tuple<Head, Rest...>& t) {
49   return TupleElement<Pos, Tuple<Head, Rest...> >::Get(t);
50 }
51 
52 int main() {
53   Tuple<int, double, char> t(42, 3.14, 'a');
54   std::cout << Get<0>(t) << std::endl;
55   std::cout << Get<1>(t) << std::endl;
56   std::cout << Get<2>(t) << std::endl;
57   return 0;
58 }

转发参数包

组合使用forward机制与可变参数模板实现转发参数包。《C++ primer 5th》16.4.3

============================分割线============================

模板元编程

(黑魔法：编译期间完成计算，如斐波那契，平方根等)

eg.斐波那契等

 1 #include <bits/stdc++.h>
 2 
 3 template<int N>
 4 struct Fac{
 5     static int const result = Fac<N-1>::result + Fac<N-2>::result;
 6 };
 7 template<>
 8 struct Fac<0>{
 9     static int const result = 0;
10 };
11 template<>
12 struct Fac<1>{
13     static int const result = 1;
14 };
15 /*
16 推荐使用enum
17 静态成员变量只能是左值
18 如果遇到void foo(int const&);
19 foo(Fac<7>::result);
20 编译器将传递Fac<7>::result的地址,
21 会强制编译期实例化静态成员的定义,
22 并为该定义分配内存,
23 于是该计算将不局限于完全的“编译期”效果
24 而enum不是左值, 会以常量的形式传递参数
25 以上抄自<<C++ template(中文版)>>P296
26 */
27 
28 template<int N>
29 struct Sum{
30     enum{result = N+Sum<N-1>::result};
31 };
32 template<>
33 struct Sum<0>{
34     enum{result = 0};
35 };
36 
37 int main(){
38     std::cout << Fac<46>::result << std::endl;
39     //std::cout << Fac<47>::result << std::endl; // without Fac<46>, compile error
40     std::cout << Sum<900>::result << std::endl;
41     //std:cout << Sum<901>::result << std::endl; // without Sum<900>, compile error
42     std::cout << Sum<1800>::result << std::endl; // OK
43     //std::cout << Sum<1801>::result << std::endl; // without Sum<1800>, compile error
44     return 0;
45 }

eg. Sqrt简易版本

 1 //easy版本, ：？条件表达式会同时实例化Sqrt<20, 0, 9>, Sqrt<20, 10, 20>
 2 #include <bits/stdc++.h>
 3 template<int N, int L = 0, int R = N>
 4 class Sqrt{
 5 public:
 6     enum{m = (L+R+1) >> 1};
 7     enum{result = m*m > N? Sqrt<N, L, m-1>::result : Sqrt<N, m, R>::result};
 8 };
 9 template<int N, int L>
10 class Sqrt<N, L, L>{
11 public:
12     enum{result = L};
13 };
14 
15 int main(){
16     std::cout << Sqrt<20>::result;
17     return 0;
18 }

tips：可以通过typedef+IfThenElse模板优化条件表达式

 1 #include <bits/stdc++.h>
 2 
 3 #ifndef IFTHENELSE
 4 #define IFTHENELSE
 5 template<bool C, typename Ta, typename Tb>
 6 class IfThenElse;
 7 
 8 //局部特化
 9 template<typename Ta, typename Tb>
10 class IfThenElse<true, Ta, Tb>{
11 public:
12     typedef Ta Result;
13 };
14 template<typename Ta, typename Tb>
15 class IfThenElse<false, Ta, Tb>{
16 public:
17     typedef Tb Result;
18 };
19 #endif
20 
21 template<int N, int L = 0, int R = N>
22 class Sqrt{
23 public:
24     enum{m = (L+R+1) >> 1};
25     typedef typename IfThenElse<
26         (m*m > N), 
27         Sqrt<N, L, m-1>,
28         Sqrt<N, m, R>
29     >::Result SubT;    //定义typedef不会实例化
30     enum{result = SubT::result};
31 };
32 template<int N, int L>
33 class Sqrt<N, L, L>{
34 public:
35     enum{result = L};
36 };
37 
38 int main(){
39     std::cout << Sqrt<20>::result;
40     return 0;
41 }

迭代版本

 1 #include <bits/stdc++.h>
 2 
 3 #ifndef IFTHENELSE
 4 #define IFTHENELSE
 5 template<bool C, typename Ta, typename Tb>
 6 class IfThenElse;
 7 
 8 //局部特化
 9 template<typename Ta, typename Tb>
10 class IfThenElse<true, Ta, Tb>{
11 public:
12     typedef Ta Result;
13 };
14 template<typename Ta, typename Tb>
15 class IfThenElse<false, Ta, Tb>{
16 public:
17     typedef Tb Result;
18 };
19 #endif
20 
21 template<int N>
22 class Value{
23 public:
24     enum{result = N};
25 };
26 template<int N, int I = 0>
27 class Sqrt{
28 public:
29     typedef typename IfThenElse<
30         ((I+1)*(I+1) > N), 
31         Value<I>, //i, 特意构造一个Value类
32         Sqrt<N, I+1>
33     >::Result SubT;
34     
35     enum{result = SubT::result};
36 };
37 
38 int main(){
39     std::cout << Sqrt<20>::result;
40     return 0;
41 }

未完待续