模板与泛型编程

--类模板成员

引言：

这一节我们介绍怎样实现前面提到的Queue模板类。

标准库将queue实现为其他容器之上的适配器。为了强调在使用低级数据结构中设计的编程要点，我们将Queue实现为链表。实际上，在我们的实现中使用标准库可能是个更好的决定!!-_-。

1、Queue的实现策略

如图所示，我们实现两个类：

1）QueueItem类表示Queue的链表中的节点，该类有两个数据成员item和next：

a. item保存Queue中元素的值，它的类型随Queue的每个实例而变化；

b. next是队列中指向下一QueueItem对象的指针。

2）Queue类提供16.1.2节描述的接口函数，Queue类也有两个数据成员：head和tail，这些成员是QueueItem指针。

像标准容器一样，Queue类将复制指定给它的值。

2、QueueItem类

template <typename Type> class QueueItem
{
    QueueItem(const Type &t):item(t),next(0) {}

    Type item;
    QueueItem *next;
};

每当实例化一个Queue类的时候，也将实例化QueueItem的相同版本。如：如果创建Queue<int>，则将实例化一个伙伴类QueueItem<int>。

QueueItem类为私有类–他没有公共接口。我们定义这个类只是为了实现Queue，并不想用于一般目的。需要将Queue类设为QueueItem的友元，以便Queue的成员能够访问QueueItem的成员。

【注解】

在类模板的作用域内部，可以用它的非限定名字引用该类。

3、Queue类

template <typename Type> class Queue
{
public:
    Queue():head(0),tail(0) {}
    Queue(const Queue &Q):head(0),tail(0)
    {
        copy_elems(Q);
    }

    Queue &operator=(const Queue &);
    ~Queue()
    {
        destroy();
    }

    Type &front()
    {
        return head -> item;
    }
    const Type &front() const
    {
        return head -> item;
    }

    void push(const Type &);
    void pop();
    bool empty() const
    {
        return head == 0;
    }

private:
    QueueItem<Type> *head;
    QueueItem<Type> *tail;

    void destroy();
    void copy_elems(const Queue &);
};

 private实用函数destroy和 copy_elems将完成释放Queue中的元素以及从另一Queue复制元素到这个Queue的任务。复制控制成员用于管理数据成员head和 tail,head和 tail是指向 Queue中首尾元素的指针,这些成员是QueueItem<Type>类型的值。

Queue类实现了几个成员函数：

1）默认构造函数，将head和tail指针置0，指明当前Queue为空。

2）复制构造函数，初始化head和tail，并调用copy_item从它的初始器中复制元素。

3）几个front函数，返回头元素的值。这些函数不进行检查：

4、模板作用域中模板类型的引用

通常，当使用类模板的名字的时候，必须指定模板形参。但是有个例外：在类本身的作用域内部，可以使用类模板的非限定名。例如,在默认构造函数和复制构造函数的声明中,名字Queue是Queue<Type>缩写表示。实质上,编译器推断,当我们引用类的名字时,引用的是同一版本。因此,复制构造函数定义其实等价于:

    //在类中这样写也不会出错
    Queue<Type>(const Queue<Type> &Q):head(0),tail(0)
    {
        copy_elems(Q);
    }

但是编译器会为类中使用的其他模板的模板形参进行这样的推断，因此，在声明伙伴类QueueItem的指针时，必须指定类型形参：

    QueueItem<Type> *head;
    QueueItem<Type> *tail;  //OK

这些声明指出,对于Queue类的给定实例化,head和 tail指向为同一模板形参实例化的QueueItem类型的对象,即,在Queue<int>实例化的内部,head 和 tail的类型是QueueItem<int>*。在 head和 tail成员的定义中省略模板形参将是错误的:

    QueueItem *head;	//Error
    QueueItem *tail;	//Error

//P547 习题16.31
template <typename elemType> class ListItem;
template <typename elemType> class List
{
public:
    List();
    List(const List &);
    List &operator=(const List &);
    ~List();

    void insert(ListItem<elemType> *ptr,elemType value);

    ListItem<elemType> *find(elemType value);

private:
    ListItem<elemType> *front;
    ListItem<elemType> *end;
};

一、类模板成员函数

类模板成员函数的定义具有如下形式：

1、必须以关键字template开头，后接类的模板形参表；

2、必须指出它是哪个类的成员；

3、类名必须包含其模板形参。

如：

