C++泛型与多态（1）：基础篇

C++的泛型编程是一种非常强大的武器。但它看上去复杂的语法，以及背后不明的原理，一直让很多程序员望而生畏。很多即便已经使用了C++很久的程序员也仅仅敢触碰其非常表象的部分。还有一些大胆而莽撞的程序员则对其进行滥用，让本来可以简单解决的问题，变成秀技场。因而，泛型技术一直得到一个不公正的名声：奇技淫巧。

但是，泛型编程对于很多问题的高效解决是不可或缺的。它是C++最重要的元编程工具，也是很多框架制作的利器，也是组合式设计的主要手段之一。不掌握它，C++的强大威力将大打折扣。

我们需要深入挖掘其背后的原理及本质，这样才能理解它，掌握它，在合适的场合使用它，避免滥用和无用。

C++的泛型编程，其本质其实非常简单：为了做基于类型和常量的编译时多态。（关于多态的目的和价值，请参阅《多态，FP与OO》)

而C++的编译时多态由如下四种类型构成:

模版
函数（操作符）重载
模板特化
Duck Typing

我们下面一一介绍。

1. 模版：参数化多态

先看一段简单的haskell代码：

max :: (Ord a) => a -> a -> a
max x y = if x > y then x else y

在这个实现里，a是类型变量，(Ord a)表示对a约束，意思是：对于所有属于typeclass Ord的类型a，都可以实例化这个函数。

这种用法被称作参数化多态。很显然，参数化多态是为了避免基于类型的重复代码。

而回到C++，基于模版的实现则为：

template <typename T>
T max(T a, T b)
{
   return a > b ? a : b;
}

参数化多态，是C++提供泛型的最初目的。STL的各种容器和算法，基本上都是基于这类目的设计的。这也是最容易理解，被使用最为广泛的C++编译时多态技术。

Concept

上述haskell代码中的约束Ord a，到C++14为止尚未支持，但已经确定要在C++17中支持（被称作Concept）。

高阶类型

上述haskell例子中的多态类型属于rank 1 type，但rank 1 type无法支持这类的代码：

g f = (f True, f 'a')

其中，参数f作为一个函数，在两次调用时传入的参数类型不同：分别为Bool和Char。这属于Rank 2 Type的范畴。而为了支持Rank 2 Type，GHC提供了一个扩展`RankNTypes'，并且要求程序员给出类型注解：

{-# LANGUAGE RankNTypes #-}

g :: (forall a. a -> a) -> (Bool, Char)
g f = (f True, f 'a')

而在C++中，对应的实现技术为Template Template Parameter。比如：

template <typename T, typename G,
template <typename E> class Container >
struct Foo
{ 
  Container<T> tContainer; 
  Container<G> gContainer;
};

这就是参数化多态的全部：非常简单，因而被很多语言采纳和引入，也被程序员广泛的使用。

2. 函数重载：Ad-hoc多态

学习任何一门语言的第一个例子,往往都是Hello World:

std::cout << "Hello, 2016!" << std::endl;

如果我们让程序稍微复杂一些，让这段代码可以对在任何一年都可以复用，那么我们可以提供一个类似于下面的函数：

void helloNewYear(unsigned int year) 
{ 
  std::cout << "Hello, " << year << "!" << std::endl;
}

在这个实现中，对于字符串和整数这两种不同类型的数据，std::cout可以用一致的方式来操作。

按照多态四要素，std::cout即是客户；同一外表是操作符<<；而不同形态则是针对不同类型的不同实现：

std::ostream& operator<<(std::ostream& os, const std::string& str);
std::ostream& operator<<(std::ostream& os, const int value);
// ...

而编译器会根据类型进行匹配（这是一种简化版本的模式匹配），从而在不同形态间进行选择。

因而函数重载是一种多态，而这样的多态被称作ad-hoc多态。

例子：双重派发

双重派发（Double Dispatch），是访问者模式（Visitor Pattern）依托的的实现技术。

假设，一颗语法树，上面有多种类型的节点。比如：Statement，Expression。

而一个访问者则必须提供针对各种类型节点的访问函数，比如:

struct Visitor 
{ 
   virtual void visit(Statement&) = 0; 
   virtual void visit(Expression&) = 0; 
   virtual ~Visitor() {} 
};

所有的节点都需要实现accept方法，所以它们都需要实现下面的接口:

struct Element 
{ 
  virtual void accept(Visitor&) = 0; 
  virtual ~Element() {} 
};

而每个具体的节点在实现此接口时，分别调用Visitor中针对自己类型的成员函数:

struct Statement: Element 
{ 
  void accept(Visitor& visitor) 
  { 
    visitor.visit(*this); 
  } 
    
  // ... 
};
 
struct Expression: Element 
{ 
  void accept(Visitor& visitor) 
  { 
    visitor.visit(*this); 
  } 
  // ... 
};

所谓双重派发，指的正是两个多态结构:

访问算法通过接口accept,在运行时将visitor派发给相应的 Element;
具体的Element再从visitor的多个访问函数中，选择归属于自己的那一个，通过它，将自己派发给visitor。

其中，前者使用的是运行时多态，后者使用的则是函数重载。有了函数重载，就完全没必要让每个具体的Element重复的编写完全相同的accept实现。所以，我们可以将上述代码重构为:

template <typename T>
struct AutoDispatchElement : Element 
{ 
  void accept(Visitor& visitor)
  { 
     visitor.visit((T&)*this); 
  } 
};
 
struct Statement 
   : AutoDispatchElement<Statement>
{ 
  // ... 
};
 
struct Expression
   : AutoDispatchElement<Expression> 
{ 
  // ... 
};

并非所有重载都是为了多态

需要强调的是：尽管函数（操作符）重载可以用来实现编译时多态，但并非所有的重载都是为了多态。大多数情况下，操作符的重载都是为了提高表达力，比如:

// 让复数可以进行 a + b 形式的操作
Complex operator+(const Complex& lhs, const Complex& rhs); 

// 让向量可以进行 vector[5] 形式的操作
template <typename T>
T Vector<T>::operator[](unsigned int index);

至于那些参数个数不同的重载函数，与多态更是没有什么关系，比如:

void f(int a) 
void f(short a, double b);

这种样式的重载，往往是因为开发人员懒得为之取一个更准确的名字，从而滥用了语言提供的重载机制，其结果反而伤害了表达力。对于这样的重载，要尽量避免。

小结

这一部分我们首先介绍了C++范型最为简单的两种多态：以基于类型的重用为目的参数化多态和以函数重载为手段的ad-hoc多态。

在后续的文章里，会继续介绍更为复杂的C++编译时多态技术。

C++泛型与多态（1）：基础篇