C++中的traits技巧

	traits，又被叫做特性萃取技术，用于提取“被传进的对象”对应的信息，让同一个接口实现对应的功能。在STL中，算法和容器是分离的，两者通过迭代器链接。算法需要知道所处理对象的一些信息，萃取器相当于在接口和实现之间加一层封装，来隐藏一些细节并协助调用合适的方法。 如何获取迭代器所指对象的信息，如类型。

获取迭代器所指对象类型的方法

1）函数模板的参数推导机制

template <class I, class T>
void func_impl(I iter, T t) {T tmp; // 迭代器所指物的类型新建的对象...
}template <class I>
inline
void func(I iter) {func_impl(iter, *iter); 
}

	通过func_impl的封装，利用函数模板推导，在func_impl中得到了迭代器所指对象同类型的对象。缺陷：如果需要获取迭代器指向对象除value_type外的其他信息，如difference_type、pointer、reference、iterator_category等。这种方法便不一定适用。并且这种推导的只是参数，无法推导函数的返回值类型。2）函数模板推导 + typedef声明内嵌型别

template <class T>
struct MyIter {typedef T value_type;T * ptr;MyIter(T * p = 0) : ptr (p) {};T& operator* () const { return *ptr;}
};template <class I>
typename I::value_type 
get (I ite) {return *ite;
}MyIter<int> iter( new int(10) );
auto ret = get( iter );

	这种方法不支持原生指针。如，为get传入一个原生指针int*时，I::value_type无法得到int，因为原生指针中无法typedef它的value_type。这时可以利用模板的偏特化特性。3）函数模板推导 + typedef声明内嵌型别 + 函数模板偏特化

template <class I>
typename I::value_type
get (I ite) {...
}template <class I>
I get(I* ite) {...
}template <class I>
I get(const I* ite) {...
}

	利用get函数模板偏特化，对指针和const指针版本做特化。这种方法可行却不够优雅。此时的解决方法可以是引入一个类模板中间层，iterator_traits，不改变get的形式，而将偏特化和typedef声明放于类模板中完成。

STL中的iterator_traits

	iterator模式便提供了这样一种方法：使之能够依序寻访某个聚合物所含的各个元素，而又无需暴露该聚合物的内部表达形式。c++中各个容器的iterator扮演着将数据容器与算法结合起来的重要角色。给算法提供一个访问容器元素的工具，即iterator，将范型算法用于某个容器。使用traits技法，一方面解决了统一了原生指针和自定义iterator被算法使用时的差异，t提供一个统一而简洁的接口，另一方面为为算法提供了关于元素的更丰富的信息，使算法可以选择更高效的实现方式。

#include <iostream>template <class T>
struct iterator_traits {typedef typename T::value_type value_type;
};template <class T>
struct iterator_traits<T*> {typedef T value_type;
};template <class T>
struct iterator_traits<const T*> {typedef T value_type;
};template <class I>
typename iterator_traits<I>::value_type
get (I ite) {...
}

	STL中的iterator_traits定义了以下几种型别：

template<class _Tp>
struct iterator_traits<_Tp*>
{typedef ptrdiff_t difference_type;typedef typename _Tp::value_type value_type;typedef typename _Tp::pointer pointer;typedef typename _Tp::reference reference;typedef typename _Tp::iterator_category iterator_category;
};

type traits

	type_traits是C++11提供的模板元基础库。type_traits可实现在编译期计算、判断、转换、查询等等功能。type_traits提供了编译期的true和false。

STL性能: 通过判断选择更高效的算法

		对于vector这种大块分配内存，然后大块析构的容器，如果容器里面是POD的话，那么只要等它的生命周期结束就行了，如果是非POD的话，那么就要判断是否拥有non trivial的析构函数。这个判断便需要依靠type_traits的偏特化特性进行判断，选择相应的行为（函数）：

POD类型

C++11 POD类型

