0CCh Blog

序列和迭代器(3)

admin
CPP

list序列的更多元函数

那么目前为止，我们完成了list序列7组基本元函数的调用和验证。不过我们不会就此满足，因为以上元函数能完成的工作有限，为了让序列能完成更多实用的功能，我们还需要进一步的对基础元函进行组合。有一个特别的好消息是，由于后续介绍的元函数都是由以上7组基本元函数组合而成，所以它们可以在任何正向迭代器的序列中使用。不仅如此，如果不是特别在意编译期的效率问题的话，将他们应用于双向迭代器或者随机访问迭代器的序列也是可以的。当然我并不推荐这么做，因为对于双向迭代器或者随机访问迭代器的序列，它们可以使用更灵活的方法操作和访问内部元素。

push_front元函数

template <class Tag>
struct push_front_impl {
  template <class R, class I, class E>
  struct apply_impl {
    using inner = typename push_back<R, typename deref<I>::type>::type;
    using type = typename apply_impl<inner, typename next<I>::type, E>::type;
  };

  template <class R, class E>
  struct apply_impl<R, E, E> {
    using type = R;
  };

  template <class T, class U>
  struct apply {
    using init = typename push_back<typename clear<T>::type, U>::type;
    using type = typename apply_impl<init, typename begin<T>::type,
                                     typename end<T>::type>::type;
  };
};

template <class T, class U>
struct push_front
    : push_front_impl<typename sequence_tag<T>::type>::template apply<T, U> {};

从上面的代码可以看出push_front是一个极为典型的组合元函数，它使用begin、end、deref、clear和push_back两个元函数的组合，所以它可以用于任何正向迭代器的序列。不过达到这个目的的代价可以不小，因为这个操作从效率上来说是很低的。观察push_front_impl的实现可知，该元函数首先调用clear元函数获取一个空的序列，接着将目标元素push_back到新的空序列中，

using init = typename push_back<typename clear<T>::type, U>::type;

并且使用begin、end和deref遍历了原始序列并且按照顺序逐个插入新序列。

using type = typename apply_impl<init, typename begin<T>::type,
                                     typename end<T>::type>::type;

pop_back和pop_front元函数

template <class Tag>
struct pop_back_impl {
  template <class R, class I, class N, class E>
  struct apply_impl {
    using inner = typename push_back<R, typename deref<I>::type>::type;
    using type = typename apply_impl<inner, typename next<I>::type,
                                     typename next<N>::type, E>::type;
  };

  template <class R, class I, class E>
  struct apply_impl<R, I, E, E> {
    using type = R;
  };

  template <class T>
  struct apply {
    using init = typename clear<T>::type;
    using type =
        typename apply_impl<init, typename begin<T>::type,
                            typename next<typename begin<T>::type>::type,
                            typename end<T>::type>::type;
  };
};

template <class T>
struct pop_back
    : pop_back_impl<typename sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct pop_front_impl {
  template <class R, class I, class E>
  struct apply_impl {
    using inner = typename push_back<R, typename deref<I>::type>::type;
    using type = typename apply_impl<inner, typename next<I>::type, E>::type;
  };

  template <class R, class E>
  struct apply_impl<R, E, E> {
    using type = R;
  };

  template <class T>
  struct apply {
    using init = typename clear<T>::type;
    using type =
        typename apply_impl<init, typename next<typename begin<T>::type>::type,
                            typename end<T>::type>::type;
  };
};

template <class T>
struct pop_front
    : pop_front_impl<typename sequence_tag<T>::type>::template apply<T> {};

事实上，pop_back和pop_front元函数与push_front元函数的实现思路基本上是一样的。它们都使用clear元函数创建了一个空序列，然后再往空序列中填充各自的元素。唯一的区别就在于，pop_back元函数会检查下一个迭代器是否为结束迭代器。如果确定是结束迭代器，那么元函数就会忽略当前迭代器，直接返回当前新序列。

using type = typename apply_impl<inner, typename next<I>::type,
                                     typename next<N>::type, E>::type;

而pop_front则是从一开始遍历原始序列迭代器的时候就用next元函数忽略首个迭代器。

using type =
        typename apply_impl<init, typename next<typename begin<T>::type>::type,
                            typename end<T>::type>::type;

insert元函数

上面已经介绍了三个组合而成的元函数，它们的实现虽说比较简单，但是却阐明了这类元函数的基本思路，即创建新的序列，然后遍历原始序列将需要的元素逐个插入到新序列中。现在让我们看一个较为复杂的insert元函数。

template <class Tag>
struct insert_impl {
  template <class R, class U, class B, class I, class E>
  struct apply_impl {
    using inner = typename push_back<R, typename deref<I>::type>::type;
    using type =
        typename apply_impl<inner, U, B, typename next<I>::type, E>::type;
  };

  template <class R, class U, class I, class E>
  struct apply_impl<R, U, I, I, E> {
    using inner = typename push_back<R, U>::type;
    using inner2 = typename push_back<inner, typename deref<I>::type>::type;
    using type =
        typename apply_impl<inner2, I, U, typename next<I>::type, E>::type;
  };

  template <class R, class U, class B, class E>
  struct apply_impl<R, U, B, E, E> {
    using type = R;
  };

  template <class R, class U, class E>
  struct apply_impl<R, U, E, E, E> {
    using type = typename push_back<R, U>::type;
  };

  template <class T, class B, class U>
  struct apply {
    using init = typename clear<T>::type;
    using type = typename apply_impl<init, U, B, typename begin<T>::type,
                                     typename end<T>::type>::type;
  };
};

template <class T, class U, class B>
struct insert
    : insert_impl<typename sequence_tag<T>::type>::template apply<T, B, U> {};

上面的代码总体思路没有变化，先通过clear创建了新序列，难点是如何遍历原始序列并且找到目标位置插入新元素。这里让我们把注意力放在4个版本的apply_impl上，首先来看通常版本的元函数：

template <class R, class U, class B, class I, class E>
  struct apply_impl {
    using inner = typename push_back<R, typename deref<I>::type>::type;
    using type =
        typename apply_impl<inner, U, B, typename next<I>::type, E>::type;
  };

该元函数非常简单，通过push_back将原序列的元素插入到新序列中，其中I是迭代器。

template <class R, class U, class I, class E>
  struct apply_impl<R, U, I, I, E> {
    using inner = typename push_back<R, U>::type;
    using inner2 = typename push_back<inner, typename deref<I>::type>::type;
    using type =
        typename apply_impl<inner2, I, U, typename next<I>::type, E>::type;
  };

第二个的apply_impl是一个特化版本，它限定了当当前迭代器I与目标迭代器相同的时候，将新元素U插入到新序列中，然后再插入迭代器I的元素，这样就能完成插入目标元素U到指定迭代器之前的任务。

template <class R, class U, class B, class E>
  struct apply_impl<R, U, B, E, E> {
    using type = R;
  };

template <class R, class U, class E>
  struct apply_impl<R, U, E, E, E> {
    using type = typename push_back<R, U>::type;
  };

最后两个特化版本的apply_impl限定了元函数的结束条件。一方面apply_impl<R, U, B, E, E>，当原序列遍历到结束迭代器时，如果插入目标位置不是结束迭代器，则插入操作直接结束，返回新序列。另一方面apply_impl<R, U, E, E, E>，当原序列遍历到结束迭代器时，如果插入目标位置正好是结束迭代器，那么就将目标元素U插入到新序列的末尾。

以下是一个调用insert元函数的示例：

using insert_list = list<int, bool, char>;
using result_list = insert<insert_list, short, begin<insert_list>::type>::type;

示例代码中，insert元函数将short类型插入了insert_list序列的begin迭代器之前，于是result_list的结果应该是list<short, int, bool, char>。

其他组合元函数

除了我们上面介绍的push_front、pop_back、pop_front和insert元函数以外，我们还能根据自己的需要实现其他的元函数。比如，用于删除元素的erase元函数，用于排重的unique元函数，用于逆向排序的reverse元函数以及用于查找元素的find元函数等等。它们虽然有各自不同的功能，但是实现思路上确实万变不离其宗的。有兴趣的读者不妨自己尝试动手实现一两个。

序列和迭代器(2)

admin
CPP

list序列

list序列实际上就是曾经介绍的seq序列的加强版，它的定义如下：

struct list_tag {};

template <class... Args>
struct list {
  using iterator_category_tag = forward_iterator_tag;
  using tag = list_tag;
};

可以看到，list序列是一个有可变模板形参的类模板，它有两个内嵌类型分别是iterator_category_tag和tag。其中tag指示该序列的类型是list_tag，iterator_category_tag指示list序列的迭代器类型是正向迭代器forward_iterator_tag。除了正向迭代器的tag，YAMPL还定义了双向和随机访问迭代器。

迭代器名称 定义
正向迭代器 forward_iterator_tag
双向迭代器 bidirectional_iterator_tag
随机访问迭代器 random_access_iterator_tag

正如上一节所说，要完成一个正向迭代器的序列需要实现至少7组基础元函数。接下来我们会逐一的实现这些元函数。

begin_impl元函数

template <>
struct begin_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class... Args>
  struct apply<T<Args...>> {
    using type = iterator<T<Args...>, integral_const<int, 0>, T<Args...>>;
  };
};

根据上面的代码，让我们来详细的观察begin_impl的实现。首先可以看到template <> struct begin_impl<list_tag>是一个template <class Tag> struct begin_impl {};针对list_tag的特化版本。它的作用就是让告知编译器在处理tag为list_tag的序列时，选用template <> struct begin_impl<list_tag>这个元函数。回过头来看begin元函数的实现，

template <class T>
struct begin : begin_impl<typename sequence_tag<T>::type>::template apply<T> {};

begin_impl元函数调用了sequence_tag来获取序列的tag，从而让编译器能够正确选择begin_impl的版本。sequence_tag的实现很简单，就是获取类型的tag并返回。

template <class T>
struct sequence_tag {
  using type = typename T::tag;
};

