c++11通过变参模板实现特殊的数据结构和算法

原创 2017年11月17日 16:20:05

    C++11中增加了变长模板参数,可以替代c语言中的...参数(比如printf系列函数)。c语言中的...参数使用va_list来解析,在运行时通过对char*指针的强转达到使用参数的目的,所以当传参类型和实际处理...参数的函数代码中要求的单数类型不一致时,会引起编译时期发现不了的问题,严重可能导致程序崩溃。

   C++11中变长模板参数的语法就不多说了,最开始使用的时候总会觉得用法和参数展开方式都很诡异(其实大多的c++11或者是后来的14,17的新特性相对于以前的标准来说都略显诡异),但是经过一个过程熟悉了之后也是能接受的。

   引用一段摘抄:C++11定义了可以展开包的几个地方:

        1. 表达式
        2. 初始化列表
        3. 基类描述列表
        4. 类成员初始化列表
        5. 模板参数列表
        6. 通用属性列表
        7. lamda函数的捕捉列表

    其他地方是不能展开的。

    这些展开的过程都由语言本身完成了,展开过程中,自己无法直接知道哪个位置参数具体是什么类型,什么值,那该怎么得到呢?

    这其中的技巧无外乎是以“递归”的方式一个个的将类型和值从参数包中剥离出来。

    比如你可以很容易实现一个链式继承的模板类,其实msvs版本的std::tuple就是类似这样的实现。下面提供一个简单的例子:

template<typename _This, typename... _Others>
class T<_This, _Others...> : public T<_Others...>
{
public:
	typedef _This type;
	size_t _size = sizeof...(_Others) + 1;
};
template<>
class T<> {};
    可以看出class T有一个模板参数为空的特化版本,可以理解为递归实现的退出条件(参考递归函数写法,里面都应该会有一个边界退出条件,不然就会死递归,一样的道理),再看std::tuple实现,其中一样有类似的退出条件的特化版本。

    各大论坛或问答网站可以搜索到很多c++11变参版本的printf和sum函数的实现,写法也都大同小异,运用递归的思想。

    不过要理解的是看似写法是递归,其实最终生成的代码却并不是递归,因为“class T<_This, _Others...> 和 class T<_Others...>并不是同一个类。


