C/C++编程：栈类模板&异质链表

短命女 2023-01-16 06:55 111阅读 0赞

# 类型无关的数据结构 #

template <typename T = int>
    struct  list_node{
        
        T value;
        list_node *next;
    };
    
    
    void caller2(){
        
        list_node<int> inode;
        list_node<float > fnode;
        list_node< > inode1;
    };

上面list\_node指针中的list\_node相当于list\_node。因为c++规定：**在一个类模板中出现的自身模板名，等价于该模板被调用时所生成的实例**

如果类模板有默认值，则在实参列表中可以省略。如果所有参数都有默认值，则模板实参列表可以省略，但是`<>`不能省略，比如 `list_node< > inode1`。

与函数模板不同的是，类模板没有模板参数实参推导机制(使用类时不需要参数，自然也就无法根据参数推导了)。所以，对于没有默认值的模板参数，只能为其一一赋值，而可以省略的仅限于列表后面有默认值的相关相邻参数。

# 栈类模板 #

#include <iostream>
    
    template <typename T> class my_stack; // 前置栈内模板声明
    
    template <typename T>
    class list_node{
        
        T value;
        list_node * next;
    
        // 私有构造函数，只能由友类构造
        list_node(T const &v, list_node *n) : value(v), next(n){
        }
    
        // 友类:为了方便my_stack直接访问其成员
        friend class my_stack<T>;
    };
    
    template <typename T = int>
    class my_stack{
        
        // node_type别名（推荐这样做）：这样在随后用到list_node模板就无须一一给出实参
        typedef list_node<T> node_type;
        node_type  *head;
    
        //my_stack不可复制构造，不可赋值
        my_stack operator=(my_stack const &){
        }
        my_stack (my_stack const &s){
        }
    
    public:
        // 构造和析构
        my_stack() : head(0){
        }
        ~my_stack() {
         while (!empty()) pop();}
    
        // 在类模板内实现的成员函数模板
        bool empty() const {
         return  head == 0; };
        T const & top() const noexcept(false){
        
            if (empty())
                throw std::runtime_error("stack is empty");
            return head->value;
        }
        void push(T const&v){
        head = new node_type(v, head);}
    
        // 成员函数声明，将在类模板外实现
        void pop();
    };
    
    // 在类模板外实现的成员函数模板
    template <typename  T>
    void my_stack<T>::pop() {
        
        if (head){
        
            node_type *tmp = head;
            head = head->next;
            delete tmp;
        }
    }

类模板不仅可以用来生成类实例，还可以作为其他类或者类模板的基类：

template <typename T=int>
    class count_stack : public my_stack<T>{
        
        typedef my_stack<T> base_type; // 推荐
    public:
            //...
    };

类模板的基类必须是某个类型，所以基类应该写为`my_stack<T>`，即保存T型数据的my\_stack类模板实例类型

当然，如果是普通类以类模板实例为基类，需要为基类模板给定明确的模板参数值：

class count_stack : public my_stack<char>{
        
    
    };

# 异质链表 #

上面的链表节点类模板只有一个模板参数，即节点所保存的数据类型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){
        }
    };
    
    template<typename T, typename N>
    hetero_node<T, N>* push(T const&v, N *n){
        
    	return new hetero_node<T, N>(v, n);
    }
    
    template<typename T, typename N>
    N* pop(hetero_node<T, N>*  head){
        
    	N *next = head->next;
    	delete head;
    	return next;
    }

类模板hetero\_node由两个模板参数，T定义节点所保存的数据类型，N定义链表中下一个节点的类型。异质链表使用实例：

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("sone"), push('a', push(1, (void*)0)));
    
        // 通过next成员可以访问三元组中任意成员
        std::cout << p2->value << "\t"
                << p2->next->value << "\t"
                << p2->next->next->value << "\n";
    
        // 嵌套pop正确释放内存销毁三元组
        return 0;
    }

# 构造元组 #

用异质链表构造多元组需要各个节点的成员变量next来保存元组数据间的联系，next指针所占内存空间有额外开销。可以通过构造模板来改进这个问题

## 通过嵌套实现元组 ##

#include <string>
    #include <iostream>
    
    
    template <typename T, typename N>
    struct tuple{
        
        T value;
        N next;
        tuple(T const &v, N const &n) : value(v), next(n){
        }
    };
    
    template <typename T, typename N>
    tuple<T, N> push(T const &v, N const&n){
        
        return tuple<T, N>(v, n);
    }
    
    int main(){
        
        // 通过typedef构造4个元素的元组类型
        typedef tuple<int, char> tuple2;
        typedef tuple<float, tuple2> tuple3;
        typedef tuple<std::string, tuple3> tuple4;
    
        tuple4 p2 = push(std::string("sone"), push(.1f, push(1, 'a')));
    
        // 通过next成员可以访问三元组中任意成员
        std::cout << p2.value << "\t"
                  << p2.next.value << "\t"
                  << p2.next.next.value<< "\n";
        return 0;
    }

上面虽然消除了额外存储开销，但是带来了构造元组时元素的重复复制问题。比如上例中的`a`，在嵌套调用push函数构造元素时，每调用push函数构造元组时，每调用一次就被复制一次。

## 用类实现 ##

实际上，最简单的元组构造法就是摒弃嵌套，直接用一个类来实现：

template <typename T0, typename T1, typename T2>
    struct tuple3{
        
        T0 v0;
        T1 v1;
        T2 v2;
        
        tuple3(T0 const &_v0, T1 const&_v1, T2 const &_v2) :
        v0(_v0), v1(_v1), v2(_v2){
        }
    };

上面方法解决了额外存储开销和重复复制问题，但是新的问题是只能构造3元组，如果要构造4元组、5元组就要求准备新类。不过利用宏定义，可以很方便的自动生成tuple1-tuple20的所有类模板