接着观察begin_impl<typename sequence_tag<T>::type>::template apply<T>的apply<T>，我们发现在编译器选择了正确的begin_impl后，真正发挥作用的是内嵌元函数template <class T> struct apply，它的任务是处理begin传入的模板参数T，并且返回第1个迭代器。

template <template <class...> class T, class... Args>
struct apply<T<Args...>> {
  using type = iterator<T<Args...>, integral_const<int, 0>, T<Args...>>;
};

apply的实现并不复杂，需要注意的是返回迭代器中模板实参的含义。第一个实参T<Args...>是记录当前迭代器所代表的元素以及该元素之后所有元素的序列，比方说现在有一个迭代器的第一个实参为list<int, char, double>，那么它的下一个迭代器的第一个实参应该是list<char, double>。第二个实参integral_const<int, 0>是用来记录当前迭代器在序列中的位置，因为begin返回的是序列的第一个迭代器，所有其位置应该是0。最后的实参T<Args...>对整个序列的记录，由于是首个迭代器所以这个实参看起来和第一个实参相同。另外需要注意的是在正向迭代器中，第三个实参并没有什么作用，之所以给出了这个定义是因为YAMPL还为list实现了一个双向迭代器的版本。

end_impl元函数

template <>
struct end_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class... Args>
  struct apply<T<Args...>> {
    using type =
        iterator<T<>, integral_const<int, sizeof...(Args)>, T<Args...>>;
  };
};

end_impl的实现和begin_impl基本相同，唯一的区别是内嵌元函数apply返回的迭代器的定义不同，它将返回序列最后一个元素之后的迭代器。该迭代器的第一个实参为T<>，这说明该迭代器已经没有代表的元素了。第二个实参integral_const<int, sizeof...(Args)>同样表示当前迭代器在序列的位置。最后的实参T<Args...>还是对整个序列的记录。

size_impl元函数

template <>
struct size_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class... Args>
  struct apply<T<Args...>> {
    using type = integral_const<int, sizeof...(Args)>;
  };
};

size_impl的内嵌元函数apply返回的是序列中元素的数量integral_const<int, sizeof...(Args)>。

clear_impl元函数

template <>
struct clear_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class... Args>
  struct apply<T<Args...>> {
    using type = T<>;
  };
};

clear_impl的内嵌元函数apply返回的是空序列T<>。

push_back_impl元函数

template <>
struct push_back_impl<list_tag> {
  template <class T, class U>
  struct apply;

  template <template <class...> class T, class U, class... Args>
  struct apply<T<Args...>, U> {
    using type = T<Args..., U>;
  };
};

push_back_impl的内嵌元函数apply和之前我们看到的apply元函数有一些区别，它需要两个模板参数，这也正是push_back元函数所需的模板参数。

template <class T, class U>
struct push_back
    : push_back_impl<typename sequence_tag<T>::type>::template apply<T, U> {};

其中实参T是序列本身，实参U是需要插入序列的元素。最终apply返回的是插入新元素之后的序列T<Args..., U>。

next_impl元函数

template <>
struct next_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class U, class N, class B,
            class... Args>
  struct apply<iterator<T<U, Args...>, N, B>> {
    using type = iterator<T<Args...>, typename N::next, B>;
  };

  template <template <class...> class T, class U, class N, class B>
  struct apply<iterator<T<U>, N, B>> {
    using type = iterator<T<>, typename N::next, B>;
  };
};

next_impl的内嵌元函数apply是一个针对迭代器的元函数，之前我们看到的无论是begin_impl还是push_back_impl的apply元函数都是针对序列本身的。这一点从next的定义中也能看出点端倪。

template <class T>
struct next
    : next_impl<typename iterator_sequence_tag<T>::type>::template apply<T> {};

我们发现，next_impl并没有调用sequence_tag获取序列tag，而是采用iterator_sequence_tag元函数获取迭代器所属序列的tag，所以这里next元函数操作的主体对象是迭代器而不是序列。

回头来看next_impl中apply的代码，可以看到apply有两个特化版本，首先当模板实参为iterator<T<U, Args...>, N, B>时，说明该迭代器不是倒数第二个迭代器，那么apply的返回结果应该是下个迭代器iterator<T<Args...>, typename N::next, B>。请注意，因为我们知道模板形参N是一个integral_const类型，所以可以直接使用N::next获取它的下一个整型包装类。

接下来当模板实参为iterator<T<U>, N, B>时，说明它是序列中倒数第二个迭代器。这时apply应该与end元函数返回一个相同的迭代器iterator<T<>, typename N::next, B>。

deref_impl元函数

template <>
struct deref_impl<list_tag> {
  template <class T>
  struct apply;

  template <template <class...> class T, class N, class U, class B,
            class... Args>
  struct apply<iterator<T<U, Args...>, N, B>> {
    using type = U;
  };

  template <template <class...> class T, class N, class B>
  struct apply<iterator<T<>, N, B>> {
    using type = none;
  };
};

deref_impl和next_impl一样也是针对迭代器的元函数，它对迭代器进行解引用操作，随后可以获得元素本身。观察deref_impl的内嵌apply元函数，它也有两个特化版本。当其实参的迭代器为iterator<T<U, Args...>, N, B>时，说明它不是最后一个迭代器，于是返回当前元素U。当实参的迭代器为iterator<T<>, N, B>时，说明这是最后一个迭代器，它不包含任何元素，所以返回none。这里的none是YAMPL专门为类似这种情况定义的类型，用来表示没有意义的结果，具体定义如下：

struct none_tag {};
struct none {
  using tag = none_tag;
};

list序列和迭代器的基本用法

熟悉STL的读者一定对迭代器的使用了如指掌，因为STL中关于容器的大部分函数都依赖迭代器。比如从std::list的容器中删除一个元素就需要使用迭代器指明元素的位置。