下面来讨论实现特殊的数据结构:

    1).参照std::tuple<int, double, std::string, bool>的使用方式,实现一个multi_key_map<int, double, std::string, bool>,要求是这个数据结构如果有n个类型参数,则使用前n-1个参数共同组成一个key,最后一个参数为实际的value(有很多使用场景,比如通过班级(参数1)和名字(参数2)定位到一个唯一的学生(参数3))

        很容易想到的做法是把前n-1个类型转换成一个std::tuple,所以实际的需求就变成了“multi_key_map<int, double, std::string, bool> => std::map<std::tuple<int, double, std::string>, bool>”,代码如何实现呢???敬请期待。。。(其实如果把第0个类型参数认为是value,后面的n-1个类型参数认为是构成tuple的参数会简单很多,但是那样就不符合常规map的定义习惯了)已更新,代码如下:

	template <size_t _Index, typename _Key, typename... _Keys_Value>
	class multi_key_map_helper : public multi_key_map_helper<_Index - 1, _Keys_Value...>
	{
	public:
		typedef multi_key_map_helper<_Index - 1, _Keys_Value...> _BaseTy;
		typedef typename decltype(
			std::tuple_cat<std::tuple<std::remove_const_t<std::remove_reference_t<_Key>>>
			, typename _BaseTy::key_type>(std::declval<std::tuple<std::remove_const_t<std::remove_reference_t<_Key>>>>()
				, std::declval<_BaseTy::key_type>())) key_type;
		typedef typename _BaseTy::value_type value_type;
	};

	template <typename _Key, typename _Value>
	class multi_key_map_helper<2, _Key, _Value>
	{
	public:
		typedef typename std::tuple<std::remove_const_t<std::remove_reference_t<_Key>>> key_type;
		typedef typename std::remove_const_t<std::remove_reference_t<_Value>> value_type;
	};

	template <typename... _Keys_Value>
	class multi_key_map_helper<1, _Keys_Value...>
	{};
	
	template <typename... _Keys_Value>
	class multi_key_map_helper<0, _Keys_Value...>
	{};

	template< typename... _Keys_Value>
	using multi_key_map = std::map<typename multi_key_map_helper<sizeof...(_Keys_Value), _Keys_Value...>::key_type
		, typename multi_key_map_helper<sizeof...(_Keys_Value), _Keys_Value...>::value_type>;

        其中“_Index”参数为“2”的特化版本为临界退出条件。可以看到还特化了“_Index”参数为“1”和“0”的两个版本,则是为了在参数不合法时能够报告错误,因为从“multi_key_map”的定义并不能直观看出至少需要多少个模板参数,那么假如用户使用类似“multi_key_map<>”或者“multi_key_map<int>”的代码则会报错。

        当然还有另一个使用起来更直观的“multi_key_map”定义方式,可以去掉特化版“_Index”参数为“1”和“0”的实现部分,代码如下:

	template<typename _Key, typename _Key_Value, typename... _Keys_Value>
	using multi_key_map = std::map<typename multi_key_map_helper<2 + sizeof...(_Keys_Value), _Key, _Key_Value, _Keys_Value...>::key_type
		, typename multi_key_map_helper<2 + sizeof...(_Keys_Value), _Key, _Key_Value, _Keys_Value...>::value_type>;

    2).基于上面一个例子,如果key是一个tuple,那么,当使用一个类型模板参数数量太多的tuple做key时,每一次比较操作都需要对tuple的每一个成员逐一运算,性能会存在明显下降,那能不能实现一种新的数据结构:level_map<int, double, std::string, bool>,其表示的实际数据结构是std::map<int, std::map<double, std::map<std::string, bool>>>,在key组合数量过多的时候性能下降不会像multi_key_map那么明显,那代码该如何实现呢???敬请期待。。。已更新,代码如下:

        实现1.

	template <size_t _Index, typename _Tuple_Value>
	class convert_map_helper : public convert_map_helper<_Index - 1, _Tuple_Value>
	{
	public:
		typedef convert_map_helper<_Index - 1, _Tuple_Value> _BaseTy;
		typedef std::map<std::tuple_element_t<std::tuple_size<_Tuple_Value>::value - _Index, _Tuple_Value>, typename _BaseTy::type> type;
	};

	template <typename _Tuple_Value>
	class convert_map_helper<2, _Tuple_Value>
	{
	public:
		typedef std::map<std::tuple_element_t<std::tuple_size<_Tuple_Value>::value - 2, _Tuple_Value>
		, std::tuple_element_t<std::tuple_size<_Tuple_Value>::value - 1, _Tuple_Value>> type;
	};

	template <typename _Tuple_Value>
	class convert_map_helper<1, _Tuple_Value>
	{};

	template <typename _Tuple_Value>
	class convert_map_helper<0, _Tuple_Value>
	{};

	template<typename _Tuple_Value>
	using convert_map = typename convert_map_helper<std::tuple_size<_Tuple_Value>::value, _Tuple_Value>::type;

	template <typename... _Keys_Value>
	class level_map_helper
	{
	public:
		typedef std::tuple<std::remove_const_t<std::remove_reference_t<_Keys_Value>>...> _Tuple;
		typedef typename convert_map_helper<std::tuple_size<_Tuple>::value, _Tuple>::type type;
	};

	template<typename... _Keys_Value>
	using level_map = typename level_map_helper<_Keys_Value...>::type;

        实现2.

	template <size_t _Index, typename _Key, typename... _Keys_Value>
	class level_map_helper2 : public level_map_helper2<_Index - 1, _Keys_Value...>
	{
	public:
		typedef level_map_helper2<_Index - 1, _Keys_Value...> _BaseTy;
		typedef typename std::map<std::remove_const_t<std::remove_reference_t<_Key>>, typename _BaseTy::type> type;
	};

	template <typename _Key, typename _Value>
	class level_map_helper2<2, _Key, _Value>
	{
	public:
		typedef typename std::map<std::remove_const_t<std::remove_reference_t<_Key>>
			, std::remove_const_t<std::remove_reference_t<_Value>>> type;
	};

	template <typename... _Keys_Value>
	class level_map_helper2<1, _Keys_Value...>
	{};

	template <typename... _Keys_Value>
	class level_map_helper2<0, _Keys_Value...>
	{};

	template< typename... _Keys_Value>
	using level_map2 = typename level_map_helper2<sizeof...(_Keys_Value), _Keys_Value...>::type;
        实现2中一样可以如上面一个例子一样,将“level_map”的定义改为:
	template<typename _Key, typename _Key_Value, typename... _Keys_Value>
	using level_map2 = typename level_map_helper2<2 + sizeof...(_Keys_Value), _Key, _Key_Value, _Keys_Value...>::type;
        实现1借助了std::tuple的特性(可以直接从变长参数构造一个std::tuple类型,而std::tuple_element则可以剥离std::tuple中的每一个类型参数),使用递归一层层构造最终的std::map,而实现二则更直接。


    3).个人认为std::tuple是旨在替代没有成员函数的struct(暂时不计较它的具体实现,至少由它提供的使用方法和api来看可以这么理解),所以,把它当成是各个类型参数通过成员方式的组合的话,那可不可以实现一个类级别的组合结构type_tuple(类似设计模式中的对象适配和类适配)呢?比如,type_tuple<std::string, std::wstring>是一个新类,其继承自std::string和std::wstring类,代码如何实现呢???敬请期待。。。已更新,代码如下:

