6、以template进行编程

1、类型限定

为class template定义一个inline函数，做法就像为non-template class定义一个inline函数一样;类似empty（）函数。但是在类体外，class template member function的定义语法却不一样。

template <typename elemType>
class BinaryTree {
public:
    BinaryTree();
	BinaryTree( const vector< elemType >& );
    BinaryTree( const BinaryTree& );
    ~BinaryTree();
    BinaryTree& operator=( const BinaryTree& );

	void insert( const vector< elemType >& );
    void insert( const elemType& );
    void remove( const elemType& );
    void clear(){ clear( _root ); _root = 0; }  // remove entire tree ...

	bool empty() { return _root == 0; }

	void inorder( ostream &os = *_current_os )   const { _root->inorder( _root, os ); }
    void postorder( ostream &os = *_current_os ) const { _root->postorder( _root, os ); }
    void preorder( ostream &os = *_current_os )  const { _root->preorder( _root, os ); }

    bool find( const elemType& ) const;
    ostream& print( ostream &os = *_current_os,
                    void (BinaryTree<elemType>::*traversal)( ostream& ) const =
                          &BinaryTree<elemType>::inorder ) const;

	static void current_os( ostream *os ){ if ( os ) _current_os = os;   }
	static ostream* os() { return _current_os; }

private:
	 BTnode<elemType> *_root;
	 static ostream   *_current_os; 

     // copy a subtree addressed by src to tar
     void copy( BTnode<elemType>*&tar, BTnode<elemType>*src );
     void clear( BTnode<elemType>* );
	 void remove_root(); 
};

template <typename elemType>
ostream *BinaryTree<elemType>::_current_os = &cout;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

template <typename elemType>
inline  BinaryTree<elemType>:: 
BinaryTree()
    : _root( 0 ){}
1
2
3
4

为什么第二次出现BinaryTree名称就不需要限定了呢？因为在class cope 运算符出现之后：
BinaryTree::
其后所有东西都视为位于class定义范围内，当我们写：

BinaryTree:: //在class定义范围之外
BinaryTree() //在class定义范围之内

第二次出现BinaryTree名称就便被视为class定义范围之内，就不需要限定。

2、template类参数的处理

建议将所有的template参数类型视为class类型来处理，意味着我们会把它声明为一个const reference，而非以by value方式传递。

方式1

//针对构造函数的参数类型，初始化列表进行初始化
template <typename valType>
inline BTnode<valType>::
BTnode( const valType &val )
    : _val( val )//将valType视为某种class类型
{ 
	_cnt = 1;
	_lchild = _rchild = 0; 
}
1
2
3
4
5
6
7
8
9

方式2

//针对构造函数的参数类型，初始化列表进行初始化
template <typename valType>
inline BTnode<valType>::
BTnode( const valType &val )
    