std::list<int> mylist{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
mylist.erase(mylist.begin());

模板元编程中序列和迭代器的使用方法和STL的迭代器比较类似，只是代码的写法上有些不同，总的来说还算比较容易掌握。以下是一段调用并验证yampl::list基本元函数的代码：

std::cout << std::boolalpha;
using my_list = list<int_<0>, int_<1>, int_<2>, int_<3>, int_<4>>;
std::cout << "my_list size = " << size<my_list>::type::value << std::endl;

using it0 = typename begin<my_list>::type;
using elem0 = typename deref<it0>::type;
std::cout << "elem0 == int_<0> : "
          << std::is_same_v<elem0, int_<0>> << std::endl;

using it1 = typename next<it0>::type;
using elem1 = typename deref<it1>::type;
std::cout << "elem1 == int_<1> : "
          << std::is_same_v<elem1, int_<1>> << std::endl;

using it2 = typename next<it1>::type;
using it3 = typename next<it2>::type;
using it4 = typename next<it3>::type;
using elem4 = typename deref<it4>::type;
std::cout << "elem4 == int_<4> : "
          << std::is_same_v<elem4, int_<4>> << std::endl;

std::cout << "next<it4>::type == end<my_list>::type : "
          << std::is_same_v<typename next<it4>::type,
                            typename end<my_list>::type> << std::endl;

using empty_list = typename clear<my_list>::type;
using my_list2 = typename push_back<empty_list, int_<5>>::type;
std::cout << "my_list2 == list<int_<5> : "
          << std::is_same_v<my_list2, list<int_<5>>> << std::endl;

在上面的代码中，首先定义了一个list序列my_list，序列共有5个元素，它们从int_<0>递增至int<4>。使用size元函数可以获取my_list中元素个数，这里返回的是int_<5>，通过::value可以获取整型数字5，所以第一句std::cout输出结果为：

my_list size = 5

接着，代码调用begin元函数返回了序列my_list的第一个迭代器it0，可以预见到这个迭代器解引用后的元素就是int_<0>。为了证明这一点，使用元函数deref可以对it0解引用并获得结果elem0，再使用std::is_same_v<elem0, int_<0>>验证类型是否相同，输出结果为：

elem0 == int_<0> : true

为了获取下一个迭代器，可以使用元函数next，这样可以获取迭代器it1。通过同样的方式我们可以获取it2到it4，并且对它们的类型进行判断：

elem1 == int_<1> : true
elem4 == int_<4> : true

it4的下一个迭代器是my_list中最后一个迭代器，应该与end元函数返回的结果相同。我们同样可以通过std::is_same_v<typename next<it4>::type, typename end<my_list>::type>来验证这个结论：

next<it4>::type == end<mylist>::type : true

最后，代码中使用clear元函数返回一个空list序列，并且调用push_back将int_<5>插入到序列之中并获得序列my_list2。用同样的方法再次验证push_back和clear元函数的正确性，得到输出结果：

my_list2 == list<int_<5> : true

序列和迭代器(1)

admin
CPP

在前面的篇幅中我们已经看到了序列在模板元编程中的一部分作用。在本篇中我们将更加深入的探讨序列以及与之相关的算法，同时我们会使用建立迭代器的方法将这些算法抽象出来以方便它们运用到不同类型的序列中。在YAMPL中实现了两种类型的序列list和vector，本章中我将着重介绍list序列，这是因为该序列更好的使用了C++11的特性。另外本篇中介绍的算法基本上都是使用迭代器实现，所以它们可以顺利的移植到vector上。读者也可以将这些算法移植到自己实现的序列上，而这个移植过程也只需要实现少量代码。

定义迭代器

为了保证序列相关算法的通用性，我们需要将算法的实现建立在迭代器的基础之上，于是设计一个通用的迭代器就变得十分重要了。以下代码是YAMPL中通用迭代器类模板的定义：

struct iterator_tag {};

template <class T, class N, class B = void, class B2 = void, class B3 = void>
struct iterator {
  using type = T;
  using index = N;
  using backup = B;
  using backup2 = B2;
  using backup3 = B3;
  using tag = iterator_tag;
};

在上面的代码中，迭代器iterator定义了5个模板形参。其中第一个形参T通常用于记录当前迭代器代表的元素本身或者是记录与该元素相关的序列；第二个形参N通常用于记录当前迭代器在序列中的位置；而剩下的3个形参可以用来记录一些额外的序列信息。

值得注意的是，以上描述是这5个形参在YAMPL序列中的惯用用法，它们并不是绝对的，所以序列的设计者可以根据序列本身的实际情况安排这5个形参的用途。比如YAMPL中的list使用了前3个形参，而vector只使用了前2个形参。

最后来说明一下内嵌类型tag的用途。在YAMPL中，和序列相关的类模板都有一个tag，比如迭代器的tag就是iterator_tag。这些tag的主要功能是对序列相关的类模板进行分类以方便通用算法在不同的序列上正常工作。例如YAMPL的list序列的tag为list_tag，那么为list_tag设计的基础元函数就能使用在list序列之上。同样的道理，若序列的设计者为了某特殊情况定义了一个special_list序列，并且将其tag定义为list_tag，那么为list_tag设计的算法就可以用于该序列了。

序列和迭代器的基础元函数

为了让迭代器能顺利的移植到不同的序列上，我们需要定义几个抽象的元函数。这些元函数有些类似C++纯虚函数的概念，它们只提供一个元函数的轮廓，而具体是定义还是要由序列的设计者来实现。这些基础元函数包括：

template <class Tag>
struct begin_impl {};

template <class T>
struct begin : begin_impl<typename sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct end_impl {};

template <class T>
struct end : end_impl<typename sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct next_impl {};

template <class T>
struct next
    : next_impl<typename iterator_sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct deref_impl {};

template <class T>
struct deref
    : deref_impl<typename iterator_sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct size_impl {};

template <class T>
struct size : size_impl<typename sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct clear_impl {};

template <class T>
struct clear : clear_impl<typename sequence_tag<T>::type>::template apply<T> {};

template <class Tag>
struct push_back_impl {};

template <class T, class U>
struct push_back
    : push_back_impl<typename sequence_tag<T>::type>::template apply<T, U> {};

上面的代码展示了7组基础元函数，它们分别是begin、end、next、 deref、size、clear和push_back。之所以把它们列为基础元函数，是因为要让一个序列和与之相关的迭代器能正常工作这7组元函数是必不可少的。如果一个序列能实现这7组元函数，那么它的迭代器至少能完成一个正向迭代器的全部工作。

这7组元函数的功能具体为：

元函数 说明
begin 返回序列中代表第一个元素的迭代器；
end 返回序列中代表最后一个元素之后的迭代器；
next 返回当前迭代器代表元素的下一个元素的迭代器；
deref 解引用，返回当前迭代器代表的元素本身；
size 返回序列中元素个数；
clear 删除序列中的所有元素；
push_back 在序列的最后新增一个元素。

如果序列的设计者并不满足于正向迭代器的功能，那么还可以实现一个prior元函数的_impl版本来完成一个双向迭代器，prior元函数的定义如下：

template <class Tag>
struct prior_impl {};

template <class T>
struct prior
    : prior_impl<typename iterator_sequence_tag<T>::type>::template apply<T> {};

prior函数的功能具体为：

元函数 说明
prior 返回当前迭代器代表元素的上一个元素的迭代器。

进一步的，如果序列的设计者希望该序列能支持一个随机访问迭代器，那么还需要实现以下2组基础元函数：

template <class Tag>
struct advance_impl {};

template <class T, class N>
struct advance
    : advance_impl<typename iterator_sequence_tag<T>::type>::template apply<T,
                                                                            N> {
};

template <class Tag>
struct distance_impl {};

template <class T, class U>
struct distance
    : distance_impl<typename iterator_sequence_tag<T>::type>::template apply<
          T, U> {};

这2组元函数的功能具体为：

元函数 说明
advance 返回当前迭代器代表元素的第N个递进元素的迭代器
distance 计算同序列中两个迭代器的间隔元素

需要注意的是，序列需要实现的并不是begin、end、next这些元函数本身，而是它们间接调用的_impl版本的内嵌apply元函数。具体来说，想实现序列的push_back功能，那么应该对应的实现push_back_impl和push_back_impl::apply的元函数，具体的实现方法会在后面list序列的小节中介绍。

YAMPL的基础组件(3)

admin
CPP

逻辑运算符元函数

在C++中逻辑运算符可以将两个或多个关系表达式连接成一个，例如&&和||，也能够使表达式的逻辑反转，例如!。在这个小节中，我们将根据C++的逻辑运算符实现一套YAMPL可以使用的逻辑运算符元函数，除此之外我们还将结合上面的内容来完成一个元编程例子。

template <class N1, class N2, class... Nargs>
struct and_ {
  using inner = and_<N2, Nargs...>;
  using value_type = bool;
  using type = integral_const<value_type, N1::value && inner::value>;
  static constexpr value_type value = type::value;
};
template <class N1, class N2>
struct and_<N1, N2> {
  using value_type = bool;
  using type = integral_const<value_type, (N1::value && N2::value)>;
  static constexpr value_type value = type::value;
};

观察上面的代码会发现，and_元函数的实现和plus元函数几乎相同，除了使用了不同的运算符以外，唯一的区别就是返回类型。and_元函数的返回类型using type = integral_const<value_type, N1::value && inner::value>;固定为integral_const<bool, true>或者integral_const<bool, false>之一，也就是true_type或者false_type。这个设计正好是对应&&运算符的返回值必须是true或者false之一。说明了这个区别之后，读者可以回味一下plus的实现应该就能理解and_元函数的实现细节了，这里也不再赘述。

如and_元函数一样，or_也可以通过这样的方式实现，而且只需要修改一个运算符而已。所以这里还是用宏简化代码的实现：

#define BINARY_MULTI_OP_BOOL(name, op)                                  \
  template <class N1, class N2, class... Nargs>                         \
  struct name {                                                         \
    using inner = name<N2, Nargs...>;                                   \
    using value_type = bool;                                            \
    using type = integral_const<value_type, N1::value op inner::value>; \
    static constexpr value_type value = type::value;                    \
  };                                                                    \
  template <class N1, class N2>                                         \
  struct name<N1, N2> {                                                 \
    using value_type = bool;                                            \
    using type = integral_const<value_type, (N1::value op N2::value)>;  \
    static constexpr value_type value = type::value;                    \
  }

BINARY_MULTI_OP_BOOL(and_, &&);
BINARY_MULTI_OP_BOOL(or_, ||);

以上代码实现了逻辑与和逻辑或的运算符元函数，接下来我们需要实现一个逻辑非运算符元函数，也就是在C++中常用的!。逻辑非运算符元函数的实现相对于前两个就单纯多了，代码如下：

template <class T>
struct not_ {
  using value_type = bool;
  using type = integral_const<value_type, !T::value>;
  static constexpr value_type value = type::value;
};

这里只需要注意not_元函数的返回类型也是固定为integral_const<bool, true>或者integral_const<bool, false>之一，剩下的代码和取负运算符元函数的代码几乎相同很容易理解。

现在，我们要利用上面介绍的内容实现一个特殊的函数模板：

template<class T>
void special_func(T) {}

该函数模板需要完成这样一个任务：当模板实参T是一个标量或者引用时，函数参数的T为实参本身；否则T为实参的引用。也就是说当T为int时，函数为void special_func(int) {}；当T为int&时，函数为void special_func(int&) {}；当T为std::string时，函数为void special_func(std::string&) {}。

以下是我的一种实现方案：

template <class T>
struct func_helper {
  using cond = or_<typename std::is_scalar<T>::type,
                   typename std::is_reference<T>::type>;
  using type = typename if_<typename cond::type, T,
                            typename std::add_lvalue_reference<T>::type>::type;
};

template <class T>
void special_func(typename func_helper<T>::type) {}

上面的代码中实现了一个func_helper元函数，该元函数会针对special_func的模板实参进行处理以满足函数需求。在func_helper的实现代码中，首先调用了逻辑或元函数or_，用于判断T是否为标量或者引用类型。然后根据返回结果调用if_元函数。当cond::type的结果为true_type时返回T本身，否则调用std::add_lvalue_reference返回T的引用类型，最终type为要求的返回类型。

来测试一下刚刚编写的函数模板：

int n = 1;
special_func<int>(n);
special_func<int&>(n);
std::string s{ "hello" };
special_func<std::string>(s);

使用-fdump-tree-gimple命令让GCC生成gimple的中间代码，观察代码发现这样三份中间代码：

special_func<int> (type v)
{
  GIMPLE_NOP
}
special_func<int&> (int & v)
{
  GIMPLE_NOP
}
special_func<std::__cxx11::basic_string<char> > (struct basic_string & v)
{
  GIMPLE_NOP
}

可以看到当模板实参为int和int&时，函数形参类型为模板实参本身，而当模板实参为std::__cxx11::basic_string<char>时，函数形参类型为struct basic_string &，满足函数的设计要求。

类型打印元函数

模板元程序之所以比普通C++程序更难编写主要是因为它很难调试。我们常用的调试方法在模板元程序上都没法正常使用，比如调试器只能调试动态运行的程序，但是却无法调试编译期执行的元程序。

另外打印日志的方法也许能帮上一点忙，因为C++为我们提供了typeid这个操作符，它返回的std::type_info结构中存在一个const char* name()的成员函数可以返回类型名称。于是我们想到可以使用以下方法打印类型信息帮助调试：

std::cout << typeid(T).name();

不过遗憾的是，这种方法也并不完美。首先来说，成员函数name()返回的类型名称在不同编译器中有不同的展现方法，比如MSVC编译出来的程序返回的是一个可读的名称，而GCC编译出来的程序返回的类型名称则需要使用特定API（例如abi::__cxa_demangle）将其转换为可读的名称。其次，typeid也无法真实的反应类型的状态，因为C++标准中说明了typeid会忽略类型的cv属性，也就是说typeid(const T) == typeid(T)。所以typeid打印日志的方法也不满足需求。

为了准确是输出类型信息，我们需要将目光从程序本身移动到编译期上，因为只有编译期才是掌握类型信息最全面的程序。于是我们可以想到使用编译期的错误信息来打印类型信息。由于错误信息往往是帮助程序员排查错误，所以类型信息会非常的全面。

template <class T>
struct err_print_type;

err_print_type<typename minus<int_<10>, int_<2>>::type>();

在上面的代码中err_print_type是一个缺少实现的类模板，所以当编译器将其进行实例化的时候必然会报错，而错误信息正是我们想要的结果。err_print_type<typename minus<int_<10>, int_<2>>::type>();在MSVC中会显示错误信息：

error C2027: use of undefined type 'err_print_type<yampl::integral_const<T,8>>'
with
[
    T=int
]

在GCC中显示错误信息：

error: invalid use of incomplete type 'struct err_print_type<yampl::integral_const<int, 8> >'

可以看到，无论是哪种编译器都非常详细的显示了类型信息。

现在类型信息是完整了，但这种方法还是不太好，因为错误会阻止程序的编译导致无法生成可执行程序。我们需要一种方法既能在编译期产生可用的日志，与此同时也不能阻碍程序的正常编译。于是我们想到，如果能将错误信息转换为警告信息不久好了么！在YAMPL中，打印类型信息的方法就是用这种思路实现的。

#if defined(__clang__)
template <class T>
struct dbg_print_type {
  const int tmp = 1 / (sizeof(T) - sizeof(T));
};
#elif defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic warning "-Wsign-compare"
template <class T>
struct dbg_print_type {
  enum { n = sizeof(T) > -1 };
};
#pragma GCC diagnostic pop
#elif defined(_MSC_VER)
#pragma warning(push, 3)
template <class T>
struct dbg_print_type {
  char tmp[0];
};
#pragma warning(pop)
#else
template <class T>
struct dbg_print_type {};
#endif

以上代码实现了一个类模板dbg_print_type，并且分别对MSVC、GCC和CLang做了支持。当编译期时MSVC时，使用了数组大小为0的技巧促使编译期发出警告；当编译器是CLang时，使用除数为0的方式让编译器发出警告；当编译器是GCC时，使用不同符号类型比较让编译器发出警告，值得注意的是这个警告需要手动开启。

将上面示例中的err_print_type修改为dbg_print_type：

dbg_print_type<typename minus<int_<10>, int_<2>>::type>();

GCC会发出这样的警告：

In instantiation of 'struct yampl::DbgPrintType<yampl::integral_const<int, 8> >':
required from here
warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   15 |   enum { n = sizeof(T) > -1 };

MSVC显示的警告为：

warning C4200: nonstandard extension used: zero-sized array in struct/union
message : This member will be ignored by a defaulted constructor or copy/move assignment operator
message : see reference to class template instantiation 'yampl::DbgPrintType<yampl::integral_const<T,8>>' being compiled
with
[
    T=int
]

请注意警告的信息确实比较多，但是仔细观察还是能看到'struct yampl::DbgPrintType<yampl::integral_const<int, 8> >'这样类似的信息。另外值得高兴的是，这些警告信息也确实没有阻止程序的编译。

YAMPL的基础组件(2)

admin
CPP

整型转换等级

考虑一个简单的问题，在C++中将两个不同类型的整型操作数相加的结果会是怎么样的？比如用short类型的变量和long类型的变量相加。答案很简单，相加的结果应该是一个long类型，因为short类型隐式转换为long，于是就需要我们使用一个long类型的变量来存储计算结果。在C++11以后，我们可以通过类型说明符auto把这件事情交给编译器来完成。但是在模板元编程中，这件事是需要我们亲力亲为的。因此需要一个有效的工具来选择合适的类型，那就是类型转换等级。所谓转换等级实际上是类型根据C++隐式类型转换规则的一种排序，简单来说整型转换等级的排序符合下面两条规则：

  1. 若两操作数的类型所需的存储空间大小不同，则存储空间较小的操作数类型隐式转换到存储空间较大的操作数类型。
  2. 若两操作数的类型所需的存储空间大小相同但符号性不同，则有符号类型操作数会隐式转换成无符号类型。

下面是YAMPL对整型转换等级的排序：

template <typename T>
struct integral_rank;

template <> struct integral_rank<bool> : int_<1> {};
template <> struct integral_rank<signed char> : int_<2> {};
template <> struct integral_rank<char> : int_<3> {};
template <> struct integral_rank<unsigned char> : int_<4> {};
template <> struct integral_rank<wchar_t> : int_<5> {};
template <> struct integral_rank<char16_t> : int_<6> {};
template <> struct integral_rank<short> : int_<7> {};
template <> struct integral_rank<unsigned short> : int_<8> {};
template <> struct integral_rank<char32_t> : int_<9> {};
template <> struct integral_rank<int> : int_<10> {};
template <> struct integral_rank<unsigned int> : int_<11> {};
template <> struct integral_rank<long> : int_<12> {};
template <> struct integral_rank<unsigned long> : int_<13> {};
template <> struct integral_rank<long long> : int_<14> {};
template <> struct integral_rank<unsigned long long> : int_<15> {};

integral_rank是一个用于描述整型转换等级的类模板，它的实现非常简单，只是继承了类模板int_的实例，如此一来我们可以通过::value的方法访问类型等级的值，这个技巧在C++模板元编程中被称为元函数转发。

整体的来看这段代码，可以看出等级的排序顺序由小到大，在规则上转换也总是从小到大进行的。比如，char类型的等级为3，int类型的等级为10，于是这两个类型的操作数互相作用后的结果是一个等级数值更大的int类型。为了方便的选择转换等级，YAMPL还提供了一个元函数来完成这件事，该函数依赖元函数if_c：

template <class T1, class T2>
using largest_int =
    if_c<integral_rank<T1>::value >= integral_rank<T2>::value, T1, T2>;

或者

template <class T1, class T2>
struct largest_int
    : if_c<integral_rank<T1>::value >= integral_rank<T2>::value, T1,
                       T2> {};

这里无论是使用别名模板还是元函数转发都会调用元函数if_c比较对应类型的转换等级，最终给出拥有较大等级的类型。它们的结果是相同的，读者可以根据自己的喜好来选择largest_int的实现方案。

在下面这段代码中largest_int和auto具有相同的效果，val1和val2都会被编译器推导为int类型。

int a1 = 5;
char a2 = 7;
largest_int<int, char>::type val1 = a1 + a2;
auto val2 = a1 + a2;

算术运算符元函数

我们知道在YAMPL中，整型常量都被包装类模板包装成了特殊的类型。这种处理方式为类型序列和元函数提供了操作数值途径，但随之而来的后果是无法对包装类进行加减乘除等算术运算，同样的也无法对包装类进行逻辑运算。为了解决这类计算问题，我们需要为YAMPL提供一套打通数值计算和类型计算的元函数，让它们来完成算术和逻辑的运算工作。

事实上，上一篇中的plus元函数就可以被列出其中，不过我并不打算直接这么做，因为它还有进一步完善的空间，请看下面的代码：

template <class N1, class N2, class... Nargs>
struct plus {
  using inner = plus<N2, Nargs...>;
  using value_type = typename largest_int<typename N1::value_type,
                                          typename inner::value_type>::type;
  using type = integral_const<value_type, N1::value + inner::value>;
  static constexpr value_type value = type::value;
};

template <class N1, class N2>
struct plus<N1, N2> {
  using value_type = typename largest_int<typename N1::value_type,
                                          typename N2::value_type>::type;
  using type = integral_const<value_type, (N1::value + N2::value)>;
  static constexpr value_type value = type::value;
};

观察以上的代码可以发现它和以前的版本有两个显著的升级。首先，现在的元函数plus支持两个或两个以上的操作数参与到加法运算中，比如plus<int_<3>, int_<2>, int_<5>, int_<6>>。显然，为了完成这个目标我们需要实现一个递归，在代码中这个递归的发起点就是using inner = plus<N2, Nargs...>;，它使用plus计算除N1外剩余形参的结果。直到参数个数减少为2时触发结束条件，struct plus<N1, N2>计算两个形参之和并返回结果，递归结束。

另外还可以注意到，该版本的plus支持不同整型的包装类，这是因为在元函数中调用了

largest_int<typename N1::value_type, typename N2::value_type>::type;

来获取计算结果的最终类型。因此plus<int_<3>, uint_<2>>::type这段代码可以顺利的编译，它的计算结果是uint_<5>。

当然，除了加法以外还有一些计算也可以支持多个操作数同时进行，例如乘法、位的与计算以及位的或计算等。而这些计算本质上与plus元函数只有运算符上的差别，以乘法为例：

template <class N1, class N2, class... Nargs>
struct times {
  using inner = times<N2, Nargs...>;
  using value_type = typename largest_int<typename N1::value_type,
                                          typename inner::value_type>::type;
  using type = integral_const<value_type, N1::value * inner::value>;
  static constexpr value_type value = type::value;
};
template <class N1, class N2>
struct times<N1, N2> {
  using value_type = typename largest_int<typename N1::value_type,
                                          typename N2::value_type>::type;
  using type = integral_const<value_type, (N1::value * N2::value)>;
  static constexpr value_type value = type::value;
};

对比元函数plus，只是N1::value + N2::value被修改为了N1::value * N2::value。根据这样的规则，我们可以用宏来简化这类代码为：

#define BINARY_MULTI_OP(name, op)                                              \
  template <class N1, class N2, class... Nargs>                                \
  struct name {                                                                \
    using inner = name<N2, Nargs...>;                                          \
    using value_type = typename largest_int<typename N1::value_type,           \
                                            typename inner::value_type>::type; \
    using type = integral_const<value_type, N1::value op inner::value>;        \
    static constexpr value_type value = type::value;                           \
  };                                                                           \
  template <class N1, class N2>                                                \
  struct name<N1, N2> {                                                        \
    using value_type = typename largest_int<typename N1::value_type,           \
                                            typename N2::value_type>::type;    \
    using type = integral_const<value_type, (N1::value op N2::value)>;         \
    static constexpr value_type value = type::value;                           \
  }

BINARY_MULTI_OP(plus, +);
BINARY_MULTI_OP(times, *);
BINARY_MULTI_OP(bitand_, &);
BINARY_MULTI_OP(bitor_, |);
BINARY_MULTI_OP(bitxor_, ^);

可以看到我将+、*、&、|和^归为了一类，并称它们为支持多运算符同时计算的二元运算符元函数。

与支持多操作数的二元运算符不同，减法、除法等运算对于操作数顺序有着严格的要求，所以对于这类运算而言，他们无法支持像加法这种多操作数的运算。也正因如此，减法、除法、移位等这些运算的模板元函数的实现更加的简单了。

template <class N1, class N2>
struct minus {
  using value_type = typename largest_int<typename N1::value_type,
                                          typename N2::value_type>::type;
  using type = integral_const<value_type, (N1::value - N2::value)>;
  static constexpr value_type value = type::value;
};
template <class N1, class N2>
struct divides {
  using value_type = typename largest_int<typename N1::value_type,
                                          typename N2::value_type>::type;
  using type = integral_const<value_type, (N1::value / N2::value)>;
  static constexpr value_type value = type::value;
};

观察以上代码可知，减法和除法元函数的实现基本上就是加法元函数的一个特化的实现。另外它们也只有一个运算符的区别，同样可以通过宏将其简化为：

#define BINARY_SINGLE_OP(name, op)                                          \
  template <class N1, class N2>                                             \
  struct name {                                                             \
    using value_type = typename largest_int<typename N1::value_type,        \
                                            typename N2::value_type>::type; \
    using type = integral_const<value_type, (N1::value op N2::value)>;      \
    static constexpr value_type value = type::value;                        \
  }

BINARY_SINGLE_OP(minus, -);
BINARY_SINGLE_OP(divides, /);
BINARY_SINGLE_OP(modulus, %);
BINARY_SINGLE_OP(left_shift, <<);
BINARY_SINGLE_OP(right_shift, >>);

这里-、/、%、<<和>>被归为一类，也就是普通的二元运算符元函数。

除了以上算数运算符之外，还有一个容易被忽略的运算符——取负运算符。当然，相对于前两种运算符，它的实现就更加简单了：

template <class T>
struct negate {
  using value_type = typename T::value_type;
  using type = integral_const<value_type, -T::value>;
  static constexpr value_type value = type::value;
};

综合上述运算符元函数，我们来做一道计算题-((5+(10-2)*3*5/2) << 2)：

using step1 = minus<int_<10>, int_<2>>;                       // step1 = 10-2
using step2 = times<typename step1::type, int_<3>, int_<5>>;  // step2 = step1*3*5
using step3 = divides<typename step2::type, int_<2>>;         // step3 = step2/2
using step4 = plus<int_<5>, typename step3::type>;            // step4 = 5+step3
using step5 = left_shift<typename step4::type, int_<2>>;      // step5 = step4 << 2
using result_step = negate<typename step5::type>;             // result_step = -step5
auto result_value = result_step::value;

编译以上代码，编译器计算result_step的类型为int_<-260>，所以result_value为-260。

关系运算符元函数

在C++中，想获得两个整数之间的关系是很容易的一件事。比如比较3和7的大小，只需要使用关系运算符<或者>。但使用C++模板元编程事情就变得不那么容易了，我们需要比较的是整型常量包装类之间关系，比如比较int_<3>和int_<7>的大小。所以除了算数运算符元函数，YAMPL还应该提供一套描述整型常量包装类之间关系的元函数，这也是C++模板元编程中必不可少的一环。

好在我们已经有了实现算术运算符元函数的基础，再实现一套关系运算符元函数也并不会觉得很难，下面是==运算符元函数的实现代码：

template <class N1, class N2>
struct equal_to {
  using value_type = bool;
  using type = integral_const<value_type, (N1::value == N2::value)>;
  static constexpr value_type value = type::value;
};

上面的代码十分简洁，甚至是在算术运算符元函数中一直发挥重要作用的largest_int也被省去了。在equal_to元函数中，value_type被直接定义为bool，这很容易理解，因为关系运算符的计算结果本就是布尔类型。因此，元函数返回的结果type就是integral_const<value_type, true>或者integral_const<value_type, false>。是不是看上去非常熟悉？没错，它们正是true_type和false_type的定义。

基于和算术类型的元函数同样的原因，关系运算符的元函数也能用宏来做统一的实现：

#define BINARY_SINGLE_OP_BOOL(name, op)                                \
  template <class N1, class N2>                                        \
  struct name {                                                        \
    using value_type = bool;                                           \
    using type = integral_const<value_type, (N1::value op N2::value)>; \
    static constexpr value_type value = type::value;                   \
  }

BINARY_SINGLE_OP_BOOL(equal_to, ==);
BINARY_SINGLE_OP_BOOL(not_equal_to, !=);
BINARY_SINGLE_OP_BOOL(greater, >);
BINARY_SINGLE_OP_BOOL(greater_equal, >=);
BINARY_SINGLE_OP_BOOL(less, <);
BINARY_SINGLE_OP_BOOL(less_equal, <=);

在上面的代码中==、!=、>、>=、<和<=被归为一类，可以称它们为返回布尔包装类的二元运算符元函数。调用它们将返回true_type或者false_type，例如：

using step1 = typename minus<int_<10>, int_<2>>::type;
using result_type1 = typename equal_to<step1, int_<8>>::type;// true_type
using result_type2 = typename greater<step1, int_<8>>::type; // false_type
using result_type3 = typename less<step1, int_<8>>::type;    // false_type

YAMPL的基础组件(1)

admin
CPP

从本篇开始，我们将开始进入轻量级C++模板元编程库YAMPL(Yet Another MPL)的编写环节。不过，在深入探索元编程的序列和算法之前，有一些基础工作必须完成，比如定义命名空间、定义整型常量包装类模板，编写包装类的算数和逻辑运算元函数、编写用于调试的类型打印元函数等等。在完成了这些基础组件后，序列和算法的编写工作将会变得非常高效和有趣。

定义命名空间

在前面的文章中，我们定义了两个特殊的类型true_type和false_type。不巧的是，在STL中也有两个一模一样的类型名，而且这两个类型在STL的type_traits中被广泛的使用，例如：std::is_same、std::is_class、std::is_const等等，它们的返回类型就是上述两种类型的其中之一。无独有偶，在Boost中也有这样的两个类型。其实，有一点很容易想到，作为Boost.MPL的模仿者，YAMPL中一定会存在大量与Boost.MPL中相同的命名。所以为了解决以上这类问题，必须为YAMPL安排一个命名空间。为了直观，我就直接定义YAMPL的命名空间名为yampl。

那么现在对于true_type这样的类型有三种实现，包括：yampl::true_type、stl::true_type以及boost::true_type。面对这样的情况，我们有时候会需要一个类型的转换元函数，例如：

template <class T, class U, class V>
struct type_convert_to;

template <class T, class V>
struct type_convert_to<T, T, V> {
    using type = V;
};

template <class T>
using stl_to_yampl_true_type = type_convert_to<T, std::true_type, yampl::true_type>;

在上面的代码中，元函数stl_to_yampl_true_type可以将std::true_type转换为yampl::true_type，如果该元函数的实参不是std::true_type则编译出错。如果有需要在库与库之间频繁切换的情况，实现一个这样的转换元函数是很有用的一种方法。

有一点需要指出的是，在后面的文章中会涉及到一些对YAMPL中元函数调用的示例，这些示例一般都默认认为已经使用using namespace yampl;打开过yampl的命名空间，所以没有使用前缀写法yampl::xxx。只有涉及到不同命名空间类型互相转换的情况才会用前缀的方式指明命名空间。

整型常量包装类模板

在YAMPL中的元函数都是关于类型的计算，但有时候数值计算却又是不可避免的。为了让类型计算的元函数能兼容数值计算，我们需要一个特殊的类模板，它能够将数值转换为类型。这里我们称这个特殊的类模板为整型常量包装类模板。其实在上一篇中我们已经见到过它的简化版本，以下是它的完整版：

template <class T, T N>
struct integral_const {
  using value_type = T;
  using type = integral_const;
  static constexpr value_type value = N;
  using next = integral_const<T, N + 1>;
  using prior = integral_const<T, N - 1>;
};

在上面的代码中，integral_const是整型常量包装类模板，其模板形参T是包装常量的类型，形参N是包装的具体数值，例如：integral_const<int, 5>是一个包装了数值为1的int类型常量的类型。integral_const定义了静态数据成员value来返回包装类型代表的具体数值，定义value_type来指示返回数值的准确类型。另外为了元函数调用形式上的统一，integral_const还定义内嵌类型type为自身。最后我们还可以发现，integral_const为了方便完成数值的自增和自减操作，分别定义了next和prior来表示integral_const<T, N + 1>和integral_const<T, N - 1>，于是我们可以完成这样的操作：

std::is_same_v<integral_const<int, 5>::next, integral_const<int, 6>>;

std::is_same_v返回的结果为true。

到目前为止integral_const似乎已经满足要求了，这很好，但还有一点却令人厌烦。考虑一下如果我们需要在序列中声明一连串的integral_const会发生什么？

seq<integral_const<int, 1>, integral_const<int, 2>, integral_const<int, 3>, ...>

显然这种写法过于冗长，这里需要一种更简洁的表达方法，我选择使用别名模板：

template <int N>
using int_ = integral_const<int, N>;

这样一来定义上面的序列会简洁不少：

seq<int_<1>, int_<2>, int_<3>, ...>

另外，读者还可以定义其他别名模板以满足自己的需求，比如定义一个无符号整型常量的包装类模板：

template <unsigned int N>
using uint_ = integral_const<unsigned int, N>;

值得注意的是，布尔类型也可以使用integral_const来表示，因为它能和整型发生隐式转换，但会有一些不同之处，请看下面这个针对bool的特化版本：

template <bool N>
struct integral_const<bool, N> {
  using value_type = bool;
  using type = integral_const;
  static constexpr value_type value = N;
};

template <bool N>
using bool_ = integral_const<bool, N>;

using true_type = bool_<true>;
using false_type = bool_<false>;

观察上面的代码可以发现，特化版本的integral_const删除了next和prior，这是因为布尔类型只有true和false之分，自增和自减对于它是没有意义的。另外还定义了true_type和false_type以方便后续使用，它们在YAMPL中使用的是比较频繁的。

if元函数

if元函数是YAMPL中最常用的元函数之一，又因为它不依赖其他元函数，所以应该优先介绍它。不过实际上，我们在上一篇已经对if元函数做过了比较详细的介绍了，为了本篇知识体系的完整性这里将它拿出来总结一下：

template <bool B, class N1, class N2>
struct if_c {
  using type = N1;
};

template <class N1, class N2>
struct if_c<false, N1, N2> {
  using type = N2;
};

template <class T, class N1, class N2>
struct if_ {
  using type = typename if_c<!!T::value, N1, N2>::type;
};

上面的代码有两个元函数if和if_c，其中if_c是真正实现选择逻辑的元函数，它接受的条件参数是布尔值。而元函数if对if_c进行了一次包装，这使得它接受的条件参数从一个布尔值转换为了类型，而且这种类型还有相当不错的兼容性，它只要求类型具有静态数据成员value即可，所以上一节提到的true_type、false_type、int_<7>甚至其他库的std::true_type、boost::mpl::false_等等都可以兼容if元函数。

元函数和序列(2)

admin
CPP

接着上一篇的话题

序列

一说到序列，我们很容易想到STL中的容器vector。相对于数组，C++程序员显然更喜欢vector，这不仅是因为vector可以动态的扩展容器的空间，更是因为STL为它提供了一系列使用算法，比如插入、查找等等。事实上，关于STL序列的设计思路放在C++模板元编程中也同样适用。要知道，Boost.MPL中的大多数算法都是操作于序列之上的，它能够发挥模板元编程更大潜力，也正因如此序列对于模板元编程才如此的重要。

当然，相对于STL的vector使用于运行期，模板元编程的序列必须是在编译阶段就能够存储数据的，所以我们能够使用的也只有类模板，例如：

template <class... Args>
struct seq {};

seq是一个最简单的序列，但千万别小瞧了它，因为它能够容纳任意多个元素。而实现这一能力的关键是C++11标准中引入的可变模板参数的特性，所以这里seq真正存储数据的是模板参数，比如：

using integer_list = seq<int, short, char>;

在上面的代码中，类模板实参<int, short, char>为序列seq的保存元素。好了，现在我们已经有了一个最基本的序列，接下来还需要准备一些配合序列的算法。继续对比STL的vector，最常用的vector算法应该是成员函数push_back，那么我们也来给seq实现一个编译阶段的seq_push_back元函数。这听起来似乎有些难度，不过事实上在可变模板形参的基础上实现push_back算法是很容易的：

template <class S, class T>
struct seq_push_back;

template <class T, class... Args>
struct seq_push_back<seq<Args...>, T> {
    using type = seq<Args..., T>;
};

在上面的代码中，首先声明了一个元函数seq_push_back，它有两个形参分别为S和T，其中S表示序列，而T代表即将插入的元素。接着代码偏特化了一个seq_push_back，该版本对S为seq的情况定义了元函数的具体实现。请注意这里的实现细节，因为后文中很多算法的实现都基于这个思路。在这个版本中引入了可变形参class... Args，并且将其运用于特化的参数中struct seq_push_back<seq<Args...>, T>，这样就可以利用编译器推导出Args的具体实参。最终通过Args定义新的seq类型以达到push_back算法的目的：using type = seq<Args..., T>;。值得注意的是，元函数seq_push_back并没有提供通用版本的实现，所以当模板实参S不是seq类型的时候编译将无法正确进行。

选择结构

在C++模板元编程中代码的选择结构是由元函数实现的。这一点比较容易理解，毕竟类模板的特化正好适合来做这件事，例如：

template <bool C, class T, class F>
struct if_ {
    using type = T;
};

template <class T, class F>
struct if_<false, T, F> {
    using type = F;
};

上面的代码实现了两个版本的if_元函数，其中通用版本无条件的返回模板形参T，而针对模板形参C为false的偏特化版本返回的则是模板形参F。这样一来元函数就可以根据模板形参C的具体值返回不同的类型，例如：

if_<false, int, double>::type double_value;
if_<true, int, double>::type int_value;

作为模板元编程中编写选择结构的常用技巧，STL也实现了一份类似的代码，不过在STL中元函数的函数名为conditional，除此以外基本上没有差异包括调用方式：

std::conditional<true, int, double>::type

请注意，无论是上面的if_还是std::conditional都存在一个问题，那就是将数值和类型计算混合了。我们希望能有一个只有类型计算的if_版本。想达到这个目的需要用到编写plus元函数时的同一个技巧，即创建一个布尔值和类型之前的桥梁：

template <bool C>
struct bool_ {
    static constexpr bool value = C;
};

using true_type = bool_<true>;
using false_type = bool_<false>;

在上面的代码中，我们将数值和类型进行了转换，数值true和false分别转换为了类型true_type和false_type。于此同步的，if_也需要进行一些修改：

template <bool C, class T, class F>
struct if_c {
    using type = T;
};

template <class T, class F>
struct if_c<false, T, F> {
    using type = F;
};

template <class C, class T, class F>
struct if_ {
    using type = typename if_c<!!C::value, T, F>::type;
};

在上面的代码中存在两个选择元函数if_c和if_，其中if_c的实现和上一个版本的if_一样，通过布尔值C来确定返回的类型。相对的，当前版本的if_元函数的第一个参数C是类型而非是布尔值，进一步来说这个类型C必须是一个带有常量静态数据成员value的类型。元函数if_会通过!!C::value的方法将数值转换成布尔值，最终调用if_c返回目标类型。

由于元函数if_的形参发生了改变，其调用方法也需要做相应的调整：

if_<false_type, int, double>::type double_value;
if_<true_type, int, double>::type int_value;

“if_是改写好了，但是我到目前为止并没有发现这样大动干戈改写的任何好处呀？”相信很多读者会有这样的疑问。这很好，不过现在还不是解释这个问题的最佳时机，请先相信这样的修改一定会带来某种优势吧。

循环结构

与选择结构不同，循环结构没有惯用元函数的具体实现。一般来说，模板元编程中的循环都是根据实际需要来实现的。不过好在它们的实现都有固定的方法和模式，所以总体而言并不算难。让我们先看一个例子：

template <int... Args>
struct sum;

template <int N, int... Args>
struct sum<N, Args...> {
    static constexpr int value = N + sum<Args...>::value;
};

template <int N>
struct sum<N> {
    static constexpr int value = N;
};

在上面的代码中，元函数sum有3个版本，其中通用版本的

template <int... Args>
struct sum;

只有声明却没提供实现，而真正的实现是由它的两个特化版本来完成的。首先struct sum<N, Args...>是一个通过递归完成循环的元函数，它的返回值是第一个形参N与使用剩余形参调用的sum的返回值之和，这样理所当然的形成了一个循环结构。请注意，在普通的C++编程中，我们经常会用到无限循环，但是在模板元编程中无限循环不具有任何意义，毕竟谁也不想自己的程序永远无法通过编译。事实上也真不会发生这样的事情，因为编译器最终会由于递归过多而停止编译并报错。所以在元编程的循环结构中，我们需要为其准备一个有效的结束条件。在本例中，这个结束条件就是struct sum<N>，它定义当sum的形参只剩下一个时递归结束，直接返回形参N，至此整个递归开始折返。

调用元函数sum:

auto val = sum<1, 2, 3, 4>::value;

这句代码在编译器中的计算顺序相当于：

auto val = 1 + (2 + (3 + (4)));

也正是递归操作的顺序。

以上是一个数值计算的求和元函数，按照惯例我们实际期望的是类型计算元函数。接下来我们可以利用之前介绍的plus元函数来实现一个类型计算的求和元函数：

template <class... Args>
struct sum;

template <class N, class... Args>
struct sum<N, Args...> {
    using type = typename plus<N, typename sum<Args...>::type>::type;
};

template <class N>
struct sum<N> {
    using type = N;
};

auto val = sum<int_<1>, int_<2>, int_<3>, int_<4>>::type::value;

可以看到在上面的代码中关于数值计算的痕迹都被抹去，元函数的调用方式也发生了略微的变化。但是不变的是实现循环结构的方法。在代码中using type = typename plus<N, typename sum<Args...>::type>::type;虽然冗长但还算清晰，很明显type的结果依赖元函数plus计算的结果，而plus的计算结果又依赖于sum的第一个形参与剩余形参调用sum的计算结果，这样就形成了递归，除多了一步plus的调用以外其他过程基本上和上一个版本一致。另外，同样一致的还有递归的结束条件，struct sum<N>与上一个版本唯一的区别是返回类型本身而不是返回数值。

根据以上两个例子我们可以总结出模板元编程循环结构的两个关键点：更新形参递归并调用元函数本身以及定义有效的结束条件。让我们带上这两个关键点来看下一个例子，这个例子结合了上文提到的序列和选择结构，实际上循环和选择正是序列相关算法的关键，在真实的模板元编程代码中它们是最好的搭档。

template <class T>
struct result_wrap {
    using type = T;
};

template <class S>
struct seq_is_all_reference;

template <class T, class... Args>
struct seq_is_all_reference<seq<T, Args...>> {
    using cond = typename std::is_reference<T>::type;
    using result = typename if_<cond, seq_is_all_reference<seq<Args...>>, result_wrap<false_type>>::type;
    using type = typename result::type;
};

template <class T>
struct seq_is_all_reference<seq<T>> {
    using cond = typename std::is_reference<T>::type;
    using type = typename if_<cond, true_type, false_type>::type;
};

在上面的代码中，元函数seq_is_all_reference的作用是判断序列seq中的元素是否全都是引用类型，如果都是引用类型就返回true_type，否则返回false_type。在实现上seq_is_all_reference相对复杂一些，因为代码中循环和选择发生了互相嵌套的情况。seq_is_all_reference<seq<T, Args...>>首先判断第一个参数T是否为引用类型，并将结果cond作为实参调用元函数if_。接下来if_判断cond的结果，如果结果为std::true_type则进入递归流程seq_is_all_reference<seq<Args...>，目的是判断后续的参数是否为引用类型。如果cond的结果是std::false_type，那么循环终止并返回false_type。请注意，这里cond是std::is_reference<T>返回的结果，所以结果类型是std::true_type或者std::false_type，而seq_is_all_reference是我们自己的元函数，其返回结果是true_type或者false_type。另外，读者可能也发现了，在seq_is_all_reference的循环结束条件并非只有一个。比较明显的是seq_is_all_reference<seq<T>>，它定义当形参只剩一个的情况下元函数返回cond的结果。除此之外，seq_is_all_reference<seq<Args...>还隐含了一个结束条件，就是当cond为std::false_type时递归中断并返回结果。

using test_seq1 = seq<int&, double, short&>;
using test_seq2 = seq<int&, double&, short&>;

using result_type1 = seq_is_all_reference<test_seq1>::type;    // result_type1为false_type
using result_type2 = seq_is_all_reference<test_seq2>::type; // result_type2为true_type

以上代码演示了对seq_is_all_reference的使用方法。其中序列test_seq1中由于double不是引用类型的关系，所以返回结果是false_type。而序列test_seq2中的所有元素都是引用类型于是返回了true_type。来看一个更加实际的例子：

template <class... Args>
class some_class_need_ref {
    static_assert(seq_is_all_reference<seq<Args...>>::type::value);
};

some_class_need_ref<int&, double&> obj1;    // 编译成功
some_class_need_ref<int&, double> obj2;        // 触发static_assert，编译失败

上面的代码定义了一个特别的类模板，它要求模板参数必须都是引用类型。它在定义中加上了static_assert(seq_is_all_reference<seq<Args...>>::type::value);以检查调用者是否正确实例化了类模板。在编译的过程中，编译器发现obj2的类型some_class_need_ref<int&, double>的模板参数并不是规定中的引用类型，于是static_assert被触发导致编译失败。

到目前为止，我们已经了解了C++模板元编程中元函数和序列的基本概念和使用方法。另外我们还看到了用元函数来控制选择和循环等代码流程的方法，之后我们将选择和循环结合在一起完成了一个判断序列中的所有元素是否为引用类型的元函数示例。可以说我们现在已经有办法独立编写一些模板元程序了。接下来的文章将会更进一步，我们将会接触到更为复杂的元程序，在那里我们会一起实现一个轻量级C++模板元编程库——YAMPL。

元函数和序列(1)

admin
CPP

元函数简单来说就是一种可以在编译期调用的函数，它操作的对象一定是编译期可以确定的，比如类型和常量。元函数也是模板元编程中最基础的组成部分，甚至代码中的选择和循环等控制流都是由元函数来完成。而序列则进一步释放了元函数的威力，我们可以通过元函数为序列提供丰富的算法以解决各种实际问题。

元函数

一个普通的C++函数通常由函数名称、参数、返回类型以及函数主体这4个部分组成，比如：

int plus(int a, int b)
{
    return a + b;
}

作为对比，C++模板元编程的元函数同样也存在函数名称、参数以及函数主体3个部分，只不过它们的形式有一些不同罢了。还是以plus函数为例，将其改写为元函数后的代码如下：

template <int a, int b>
struct plus {
    static constexpr int value = a + b;
};

看到以上代码，有人可能会惊呼道：“这哪是什么函数，它明明就是一个类模板！”。是的没错！它确实是一个类模板，可同时也是一个元函数。让我们先接受这个定义，这样可以让我们很容易的找到它和普通函数版本的对应关系：首先plus作为类模板名也是元函数名，然后类模板形参int a, int b对应是元函数的形参，最后元函数的函数体就是类模板的定义。虽然在元函数中我们没有办法定义返回类型（实际上也没有必要定义，因为大多数时候元函数返回的就是类型本身），但是可以通过约定元函数的函数体中静态变量名称的方法定义数值的返回值，体现在plus中即为static constexpr int value = a + b;，通常情况下，元函数会约定value为数值类型的返回值名称。

另外还有一种特殊的情况，当元函数没有形参时，对应的则是类或者实例化的类模板。比如：

struct kilometer {
    static constexpr int value = 1000;
};

using plus11 = plus<3, 8>;

在C++模板元编程中，对于数值计算元函数的调用实际上就是访问起静态成员，根据约定会获取value的值：

auto x1 = plus<7, 11>::value;
auto x2 = kilometer::value;
auto x3 = plus11::value;

到此为止，我们看到的都是有关数值计算的元函数，但是我又强调过数值计算并非元函数的重点工作。其实这是有意为之，目的是为了方便元函数与普通函数的对比，接下来让我把数值转换为类型以帮助我们讨论类型计算元函数。

这里我并不打算让类型计算元函数的例子显得过于跳跃，所以还是以plus为例将其修改为：

template <int n>
struct int_ {
    static constexpr int value = n;
};

template <class T1, class T2>
struct plus {
    using type = int_<T1::value + T2::value>;
};

在上面的代码中新增了一个类模板int_。int_的实现非常简单，只是将数值转换成了类型。不过请不要小看了它的作用，因为它为类型计算元函数提供了计算数值的桥梁。我们发现元函数plus的参数不再是数值类型而是类型本身，更有意思的是它也不再返回数值而是返回类型本身。请注意，对于类型计算的元函数，返回的是可公开访问的嵌套类型，我们通常约定该类型名为type。在这个例子中即是：using type = int_<T1::value + T2::value>;。当然，除了使用using来定义别名以外，使用typedef也是允许的。我选择使用using，一方面因为它是新标准推荐的做法，另一方面从语法上看它更像是一个赋值语句，作为元函数的一部分它更容易理解。

同样的道理，调用类型计算元函数也需要用到using或者typedef，例如：

using new_type = typename plus<int_<7>, int_<11>>::type;
static_assert(std::is_same_v<new_type, int_<18>>);

上面的代码可以成功编译，这表明通过元函数plus<int_<7>, int_<11>>::type得出的新类型new_type和预期结果int_<18>是符合的。

还有需要解释的一点是，虽然上文中介绍一些编写元函数的常规约定，但是有时候也可以灵活处理。比如，作为元函数的本体类模板，完全有能力返回多个嵌套类型或者常量数值：

template <class T1, class T2>
struct plus {
    using type = int_<T1::value + T2::value>;
    static constexpr int value = type::value;
};

这样修改的好处是能够直接访问元函数计算的数值结果，而不必通过::type间接的访问：

auto x = plus<int_<7>, int_<11>>::value;

最后也是元函数最重要的一个特点：特化。特化是C++模板元编程能够成立的根基。我们知道通过特化可以针对类模板的特定参数来规定类模板的具体行为，而元函数正是利用这一点来实现选择和循环等控制流的。关于特化在元函数中具体的使用方法，我将在后面的内容中详细介绍。

初探C++模板元编程

admin
CPP

C++模板元编程，通常来说是指利用模板控制编译器产生临时源代码的技术。该临时源代码可以和以后代码共同编译为可执行程序。由于模板元编程控制的是编译器，所以这个过程是在编译期进行，对于代码运行期的状态没有影响。

使用C++模板元编程编写的程序我们可以称之为模板元程序，最简单的模板元程序我们可以写成这样：

#include <iostream>
#include <type_traits>
int main() {
  using mytype = int;
  std::cout << "std::is_same<mytype, int>::value = "
            << std::is_same<mytype, int>::value << std::endl;
  return 0;
}

在上面的代码中std::is_same<mytype, int>::value是典型的模板元程序代码，编译器会在编译期对这句代码进行计算，最终产生以下临时代码：

std::cout << "std::is_same<mytype, int>::value = "
            << 1 << std::endl;

进一步可以看出，由于std::is_same<mytype, int>::value在编译期已经得出结果，所以它并不会对程序的运行产生任何副作用。

解释到这里，我想读者应该对C++模板元编程和模板元程序有了一个大概的理解。实际上，在我刚刚接触到模板元程序的时候，最疑惑的问题就是它为什么叫做元程序（metaprogram）。经过一番研究后发现，meta起源于希腊语，有after和beyond的含义，作为前缀通常用于表达更高抽象水平的描述。比如在解释数据库元数据（MetaData）时，我们说它是定义数据的数据。而联想到元程序，同样也可以理解为定义程序的程序。熟悉编写编译器的读者应该会接触到flex和bison（或者lex和yacc）。它们是一对词法和语法的解析器生成器，我们可以通过定义词法和语法规则让它们生成出相当完善的词法和语法的解析器源代码，所以flex和bison就是一对最典型的元程序。

最早的C++模板元程序

1994年Erwin Unruh在C++委员会上提交了下面这份代码：

// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
    };