template <typename... _Ty>
class type_tuple : virtual public _Ty...
{
public:
	type_tuple(_Ty&&... value) : _Ty(value)...{}
};

    三个例子中使用的技巧各不相同,第一个例子最为复杂,主要是因为keys的类型(std::tuple)并不像第二个例子中的std::map那么容易递归实现,期间使用了std::tuple_cat和decltype还有std::declval配合转换,看起来很复杂,不过因为这些工作都是在编译期进行的所以在实际运行中并不会对性能有什么影响,唯一要注意的可能是编译时间可能会因此而变长,第三个例子相对简单,因为直接利用了变参模板可以在“基类描述列表”中展开的特性。

    当然使用变参模板还可以实现其他很多的函数,比如变参的printf,sum,max等等,因为各大论坛网帖中都能很容易的找到,这里就不再赘述。

    在gcc中例1和例2中“_Index”参数为“1”和“0”的特化版本编译不过,需要修改成:

template <typename _Value>
class multi_key_map_helper<1, _Value>
{};

template <typename _Value>
class multi_key_map_helper<0, _Value>
{};

    “level_map_helper2”同上


总结:

    变长模板参数运用确实是可以很灵活,因为是编译时期的特性,所以可以用它来实现很多灵活的数据结构封装,并且由于其相对于c传统的变参函数更安全,使用更简单,使用它来写变参函数也是更加不错的选择,同时,于传统变参相比,其参数列表扩展情形更多,使用场景也就更多,所以会有很多奇妙的用法等着你发现。


版权声明:本文为博主原创文章,未经博主允许不得转载。

C++11中的变参模板的使用

在新的C++11标准里提供了变参模板,这个类似于在C语言里的printf这个打印函数,参数可以是随机的。当时记得在写嵌入式底层的时候儿需要实现一个类似于printf的函数,还使用var_start,v...
  • fpcc
  • fpcc
  • 2017年01月16日 10:59
  • 1243

泛化之美--C++11可变模版参数的妙用

泛化之美--C++11可变模版参数的妙用 1概述 C++11的新特性--可变模版参数(variadic templates)是C++11新增的最强大的特性之一,它对参数进行了高度泛化,...
  • linuxheik
  • linuxheik
  • 2016年07月07日 17:19
  • 2931

C++11变参模板的参数包

Parameter pack 原文来自这里 A template parameter pack is a template parameter that accepts zero or more t...
  • zhouguoqionghai
  • zhouguoqionghai
  • 2015年09月22日 21:01
  • 3787

C++ 11 可变模板参数详解

C++ 11 可变模板参数详解1. 概述​ 可变模板参数(variadic templates)是C++ 11新增的最强大的特性之一,它对参数进行高度泛化,它能表示0到任意个数、任意类型的参数。2...
  • zt_xcyk
  • zt_xcyk
  • 2017年06月29日 15:24
  • 212

图_dijkstra算法【数据结构实践报告】

数据结构实验报告 实验名称: 实验七 图 dijkstra算法 学号:*** 姓名:gnosed 实验日期:2017.12.23   一、实验目的 掌握求最短路径的Dijkstra算法 ...
  • gnosed
  • gnosed
  • 2017年12月23日 02:40
  • 119

【C++】C++11特性:模板推导和循环区间

模板推导C++11在template编程的领域有很大的更新,功能愈发强大了,引入变参模板、外部模板等新功能,大大增强了模板编程的能力,其中新特性Tuple元组使用了变参模板特性。其中用的最多的,是模板...
  • lpsl1882
  • lpsl1882
  • 2016年10月02日 13:07
  • 335

C++11可变参数函数模板

在Log时参数是类型和个数是不固定的,所以在做log函数时,很多烦恼,不过C++11给我们带来的希望 这个是今天刚读到的,加上自己的理解为字节写了一个logger类,也给大家瞧瞧啊,欢迎大虾拍板...
  • zhx6044
  • zhx6044
  • 2013年04月27日 13:34
  • 4674

使用模板元编程操作类型集合(C++11下的TypeList)

Wrote by mutouyun. (http://darkc.at/cxx-type-list/) 群里有个朋友要实现这么一个功能:如何在编译期把一个函数类型的参数减少一个。 简单来说...
  • markl22222
  • markl22222
  • 2014年05月28日 22:44
  • 1885

<C/C++数据结构>队列(C++模板实现)

一,队列的基本概念 队列特性:先进先出(FIFO)——先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。...
  • EbowTang
  • EbowTang
  • 2015年02月01日 23:21
  • 1297

c++11 条款1:理解模板类型推导

前言 c++98有单独一套类型推导规则:适用用函数模板。c++11修改了这套规则并且增加了两个,一个是auto,一个是decltype。c++14扩展了auto和decltype使用的场景。随着类型推...
  • coolmeme
  • coolmeme
  • 2015年03月03日 15:17
  • 7027
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:c++11通过变参模板实现特殊的数据结构和算法
举报原因:
原因补充:

(最多只允许输入30个字)