#include <iostream>namespace my_type_trait{/** 2两个空白类,没有任何成员,不会带来额外负担,却能通过类型代表真假,可以用于函数特化参数 */struct __true_type { };struct __false_type { };template <class _Tp>struct __type_traits {typedef __true_type this_dummy_member_must_be_first;// 不要移除这个成员 // 它通知能自动特化__type_traits的编译器, 现在这个__type_traits template是特化的 // 这是为了确保万一编译器使用了__type_traits而与此处无任何关联的模板时 // 一切也能顺利运作 typedef _false_type has_trivial_default_constructor;//默认构造函数是否有意义？  typedef _false_type has_trivial_copy_constructor;//拷贝构造函数是否有意义?  typedef _false_type has_trivial_assgignment_constructor;//拷贝赋值操作是否有意义?  typedef _false_type has_trivial_destructor;//析构函数是否有意义?  typedef _false_type is_POD_type;//是否为Plain Old Data?  };
}

	对__type_traits类模板，class A可以偏特化出__type_traits<A>，并对has_trivial_destructor进行重新的typedef，改变has_trivial_destructor为_false_type类型或者__true_type类型。对于一个算法模板函数，接收一个__true_type或者__false_type类型的参数，重载出针对_false_type类型和__true_type类型的不同版本。于是，对算法传入class A类型的对象时，便可以根据__type_traits<A>::has_trivial_destructor的类型，选择到相应版本的算法函数。

template <class T>
void doSth(T& t, my_type_trait::__true_type) {std::cout << "true" << std::endl;
}template <class T>
void doSth(T& t, my_type_trait::__false_type) {std::cout << "false" << std::endl;
}template <typename T>
void doSth(T& t) {typedef typename my_type_trait::__type_traits<T>::is_POD_type is_POD_type; doSth(t, is_POD_type());
} class A {
public:
};class B {
};namespace my_type_trait{template <>struct __type_traits<A> {typedef __true_type is_POD_type;};template <>struct __type_traits<B> {typedef __false_type is_POD_type;};
}int main(void) {A a;B b;doSth(a);   // truedoSth(b);   // falsereturn 0;
} 

C++标准库中丰富的type traits

Standard library header <type_traits>

#include <iostream>
#include <type_traits>
using namespace std;int main()
{// 判断int和const int类型std::cout << "int: " << std::is_const<int>::value << std::endl;std::cout << "const int:" << std::is_const<const int>::value << std::endl;// 判断类型是否相同std::cout << std::is_same<int, int>::value << "\n";std::cout << std::is_same<int, unsigned int>::value << "\n";// 添加/移除conststd::cout << std::is_same<const int, add_const<int>::type>::value << std::endl;std::cout << std::is_same<int, remove_const<const int>::type>::value << std::endl;// 添加引用std::cout << std::is_same<int&, add_lvalue_reference<int>::type>::value << std::endl;std::cout << std::is_same<int&&, add_rvalue_reference<int>::type>::value << std::endl;// 取公共类型typedef std::common_type<unsigned char, short, int>::type NumericType;std::cout << std::is_same<int, NumericType>::value << std::endl;// 对于普通类型移除引用、const和volatiletypedef std::decay<int>::type Normal;    // inttypedef std::decay<int&>::type Ref;    // inttypedef std::decay<int&&>::type RefRef;    // inttypedef std::decay<const int&>::type const;    // inttypedef std::decay<int[2]>::type Array;    // int*typedef std::decay<int(int)>::type FunPtr;    // int(*)(int) 函数指针typedef int(&fn_ref)(int);typedef int(*fn_ptr)(int);// 用来获取可调用对象的返回类型typedef std::result_of<fn_ref(int)>::type int_f;    // inttypedef std::reuslt_of<fn_ptr(int)>::type int_s;    // intreturn 0;
}

闭包之binder1st实现

提取并保存一个类型的信息叫做type traits，提取并保存一个函数参数或返回值同理可叫做参数traits或者返回值traits。利用traits手法，可以轻易实现一个仿函数类，binder1st，用于绑定一个仿函数的第一个参数，形成闭包。虽然C++11中对闭包有更好的编译层面的支持——lambda表达式，也不妨碍对简单的binder1st的学习，加深对traits技法的理解。