{ 
	_val=val ;//不建议这样做，因为它是某种class类型

//内置类型 它们的类型不会改变
	_cnt = 1;
	_lchild = _rchild = 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12

如果在下面这种情况，以上两种方式无差异

BTnode<int> btni(42);
1

但是如下这种就有差异了

BTnode<Matrix> btnm(transform_matrix);
1

因为构造函数体内_val的赋值操作可以分解为两个步骤：（1）函数体执行前，Matrix的默认构造函数会先作用于_val身上；（2）函数体内会以copy assignment opreator 将val复制给_val。但如果我们采用上述的方式1，在构造函数的成员初始化列表中将_val 初始化，那么只需要一个步骤就能完成工作：以拷贝构造函数将val复制给_val。

我们将prev声明为指针的引用（reference to pointer）,我们不但可以改变指针本身，也可以改变由此指针指向的对象。

template <typename valType>
void 
BTnode<valType>::
remove_value( const valType &val, BTnode *&prev ) 
{
    if ( val < _val )
    {
         if ( ! _lchild )
              return; // not present
         else _lchild->remove_value( val, _lchild );
    } 
    else 
    if ( val > _val )
    {
         if ( ! _rchild )
              return; // not present
         else _rchild->remove_value( val, _rchild );
    } 
    else 
    { // ok: found it
      // reset the tree then delete this node
      if ( _rchild ) 
      {
         prev = _rchild;
         if ( _lchild )
			  if ( ! prev->_lchild )
				   prev->_lchild = _lchild;
			  else BTnode<valType>::lchild_leaf( _lchild, prev->_lchild );
      }
      else prev = _lchild;
      delete this;
    }         
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

全局作用域（global scope）内的函数及对象，其地址也是一种常量表达式，因此也可以被拿来表达这一形式的参数。例如，以下是一个接受函数指针作为参数的数列类：

#include <iostream>
#include<vector>

using namespace std;

template<void (*pf) (int pos,vector<int> &seq)>
class numeric_sequence{
public:
    numeric_sequence(int len,int beg_pos =1){
        if(!pf)//判断是否为null
            return;
        _len=len>0?len:1;
        _beg_pos= beg_pos >0?beg_pos:1;
        
        pf(beg_pos+len-1,_elems);
            
    }
private:
    int _len;
    int _beg_pos;
    vector<int > _elems;    
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

练习6.1

修改以下类，使它成为一个class template

class example{
public:
    example(double min,double max);
    example(const double *array,int size);
    double & operator[](int index);
    bool operator==(const example &) const;
    bool insert(const double *,int);
    bool insert(double);
    double min() const {return _min;}    
    double max() const {return _max;}
    void min (double);    
    void max (double);  
    int count(double value) const;
private:
    int size;
    double * parray;
    double _min;
    double _max;    
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

修改后

template<typename elemType>
class example{
public:
    example(const elemType min,const elemType max);
    example(const elemType *array,int size);
    double & operator[](int index);
    bool operator==(const example &) const;
    bool insert(const elemType *,int);
    bool insert(const elemType);
    double min() const {return _min;}    
    double max() const {return _max;}
    void min (const elemType);    
    void max (const elemType);  
    int count(const elemType value) const;
private:
    int size;
    elemType * parray;
    elemType _min;
    elemType _max;    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

练习6.2
重新以template形式实现练习4.3的Matrix class,并扩充其功能，使它能够通过heap memory（堆内存）来支持任意行列大小。分配/释放内存的操作，请在constructor/destructor中进行。

matrix.h

#ifndef MATRIX_H
#define MATRIX_H
#include<iostream>

#include<ostream>
template <typename elemType>


class Matrix
{
    friend Matrix<elemType>
    operator+(const Matrix<elemType>&,const Matrix<elemType>&);
    friend Matrix<elemType>
    operator*(const Matrix<elemType>&,const Matrix<elemType>&);


public:
    Matrix(int row,int columns);
    Matrix(const Matrix&);
    ~Matrix();
    Matrix& operator=(const Matrix&);

    void operator+=(const Matrix&);
    elemType operator()(int row,int column){return _matrix[row*cols()+column];}

    const elemType operator()(int row,int column)const
    {return _matrix[row*cols()+column];}


    int rows() const {return _rows;}
    int cols() const {return _cols;}

    bool same_size(const Matrix& m) const{
        return rows()==m.rows()&&cols()==m.cols();
    }
    bool comfortable(const Matrix& m) const{
        return (cols()==m.rows());
    }
    ostream & print (ostream&) const;

protected:
    int _rows;
    int _cols;
elemType *_matrix;

};
template<typename elemType>
inline ostream& operator<<(ostream& os,const Matrix<elemType> &m)
{
    return m.print(os);
}


#endif // MATRIX_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

matrix.cpp

#include "matrix.h"

template <typename elemType>
Matrix<elemType>
operator+(const Matrix<elemType>&m1,const Matrix<elemType>&m2){
    //确定m1和m2的大小相同
    Matrix<elemType> result(m1);
              result+=m2;
              return   result;
}

template <typename elemType>
 Matrix<elemType>
 operator*(const Matrix<elemType>&m1,const Matrix<elemType>&m2){
     //m1的行数（row）必须等于m2的列数（column）
     Matrix<elemType> result(m1.rows(),m2.cols());
     for (int ix=0;ix<m1.rows();ix++) {
         for (int jx=0;jx<m1.cols();jx++) {
             result(ix,jx)=0;
             for (int kx=0;kx<m1.cols();kx++) {
                 result(ix,jx)+= m1(ix,kx)+m2(kx,jx);
             }
         }
     }
     return  result;
 }

 template <typename elemType>
 void Matrix<elemType>::operator+=(const Matrix&m){
     int matrix_size=cols()*rows();
     for (int ix=0;ix<matrix_size;++ix) {
         (*(_matrix+ix))+=(*(m._matrix+ix));
     }
 }
template <typename elemType>
ostream& Matrix<elemType>::print(ostream &os) const{
    int col=cols();
     int matrix_size=cols()*rows();
     for (int ix=0;ix<matrix_size;++ix) {
         if(ix%col==0)os<<endl;
         os<<(*(_matrix+ix))<<' ';
     }
     os<<endl;
     return os;
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46