template < int i > struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    void f() { D<i> d = prim; }
    };

struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
    Prime_print<LAST> a;
    }

从类模板命名上看，它似乎是一份打印质数的代码。但是请注意，这份代码在现在看来并不符合当前C++的语法规范，所以是无法通过编译的。实际上，当时Erwin Unruh使用的是一款叫做Metaware Compiler的编译器编译的上述代码，虽然仍然无法通过编译，但是却能输出一些有趣的信息：

MetaWare High C/C++ Compiler R2.6
(c) Copyright 1987-94, MetaWare Incorporated
E "primes.cpp",L16/C63(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<2>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<3>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<5>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<7>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<11>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<13>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<17>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<19>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<23>´ ("primes.cpp",L2/C25).
-- Detected during instantiation of Prime_print<30> at "primes.cpp",L21/C5:
E "primes.cpp",L11/C25(#416):   prim
|    Type `enum{}´ can´t be converted to txpe `D<29>´ ("primes.cpp",L2/C25).

观察上面这份编译器输出的错误信息，我们发现每条错误信息都给出了一个质数，例如D<2>、D<3>、D<4>等等，这说明编译器在编译阶段已经开始了对模板的计算。在1994年之后，Erwin Unruh发现上述代码已经不能被新语法所支持，所以在2002年发布了新代码：

// Prime number computation by Erwin Unruh

template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
 enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0), i-1> :: prim };
};

