表驱动与面向对象编程

写在前面

---

现在回顾起来，我对于CPP的偏爱应该是有那么点“斯德哥尔摩综合症”在里面的：我所在本科学校的编程语言教学是直接从CPP上手的，大概学校是考量到了CPP囊括了C的原因。于是我在并未体会到C的简洁优雅的情况下就被动去接触繁复浩杂的CPP（对，我也不是主动去接触CPP的）——在没有一点编程的认知下便开始了“所谓”的OO概念的灌输，结果可想而知：写CPP程序期间各种百思不解，特别是CPP里面资源管理的复杂性使我一败涂地，甚至用不了模板出手。我那可怜的在没有任何框架帮助下的本科小毕设大概也就那么3k行不到就使我有了那种“无力感”——我很清楚的记得最后程序跑起来时给我的那种无法言喻的 “WTF, It works?!” 的感觉。后面我又断断续续的写一些东西，然而无论怎么写，一旦没有了Framework的支撑，我对于代码掌控能力就降了不止一个档次。

本科期间也不是没有去接触Java和C#（那时候大数据没有火起来，Python还不够普及），然而我比较死硬，死心眼子要跟CPP刚正面，也就没转去别的语言。当时有搞C#的大神说：“C#真是门好语言，能让你确实理解OO，理解设计模式”——当然现在看来大神之所以那样说极有可能大神本身就理解了OO，C#只是更容易表达他的OO思想。至于我么，说出来让大家见笑，设计模式这个东西我当时磕了一年，终究还是没弄明白这么个东西是到底怎么提出来的——“what, why, how”，三点一个都不明白。

现在来写这篇东西（可能不止这一篇），也算是我最近一段时间的对编程的理解了吧，就从OO，设计模式以及C/CPP开始。

正文

---

多态

这是一个基础的不能在基础的概念了，之前去实习面试的时候不止一次被问到过，然而这又不是一个很容易就能答好的问题。我当时的在听到这个问题的时候思考了一会，可能我的肢体语言跟面部表情让面试官觉得我对多态的概念比较模糊，于是直接转去问语言层面是怎么表达了（比如该加哪些关键字之类的……）。

对于这个问题我个人的看法是：多态是程序动态特性的集中体现。正如其字面意思：接口的不同实现形式即为多态，接口不同的实现方式即为“采取的策略”。在C/CPP中的多态其实是有两种形式的：静态和动态。

静态多态

亦即是常说的编译期多态，最常见于CPP模板编程中。这个概念我第一次是见于《Modern Design C++》这本书，书内着重介绍了一种基于模板的策略编程，应用场景以及举例如下：

1. 场景：
   假如有两个模块A和B，程序要求当A模块调用B模块中的接口时，需要先保存当前程序的状态，然后在调用返回的时候恢复为原来的状态。即使是模块A对模块B的同一个接口进行调用，也有可能根据不同的需要保存不同的状态。
2. 场景代码

   struct StatePolicyA
   {
   	StatePolicyA()
   	{
   		// do save policy A
   		printf("Save states with Policy A\n");
   	}
   	~StatePolicyA()
   	{
   		// do restore
   		printf("Restore states with Policy A\n");
   	}
   };
   
   struct StatePolicyB
   {
   	StatePolicyB()
   	{
   		// do save policy B
   		printf("Save states with Policy B\n");
   	}
   	~StatePolicyB()
   	{
   		// do restore
   		printf("Restore states with Policy B\n");
   	}
   };
   
   struct ModuleB
   {
   	void interface1()	{
   	
   		printf("Module B interface 1\n");
   	}
   	void interface2()	{
   	
   		printf("Module B interface 2\n");
   	}
   };
   
   struct ModuleA
   {
   	// other functions
   	ModuleB m_moduelB;
   
   	template<typename StatePolicy>
   	void callModuleB_interface01()	{
   	
   		StatePolicy state;
   		m_moduelB.interface1();
   	}
   
   	template<typename StatePolicy>
   	void callModuleB_interface02()	{
   	
   		StatePolicy state;
   		m_moduelB.interface2();
   	}
   };
   
   
   int main(int argc, char* argv[]) {
   
   	ModuleA ma;
   	printf("With Policy A-->\n");
   	ma.callModuleB_interface01<StatePolicyA>();
   	printf("\nWith Policy B-->\n");
   	ma.callModuleB_interface01<StatePolicyB>();
   	system("pause");
   	return 0;
   }

