2.3　突破——异质链表

例2.1中的链表节点类模板只有一个模板参数，即节点所保存的数据类型T，而节点中的另一个成员变量next指针，其类型固定为指向另一同类型节点类，这就约束了链表中节点必须是同一类型，从而整个链表只能保存同一类型的数据。

试想next指针所指类型也由一个新的模板参数定义则会如何？next将可以指向任何一种类型，也包括保存有其他类型值的节点。那么由此节点类模板的一系列实例构成的链表就可用于保存不同类型的值，构成一种异质链表。按照这个思路，对list_node类模板稍加改动，改后的类模板代码如下：

template<typename T, typename N> 
struct hetero_node  
{  
    T value;  
    N* next;  
    hetero_node(T const &v, N *n) : value(v), next(n) {}  
}; 

类模板hetero_node有两个模板参数，T定义节点所保存数据类型，而N则定义链表中下一个节点的类型。假设需要一个数据结构保存三个数据分别为int、char及std::string类型，则用hetero_node类模板可以构造出一个拥有三个节点分别保存以上三个数据的异质链表。具体构造方法如下所示：

typedef hetero_node<int, void> node_0;  
node_0* p0;  
typedef hetero_node<char, node_0> node_1;  
node_1* p1;  
typedef hetero_node<std::string, node_1> node_2;  
node_2* p2;  
// 忽略中间申请空间及赋值过程  
p1->next = p0;  
p2->next = p1; 

经过这样处理后，只需要保存p2就可以保存整个链表及其上的数据。而访问该链表上的数据也很简单，通过一系列的next找到相应指针后读取其所指value值即可，例如：

std::string s = p2->value;  
char c = p2->next->value;  
int i = p2->next->next->value; 

异质链表中增加数据的操作可用函数模板来实现，如例2.4所示。

例2.4

template<typename T, typename N> 
hetero_node<T, N>* push(T const &v, N *n)  
{  
    return new hetero_node<T, N>(v, n);  
} 

从异质链表中删除链表首数据的函数如例2.5所示。

例2.5

template<typename T, typename N> 
N* pop(hetero_node<T, N> *head) {  
    N *next = head->next;  
    delete head;  
    return next;  
} 

借助函数模板的模板参数自动推导机制，在调用pop函数模板时无须显式给出模板参数的值，而只需要给出一个诸如hetero_node<char, node_0>*型的指针变量作为函数参数，编译器就可推导出T=char及N=node_0。如果要释放之前所有三个节点的内存，可以通过嵌套调用pop的方式实现，代码如下：

pop(pop(pop(p2))); 

异质链表的每个节点类型都不相同，即使所保存数据类型都相同，其节点类型也不同。例如从空链表开始连续插入三个int数时，链表中三个节点的类型依插入顺序分别为：

typedef hetero_node<int, void> node_0;  
typedef hetero_node<int, node_0> node_1;  
// 即 hetero_node<int, hetero_node<int, void>> 
typedef hetero_node<int, node_1> node_2;  
// 即 hetero_node<int, hetero_node<int, hetero_node<int, void>>> 

所以异质链表无法像普通链表一样，用一个指向节点类型的指针来遍历整个链表，而需要在每次压入数据后，根据新入栈节点类型引入新指针来指向链表头节点。这使得异质链表的用法受到很大限制。要将一组数据插入异质链表，无论数据类型是否相同，都必须逐行声明新节点类型指针以及调用插入函数模板等，而无法像普通链表一样采用一个循环实现批量插入、删除或访问数据。

异质链表的作用更类似于元组（tuple），可将一组数量已知、类型已知且不同的数据组合在一起并在不同函数间传递。借助异质链表的入栈/出栈函数模板可方便构造不同元素数的元组。例如，通过嵌套调用push模板可以很方便地构造一个三元组，而嵌套调用pop模板则可以销毁一个三元组。根据节点的next指针可以顺藤摸瓜地取到三元组中每个元素值。以下程序演示了异质链表构造的三元组的用法。

// 假设之前hetero_node的定义都放在文件“hetero_stack.hpp”中  
#include "hetero_stack.hpp"  
#include <string> 
#include <iostream> 
 
int main()  
{  
    typedef hetero_node<int, void> node_0;  
    typedef hetero_node<char, node_0> node_1;  
    typedef hetero_node<std::string, node_1> node_2;  
 
    // 嵌套调用push模板以构造三元组  
    node_2 *p2 = push(std::string("Awesome!"),  
                      push('a',  
                           push(1, (void*)0)));  
 
    // 通过next成员可以访问到三元组中任意成员  
    std::cout << p2->value << ", "  
              << p2->next->value << ", "  
              << p2->next->next->value << std::endl;  
 
    // 而通过嵌套调用pop模板则可以正确释放内存销毁三元组  
    pop(pop(pop(p2)));  
 
    return 0;  
}