template <int i> struct Prime_print {
 Prime_print<i-1> a;
 enum { prim = is_prime<i, i-1>::prim };
 void f() { D<i> d = prim ? 1 : 0; a.f();}
};

template<> struct is_prime<0,0> { enum {prim=1}; };
template<> struct is_prime<0,1> { enum {prim=1}; };

template<> struct Prime_print<1> {
 enum {prim=0};
 void f() { D<1> d = prim ? 1 : 0; };
};

#ifndef LAST
#define LAST 18
#endif

main() {
 Prime_print<LAST> a;
 a.f();
}

这份代码可以用较老版本的GCC编译，比如GCC 4.1，同样的它会让编译器计算并打印出关于质数的错误信息（由于错误信息过多影响阅读，所以这里省略了无用部分，想看完整错误信息的读者可以自己尝试编译上述代码。）：

<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 17]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 13]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 11]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 7]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 5]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 3]'
...
<source>:12: error:   initializing argument 1 of 'D<i>::D(void*) [with int i = 2]'

虽然这份代码可以使用GCC编译，不过有些遗憾的是，它依然无法编译成功。为了弥补这个缺憾，我再次对这份代码进行了修改，修改的目的有两个：

  1. 使用现代C++语法；
  2. 消除错误信息，让代码能够顺利的编译。