如果有看过前文View CPP Template 的话，就会发现这个技巧其实就是利用模板向函数中传递了一个类型而，当模板被实例化的时候，类型将会被具现，从而完成任务。

我们知道CPP中引入模板的初衷就是为了提供一个比C中的宏更有力和更安全的“代码生成机制”，也就是说模板的一部分功能可以由C的宏来实现，这个技巧最有代表性的应该就是Linux中的“侵入式链表”，这里不对其做详细介绍，只举一个简单的例子来说明这种技巧，下面的例子中，如果将宏展开来，就可以看到生成了包含有int以及float两个不同类型的链表节点结构：

#define List(type) struct List##_##type { type data; List##_##type * next;}

typedef List(int) ListInt;
typedef List(float) ListFloat;
typedef List(ListInt) ListListInt;

int main(int argc, char* argv[]) {

	ListInt ihead;
	ihead.data = 1;
	ihead.next = NULL;
	printf("Int Head: data = %i, next = %p\n",ihead.data, ihead.next);

	ListFloat fhead;
	fhead.data = 3.5f;
	fhead.next = NULL;
	printf("Float Head: data = %f, next = %p\n", fhead.data, fhead.next);

	ListListInt llhead;
	llhead.data = ihead;
	llhead.next = NULL;
	printf("ListListInt Head: data = %i, next = %p\n", llhead.data.data, llhead.next);

	system("pause");
	return 0;
}

事实上静态的多态比OO语言中动态的多态更容易看清楚问题的本质：实际上多态只是不同的“过程”而已，这个不同的过程被通过一个统一的接口进行描述，使得“外界”看起来一样而已。

在这里我无意探讨宏于模板之间的异同以及模板的机理，原因很简单，我对语言理论的理解尚浅，还未有够格。在这里只引用一小段话来说明C++模板的特殊之处：

C++ templates are essentially language-aware macros.
Each instance generates a different refinement of the same code.
	—— from notes of 'Programming Languages and Translators', Fall 2012, Columbia University.

动态多态

动态多态就非常常见了，我们熟知的具有OO性质的语言都提供了这种特性，一般是通过函数覆盖来实现的，比如C++中提供了关键字virtual，而在Java中则是将所有的成员函数都视为是可以覆盖的虚函数。这里就不再赘述了，当然一同提供的还有“向上、向下”的类型转换机制。这里我们就不提供相关代码了，只大致说明一下单继承情况下的虚函数机制，多继承可以以此为根基进行拓展。

在单继承情况下，每个类都包含了一个指向虚函数表vtable的指针，这个表中记录了当前类中那些成员函数是虚函数（在C++中，如果一个根基类没有声明virtual关键字，那么是不会包含这个vtable指针的）：

BaseClass:
+---------+
| vtable -|-------+
|         |       |
|   ...   |       |
+---------+       |
                  |
虚函数表：         |
+-----------+ <---+		
| vb func 1 |
| vb func 2 |
|           |
+-----------+

如果这个类有一个继承它的子类，并且它重写覆盖了基类的virtual func 2，那么它的情况将会是下面这样：

DeriverClass : BaseClass
+---------+
| vtable -|-------+
|         |       |
|   ...   |       |
+---------+       |
                  |
虚函数表：         |
+-----------+ <---+		
| vb func 1 |	这里复制了基类的成员函数的地址
| vd func 2 |	这里更新了自己定义的成员函数的地址
|           |
+-----------+