binder1st的使用：template<class _Arg1,class _Arg2,class _Result>struct binary_function{	// base class for binary functionstypedef _Arg1 first_argument_type;typedef _Arg2 second_argument_type;typedef _Result result_type;};#include <iostream>
#include <functional>template<typename T>
class MLess : public std::binary_function<T, T, bool>
{
public:bool operator() (const T& a, const T& b) const{return a < b;}
};int main(int argc, char** argv)
{auto lessObj = std::bind1st(MLess<int>(), 5);std::cout << lessObj(6) << std::endl;system("pause");return 0;
}binder1st的实现：template<class _Fn2>class binder1st: public unary_function<typename _Fn2::second_argument_type,typename _Fn2::result_type>{	// functor adapter _Func(stored, right)
public:typedef unary_function<typename _Fn2::second_argument_type,typename _Fn2::result_type> _Base;typedef typename _Base::argument_type argument_type;typedef typename _Base::result_type result_type;binder1st(const _Fn2& _Func,const typename _Fn2::first_argument_type& _Left): op(_Func), value(_Left){	// construct from functor and left operand}result_type operator()(const argument_type& _Right) const{	// apply functor to operandsreturn (op(value, _Right));}result_type operator()(argument_type& _Right) const{	// apply functor to operandsreturn (op(value, _Right));}protected:_Fn2 op;	// the functor to applytypename _Fn2::first_argument_type value;	// the left operand};// TEMPLATE FUNCTION bind1st
template<class _Fn2,class _Ty> inlinebinder1st<_Fn2> bind1st(const _Fn2& _Func, const _Ty& _Left){	// return a binder1st functor adaptertypename _Fn2::first_argument_type _Val(_Left);return (binder1st<_Fn2>(_Func, _Val));}

模板迭代与递归

递归模板模式(CRTP)

编译期多态

	使用派生类作为模板参数特化基类：使用派生类覆盖基类成员函数实现静态绑定，可实现编译时多态。使用父类调用直接子类函数，实现多态：1）静态函数成员多态：在父类模板的静态方法中使用模板参数（即子类）的同名静态方法；2）非静态函数成员：通过this指针进行静态转换，在父类模板方法中调用子类同名方法。

#include<iostream>
#include<stddef.h>
using namespace std;
template<class Derived>
struct Base  
{  void Interface()  {  cout <<"come from Interface"<<endl;      // 转换为子类指针，编译期将绑定至子类方法  static_cast<Derived*>(this)->Implementation(); }  static void StaticInterface()  {  // 编译期将绑定至子类方法  cout <<"come from StaticInterface"<<endl;Derived::StaticImplementation();  }  void Implementation(){cout <<"Base Implementation"<<endl;return;}static void StaticImplementation(){cout << "Base StaticImplementation"<<endl;return;}
};  // The Curiously Recurring Template Pattern (CRTP)  
struct Derived1 : Base<Derived1>  
{  static void StaticImplementation();  
};  struct Derived2 : Base<Derived2>  
{  void Implementation();  
};  

编译期递归计算

	利用模板递归的特性，模板特例化为递归终止条件，在编译期计算出递归结果。优点：1）编译时就把数据计算出来了，对于运行时的大数据递归计算效率大大提高了缺点：1）编译时间的损失2）代码可读性有些损失3）调试困难4）不能计算变量的值，也就是对于运行时确定的数据是不能通过模板递归出来的5）不能进行异常处理，也就是模板参数传入一个错误的数字后可能导致崩溃

计算斐波那契数列：template< int n >
struct Factorial{const static int value = Factorial< n-1 >::value * n;
};template<>
struct Factorial< 0 >{const static int value = 1;
};计算幂：template< int m, int n >
struct POWER{static const size_t data=POWER< m,  n-1 >::data * m;
};template< int m >
struct POWER< m, 0 >{static const size_t data = 1;
};计算阶乘：template < unsigned int N >
struct FactR{ enum { Val = N * FactR::Val }; 
};template <> 
struct FactR < 1 >
{enum {Val = 1};

变长模板的迭代与递归

	通过变长模板，对传入的个数变化的模板参数依次解包，实例化出不同参数的模板对参数进行处理，应对不定数量的参数的情况。

#include <iostream>
#include <vector>
#include <functional>
using namespace std;template<class... Args>
void fun (Args... args) {function<bool (int)> check = [] (int t) {if (t == 3) {cout << "find 3" << endl;} else {cout << t << " is not 3" << endl;}return t != 3;};vector<function<bool ()>> fun = { bind (check, args)... };for (auto f : fun) {if (!f ()) break;}
}int main (int argc, char* argv []) {fun (1,2,5,7,9,3,5,6);return 0;
}

	以上程序对输入的任意长度的参数，按照顺序寻找数值等于3的数。对输入的n个参数，为每个参数实例化出一个仿函数，存储在vector中，依次调用，寻找数值3。

可变参数hash函数

//计算种子数值
template<typename T>
inline void hash_combine(size_t& seed, const T& val)
{seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}//递归调用出口
template<typename T>
inline void hash_val(size_t& seed, const T& val)
{hash_combine(seed, val);
}template<typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Types&... args)
{//重新计算种子值hash_combine(seed, val);//递归调用hash_val(seed, args...);
}template<typename... Types>
inline size_t hash_val(const Types&... args)
{size_t seed = 0;hash_val(seed, args...);return seed;
}