template <class Type> ret-type Queue<Type>::member-name

1、destroy函数

template <typename Type>
void Queue<Type>::destroy()
{
    while (!empty())
    {
        pop();
    }
}

2、pop函数

template <typename Type>
void Queue<Type>::pop()
{
    QueueItem<Type> *p = head;
    head = head -> next;
    delete p;
}

  pop函数假设用户不会在空Queue上调用pop。该函数的唯一技巧是：记得保持指向该元素的一个单独指针，以便在重置head指针之后可以删除元素。

3、push函数

template <typename Type>
void Queue<Type>::push(const Type &val)
{
    QueueItem<Type> *pt = new QueueItem<Type>(val);

    if (empty())
    {
        head = tail = pt;
    }
    else
    {
        tail -> next = pt;
        tail = tail -> next;
    }
}

这个函数首先分配新的QueueItem对象，用传递的值初始化它。几点说明：

1）QueueItem构造函数将实参复制到QueueItem对象的 item成员。像标准容器所做的一样,Queue类存储所给元素的副本。

2）如果item为类类型,item的初始化使用item所具有任意类型的复制构造函数。

3）QueueItem构造函数还将next指针初始化为0,以指出该元素没有指向其他QueueItem对象。在Queue的末尾添加元素，将next置0正是我们所希望的。

创建和初始化新元素之后，必须将它链入Queue，如果Queue为空，则head和tail都应该指向这个元素。如果Queue中已经有元素了,则使当前tail元素指向这个新元素。旧的tail不再是最后一个元素了,这也是通过使tail指向新构造的元素指明的。

4、copy_elem函数

该函数的目的就是提供给赋值操作符和复制构造函数使用：

template <typename Type>
void Queue<Type>::copy_elems(const Queue &orig)
{
    //循环进行直至获得orig中最后一个元素之后，pt为0
    for (QueueItem<Type> *pt = orig.head; pt ; pt = pt -> next)
    {
        push(pt -> item);
    }
}

【附：赋值操作符[P551习题16.32]】

template <typename Type>
Queue<Type> &Queue<Type>::operator=(const Queue<Type> &rhs)
{
    destroy();
    copy_elems(rhs);

    return *this;
}

5、模板成员函数的实例化

类模板的成员函数本身也是函数模板。像任何其他函数模板一样，需要使用类模板的成员函数产生该成员的实例化。与其他函数模板不同的是，在实例化类模板成员函数的时候，编译器不执行模板实参推断，相反，类模板成员函数的模板形参由调用该函数的对象的类型确定。例如，当调用Queue<int>类型对象的push成员时，实例化push函数为：

	void Queue<int>::push(const int &val);

对象的模板实参能够确定成员函数模板实参，这一事实意味着，调用类模板成员函数比调用类似函数模板更灵活。用模板形参定义的函数函数形参的实参允许进行常规转换：

template <typename Type>
void f(const Type &);

int main()
{
    Queue<int> qi;
    short s = 42;
    int i = 42;
    qi.push(s);		//调用Queue<int>::push(const int&) 
    qi.push(i);		//调用Queue<int>::push(const int&) 

    f(s);				//调用f(const short&)
    f(i);				//调用f(const int&)
}

6、何时实例化类和成员

类模板的成员函数只有为程序所用才进行初始化。这样，用于实例化模板的类型只需满足实际使用的操作的要求。

定义模板类型的对象时，该定义导致实例化类模板。定义对象也会实例化用于初始化该对象的任一构造函数，以及该构造函数调用的任意成员：

	Queue<string> qs;   //实例化Queue<string> 类和 Queue<int>::Queue()
	qs.push("hello");   //实例化Queue<string>::push

第一个语句实例化Queue类及其默认构造函数,第二个语句实例化push成员函数。

template <typename Type>
void Queue<Type>::push(const Type &val)
{
    QueueItem<Type> *pt = new QueueItem<Type>(val);

    if (empty())
    {
        head = tail = pt;
    }
    else
    {
        tail -> next = pt;
        tail = tail -> next;
    }
}

将依次实例化伙伴类QueueItem<string>及其构造函数。

Queue类中的QueueItem成员是指针。类模板的指针定义不会对类进行初始化，只有用到这样的指针时才会对类进行实例化。因此，在创建Queue对象时不会实例化QueueItem类，相反在使用诸如front、push或pop这样的Queue成员时，才会实例化QueueItem类。