这样继承类的实例对象就能够正确找到自己新定义的函数了。当然类的析构函数与普通的函数是不同的，析构函数会经过一个链式结构从根基类的析构函数开始，按照继承链执行每一个析构函数，直到这个类自己的析构函数执行完毕结束。
当然C++标准并没有规定虚函数表的指针应该放在类的哪个位置，这要视编译器的实现而定。

表驱动

通过前面对多态的描述我们可以看到，OO的过程实际上就是对不同的“process”通过一个统一的interface进行调用的过程。process这个概念放到C里面就是C函数；放在C++里面可以是C风格的函数，也可以是用class封装而成的Functor，在C++11中更可以是一个lamdba；至于在Java和C#中就是class或者lambda，在函数式编程中就是一个Closure，或者一个Continuation。并且通过前面的论述，我们成功在动态多态中引入了表的话题。

我们先来说结论：OO语言中的类，其实是一个大的函数转发表。

这个结论其实很好理解：除却上文提到的虚成员函数之外，对于类的非虚成员函数，我们知道它是类相关的。而在C语言中，是没有类这跟概念的，这一点我们可以通过一个小小的中间层的帮助来体会一下它们之间的异同：

void func0(void) { printf("c style func 0\n"); };
void func1(void) { printf("c style func 1\n"); };
void func2(void) { printf("c style func 2\n"); };
void func3(void) { printf("c style func 3\n"); };

typedef void(* vvfunc)(void);
vvfunc table[4] = {func0,func1,func2,func3};

void printCfunc(vvfunc* tb, int index){

	if (index < 0 || index >= 4) {
		printf("Exception : index out of range!\n");
		return;
	}
	tb[index]();  // call func
}

int main(int argc, char* argv[]) {
	printCfunc(table,0);
	printCfunc(table,1);
	system("pause");
	return 0;
}

上面是C代码，通过一个函数表，和一个索引来调用我们的函数。注意这里仅仅是为了简化说明使用了数组结构，事实上使用一个map，用函数名来索引将会更加贴近我们编写实际看到的情况（当然编译器很有可能性还是使用一个offset来索引）。

struct Funcs
{
	void func0(void) { printf("oo style func 0\n"); };
	void func1(void) { printf("oo style func 1\n"); };
	void func2(void) { printf("oo style func 2\n"); };
	void func3(void) { printf("oo style func 3\n"); };
};

Funcs oo_tb;

int main(int argc, char* argv[]) {
	oo_tb.func0();
	oo_tb.func1();
	system("pause");
	return 0;
}

上面是C++代码，通过类直接调用了函数。对比一下前面C风格的代码，这里的Funcs oo_tb就相当于vvfunc table[4]；main函数中直接对成员函数的调用就相当于C代码部分由printCfunc通过一个函数表指针（C++中就是那个众所周知的this了）和一个索引（在C++中是无法看到的，这一步由编译器帮忙做了）来调用需要的函数。

上面的例子还是比较简单的，如果加入函数重载的特性，那么就需要另外考虑到语义的问题了（函数类型），不适合用来做一个简单明了的说明。但无论加不加重载，最基本的道理是相同的，都是通过转发表来实现。如果想更加了解表驱动编程，推荐阅读《代码大全》相关章节。

结语

---

这边文章的中心意思基本讲述完毕了，最后让我们以两个设计模式的例子来加深一下对文章的理解：

策略模式

• C++代码

  struct Plan
  {
  	virtual void proc(void) = 0;
  };
  
  struct Plan_A : public Plan
  {
  	virtual void proc(void) { printf("Plan A is choosed\n"); }
  };
  
  struct Plan_B : public Plan
  {
  	virtual void proc(void) { printf("Plan B is choosed\n"); }
  };
  
  struct TheMan
  {
  	void choose(Plan& plan) { plan.proc(); }
  };
  
  int main(int argc, char * argv[]) {
  	TheMan man;
  	Plan_A a;
  	Plan_B b;
  	man.choose(a);
  	man.choose(b);
  	system("pause");
  	return 0;
  }