template <int... args>
struct prime_values {
  static const int size = sizeof...(args);
};

template <class T, T t, class U, template <T...> class R>
struct add_to {};

template <class T, T t, template <T...> class U, template <T...> class R,
          T... args>
struct add_to<T, t, U<args...>, R> {
  using result = R<t, args...>;
};

constexpr int is_prime2(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }

  return 1;
}

template <int n, int>
struct prime_list {
  using result = typename prime_list<n - 1, is_prime2(n - 1)>::result;
};

template <int n>
struct prime_list<n, 1> {
  using result =
      typename add_to<int, n,
                      typename prime_list<n - 1, is_prime2(n - 1)>::result,
                      prime_values>::result;
};

template <>
struct prime_list<2, 1> {
  using result = prime_values<2>;
};

template <int n>
using get_prime_list_t = typename prime_list<n, n - 2>::result;

#ifndef LAST
#define LAST 18
#endif
#pragma GCC diagnostic push
#pragma GCC diagnostic warning "-Wsign-compare"
template <class T>
struct DbgPrintType {
  enum { n = sizeof(T) > -1 };
};

#define PRINT_TYPE(x) DbgPrintType<x>();
#define PRINT_VALUE_TYPE(x) DbgPrintType<decltype(x)>();
#pragma GCC diagnostic pop