• 对应的C代码

  void PlanA(void) { printf("Plan A is choosed\n"); }
  void PlanB(void) { printf("Plan B is choosed\n"); }
  
  void man_choose(void(* pfun)(void))
  {
  	pfun();
  }
  
  int main(int argc, char * argv[]) {
  	man_choose(PlanA);
  	man_choose(PlanB);
  	system("pause");
  	return 0;
  }

这个还是比较好理解的，只用了一次转发。

访问者模式

• C++代码

  // 写完才发现今天是12.25...
  struct Accepter_A;
  struct Accepter_B;
  
  //////////////////////////////////////////////////////////////////////////
  // visitor
  struct Visitor
  {
  	virtual void visit(Accepter_A& accepter) = 0;
  	virtual void visit(Accepter_B& accepter) = 0;
  };
  
  struct Visitor_SelfIntro : public Visitor
  {
  	void visit(Accepter_A& accepter) { printf("I am A\n"); }
  	void visit(Accepter_B& accepter) { printf("I am B\n"); }
  };
  
  struct Visitor_Greetings : public Visitor
  {
  	void visit(Accepter_A& accepter) { printf("Hey~\n"); }
  	void visit(Accepter_B& accepter) { printf("Hi~\n"); }
  };
  
  //////////////////////////////////////////////////////////////////////////
  // accepter
  struct Accepter
  {
  	virtual void accept(Visitor& v) = 0;
  };
  
  struct Accepter_A
  {
  	virtual void accept(Visitor& v) { v.visit( * this); }
  };
  
  struct Accepter_B
  {
  	virtual void accept(Visitor& v) { v.visit( * this); }
  };
  
  int main(int argc, char * argv[]) {
  	Accepter_A a;
  	Accepter_B b;
  	Visitor_SelfIntro intro;
  	Visitor_Greetings greeting;
  
  	a.accept(greeting);
  	a.accept(intro);
  
  	b.accept(greeting);
  	b.accept(intro);
  
  	system("pause");
  	return 0;
  }

• visitor模式被认为是GoF书中较为难以理解的模式，主要在于它使用了双重转发。我们先来梳理它是怎么工作的，然后将其换位对应的C代码：

1. 过程：
   每一个accpter接受一个visitor，并根据visitor的具体实例来做出对应的动作。
   每个visitor定义所有的accpeter的具体动作，实际工作的时候只调用accpter来接受不同的visitor就可以达到目的了。所谓的双重转发是指：第一次转发在接受visitor时的动态转发，第二次转发在visitor根据接受它的accpter的类型进行一次静态转发（函数重载）。
2. 对应的C代码

   typedef void(* vvfunc)(void);
   void visitor_selfintro_A() { printf ("I am A\n");}
   void visitor_selfintro_B() { printf ("I am B\n");}
   vvfunc visitor_selfintro[2] = {visitor_selfintro_A,visitor_selfintro_B};
   
   void visitor_greetings_A() { printf ("Hey~\n");}
   void visitor_greetings_B() { printf ("Hi~\n");}
   vvfunc visitor_greetings[2] = {visitor_greetings_A,visitor_greetings_B};
   
   void accepter_A(vvfunc * vtb) {vtb[0]();}//注意，这里的转发过程直接写进去了
   void accepter_B(vvfunc * vtb) {vtb[1]();}//注意，这里的转发过程直接写进去了
   
   int main(int argc, char * argv[]) {
   	accepter_A(visitor_greetings);
   	accepter_A(visitor_selfintro);
   	accepter_B(visitor_greetings);
   	accepter_B(visitor_selfintro);
   	system("pause");
   	return 0;
   }

尝试把OO设计模式用C表述一下，结果发现蛮好玩的，后面应该还会继续做，争取把常用的几个模式给过一遍。

收工，写篇文章真心花时间……