int main() {
  get_prime_list_t<LAST> x;
  PRINT_VALUE_TYPE(x);
}

对于不熟悉模板元编程的读者来说，上面的代码可能不是很好理解。不过没关系，后面会详细介绍模板元编程的细节。现在我只是想让读者看到模板元编程的强大和有趣之处。

使用支持C++17标准的GCC可以成功编译以上代码并且输出以下警告信息：

test.cpp: In instantiation of 'struct DbgPrintType<prime_values<17, 13, 11, 7, 5, 3, 2> >':
test.cpp:62:3:   required from here
test.cpp:53:24: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   53 |   enum { n = sizeof(T) > -1 };
      |              ~~~~~~~~~~^~~~

在这些警告信息中，我们可以清晰的看到一组倒序的质数序列17, 13, 11, 7, 5, 3, 2。值得注意的是，这条警告是我有意而为之的，目的是为了让编译器打印出质数序列。

事实上，从语法角度来说模板元编程是图灵完备（Turing Complete）的，也就是说理论上能够解决所有可计算的问题。不过有些遗憾的是，从编译器的角度来说模板元编程是图灵不完备的，因为作为循环的实现方法，递归在编译器中是有明确的深度限制的。

范型编程与C++模板元编程

泛型编程是一种编程风格，它允许程序员在强类型程序设计语言中编写代码时使用一些以后才指定的类型，并在实例化时作为参数指明这些类型。在C++语言中，实现范型编程的基础就是模板，换句话说模板也是为了让C++具有范型能力而设计的。

模板元编程则有些不同，正如我们在上文中看到的，它的出现更像是一个意外而并非有意设计。这也能解释模板元编程的语法为什么如此晦涩难懂。不过幸运的是，模板元编程除了晦涩难懂之外，还是带来了一些意外的惊喜。比如它可以为范型编程加入静态类型检查以及策略定制的能力。

接下来做什么

如果只是用C++模板元编程做数值计算，那么我敢肯定的说这种计算有90%是几乎没有意义的，因为使用运行期做数值计算往往是更好的方法。而真正让模板元编程具有价值的是它对类型的计算能力，通过类型计算能够让我们的代码更加通用且有更高的运行效率，当然代价是更加晦涩难懂的代码，更长的编译时间，以及更加复杂的错误信息。不过读者也不必担心这些代价，因为后续部分就是围绕着类型计算以及其相关问题展开的。

在后面的内容中，我们首先将接触到序列和元函数的概念以及它们的习惯用法。然后我们会使用序列和元函数完成基本的判断和循环操作。以上是模板元编程的基础部分，在此之后我们将实现一套轻量级的模板元编程库YAMPL（Yet Another MPL），YAMPL在接口上将非常接近Boost的MPL。请注意，实现YAMPL的目的并不是取代MPL，而是让我们牢牢掌握模板元编程的一种手段。

事实上，无论什么时候，只要用到模板元编程，STL的type_traits和Boost的MPL这些成熟的模板元编程库都应该是优先考虑的对象。其中STL的type_traits专注于完成关于类型的一些基本操作，它是模板元编程的基础设施，是一个正规模板元编程程序库必不可少的组成部分。而Boost的MPL则是一个强大的模板元编程框架，它构建于Boost的type_traits的基础之上，并且提供一套强大且连贯的工具集，这些工具能让C++模板元编程变得简单有趣。

打印机API相关的一点记录

admin
Tips

最近研究了一点Windows上打印相关的内容，发现打印这块的东西的确挺多的。比如纸张，分辨率，打印处理器，打印数据类型等等。

首先我们需要通过EnumPrintersW枚举打印机，为了方便我写了一个简单的类模板：

template<class T = PRINTER_INFO_2, int level = 2>
class CEnumPrinter {
public:
    void Init(ULONG flags)
    {
        ULONG bytes_needed = 0;
        ULONG elems_returned = 0;
        EnumPrintersW(flags, nullptr, level, nullptr, 0, &bytes_needed, &elems_returned);
        buffer_.resize(bytes_needed);
        EnumPrintersW(flags, nullptr, level, buffer_.data(), bytes_needed, &bytes_needed, &elems_returned);
        elems_returned_ = elems_returned;
    }

    ULONG Count()
    {
        return elems_returned_;
    }

    const T& operator[] (ULONG idx)
    {
        assert(idx < elems_returned_);
        return reinterpret_cast<T*>(buffer_.data())[idx];
    }

private:
    std::vector<UCHAR> buffer_;
    ULONG elems_returned_ = 0;
};

在枚举和选择目标打印机之后可以通过PRINTER_INFO_2中的pPrinterName获得打印机句柄。为了方便也写了一个类：

class CPrinterHandle {
public:
    ~CPrinterHandle() 
    {
        Close();
    }

    bool Open(LPCWSTR printer_name)
    {
        std::vector<WCHAR> name;
        name.resize(wcslen(printer_name) + 1);
        wcscpy_s(name.data(), name.size(), printer_name);
        return OpenPrinter(name.data(), &printer_, nullptr);
    }

    HANDLE Detach()
    {
        HANDLE h = printer_;
        printer_ = nullptr;
        return h;
    }

    HANDLE Attach(HANDLE printer)
    {
        HANDLE h = printer_;
        printer_ = printer;
        return h;
    }

    void Close()
    {
        if (printer_) {
            ClosePrinter(printer_);
            printer_ = nullptr;
        }
    }

    operator HANDLE() const
    {
        return printer_;
    }

private:
    HANDLE printer_ = nullptr;
};

而通过这个句柄就可以做很多的事情了，比如获取打印机的具体配置，弹出打印机属性对话框等等，这里以获取其支持的纸张类型为例：


template<class T = FORM_INFO_1, int level = 1>
class CEnumPrinterForm {
public:
    void Init(HANDLE hp)
    {
        ULONG bytes_needed = 0;
        ULONG elems_returned = 0;
        EnumForms(hp, level, NULL, 0, &bytes_needed, &elems_returned);
        buffer_.resize(bytes_needed);
        EnumForms(hp, level, buffer_.data(), bytes_needed, &bytes_needed, &elems_returned);
        elems_returned_ = elems_returned;
    }

    ULONG Count()
    {
        return elems_returned_;
    }

    const T& operator[] (ULONG idx)
    {
        assert(idx < elems_returned_);
        return reinterpret_cast<T*>(buffer_.data())[idx];
    }

private:
    std::vector<UCHAR> buffer_;
    ULONG elems_returned_ = 0;
};

可以枚举出类似A3、A4、B5这种纸张类型。不过这套打印数据的函数有一些不太友好，因为通过打印机句柄打印数据，我们只能传输emf或者raw格式的数据。而我们比较熟悉的方法是通过DC绘制图形并且打印，这样所见即所得用起来会更舒适。不过，这套API没有提供用打印机句柄转换到HDC的方法。只能通过PRINTER_INFO_2中的pPrinterName和pDevMode重新打开一个HDC，然后通过HDC相关的API进行打印。例如：

hdc = CreateDCW(NULL, info.pPrinterName, NULL, info.pDevMode);
DOCINFO docInfo = {0};
docInfo.cbSize = sizeof(docInfo);
docInfo.lpszDocName = L"test";

RECT rc = { 40, 10 };

StartDoc(hdc, &docInfo);
StartPage(hdc);
DrawTextA(hdc, "hello", -1, &rc, DT_SINGLELINE | DT_NOCLIP);
EndPage(hdc);
StartPage(hdc);
DrawTextA(hdc, "world", -1, &rc, DT_SINGLELINE | DT_NOCLIP);
EndPage(hdc);
EndDoc(hdc);

About

https://github.com/0cch

Categories

Tags

Tag Cloud

File System IDE Kernel MiniKernel NTFS NTInternals NTSTATUS OS PIO System Test Volume Windows grub snapshot

Archives

Recents