C++ Template 之應用 ☆ 電腦 ☆

《前言》

　關於 C++ Template 的基本介紹
　在一般介紹 C++ 完整一點的書（例如：C++ Primer）上都會有
　所以我這邊就不說了
　以下假設讀者對 C++ 的 Class 和 Template 有基本的認識

---

我們先來看一個例子

《例子一》之《版本一》

void AssignItemValue(int Exp, __int64 Co)
{
    if(ItemList.Head==0) { PushBack(Exp, Co); return; }

    _Item* p2 = ItemList.Head;
    if(p2->Exponent < Exp) { ItemList.PushFront(NewItem(Exp, Co)); return; }

    while(p2->Exponent > Exp)
        if(p2->NextItem) p2 = p2->NextItem; else break;

    if(p2->Exponent > Exp)
        PushBack(Exp, Co);
    else if(p2->Exponent == Exp)
        p2->Coefficient = Co;
    else
        ItemList.InsertBefore(NewItem(Exp, Co), p2);
}

void AddItemValue(int Exp, __int64 Co)
{
    if(ItemList.Head==0) { PushBack(Exp, Co); return; }

    _Item* p2 = ItemList.Head;
    if(p2->Exponent < Exp) { ItemList.PushFront(NewItem(Exp, Co)); return; }

    while(p2->Exponent > Exp)
        if(p2->NextItem) p2 = p2->NextItem; else break;

    if(p2->Exponent > Exp)
        PushBack(Exp, Co);
    else if(p2->Exponent == Exp)
        p2->Coefficient += Co;
    else
        ItemList.InsertBefore(NewItem(Exp, Co), p2);
}

兩個函式只有紅色的地方不同
而且還有其它對映 -=, *=, /=, %= 的函式
為了縮短程式碼，並且讓程式容易維護
所以我們可以改成下面的版本

《例子一》之《版本二》

#define LJJ_POLY_Assign 0
#define LJJ_POLY_Add    1
#define LJJ_POLY_Sub    2
#define LJJ_POLY_Mul    3
#define LJJ_POLY_Div    4
#define LJJ_POLY_Mod    5

void _ModifyItemValue(int Exp, __int64 Co, int Func)
{
    if(ItemList.Head==0) { PushBack(Exp, Co); return; }

    _Item* p2 = ItemList.Head;
    if(p2->Exponent < Exp) { ItemList.PushFront(NewItem(Exp, Co)); return; }

    while(p2->Exponent > Exp)
        if(p2->NextItem) p2 = p2->NextItem; else break;

    if(p2->Exponent > Exp)
        PushBack(Exp, Co);
    else if(p2->Exponent == Exp)
        switch(Func)
        case LJJ_POLY_Assign:
            p2->Coefficient = Co;
            break;
        case LJJ_POLY_Add:
            p2->Coefficient += Co;
            break;
        case LJJ_POLY_Sub:
            p2->Coefficient -= Co;
            break;
        case LJJ_POLY_Mul:
            p2->Coefficient *= Co;
            break;
        case LJJ_POLY_Div:
            p2->Coefficient /= Co;
            break;
        case LJJ_POLY_Mod:
            p2->Coefficient %= Co;
            break;
    else
        ItemList.InsertBefore(NewItem(Exp, Co), p2);
}

void AssignItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Assign); }
void AddItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Add); }
void SubItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Sub); }
void MulItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Mul); }
void DivItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Div); }
void ModItemValue(int Exp, __int64 Co) { _ModifyItemValue(Exp, Co, LJJ_POLY_Mod); }

但是《版本二》也有一些缺點
例如 switch 要先寫好，擴充性較差
另外就是會有速度上的損失
我們再看下面的例子就更明顯了

《例子二》之《版本一》

void Copy(const Polynomial& B)
{
    _Item* p1 = B.ItemList.Head;
    if(p1==0) { ItemList.Reset(); return; }

    while(p1)
    {
        PushBack(p1->Exponent, p1->Coefficient);
        p1 = p1->NextItem;
    }
}

void InverseCopy(const Polynomial& B)
{
    _Item* p1 = B.ItemList.Head;
    if(p1==0) { ItemList.Reset(); return; }

    while(p1)
    {
        PushBack(p1->Exponent, -p1->Coefficient);
        p1 = p1->NextItem;
    }
}

Polynomial& Polynomial::operator+= (const Polynomial &B)
{
    if(ItemList.Head == 0) { Copy(B); return *this; }
    if(B.ItemList.Head == 0) return *this;

    _Item* pa = ItemList.Head;
    _Item* pb = B.ItemList.Head;

    while(pa && pb)
    {
        if(pa->Exponent > pb->Exponent) { pa = pa->NextItem; }
        else if(pa->Exponent < pb->Exponent)
        {
            ItemList.InsertBefore(NewItem(pb->Exponent, pb->Coefficient), pa);
            pb = pb->NextItem;
        }
        else
        {
            pa->Coefficient += pb->Coefficient;
            if(pa->Coefficient) { pa = pa->NextItem; pb = pb->NextItem; }
            else
            {
                _Item* NextItem = pa->NextItem;
                ItemList.Separate(pa);
                FreeItemList.PushBack(pa);
                pa = NextItem;
                pb = pb->NextItem;
            }
        }
    }

    if(pa) return *this;

    while(pb) { PushBack(pb->Exponent, pb->Coefficient); pb = pb->NextItem; }
    return *this;
}

Polynomial& Polynomial::operator-= (const Polynomial &B)
{
    if(ItemList.Head == 0) { InverseCopy(B); return *this; }
    if(B.ItemList.Head == 0) return *this;

    _Item* pa = ItemList.Head;
    _Item* pb = B.ItemList.Head;

    while(pa && pb)
    {
        if(pa->Exponent > pb->Exponent) { pa = pa->NextItem; }
        else if(pa->Exponent < pb->Exponent)
        {
            ItemList.InsertBefore(NewItem(pb->Exponent, -pb->Coefficient), pa);
            pb = pb->NextItem;
        }
        else
        {
            pa->Coefficient -= pb->Coefficient;
            if(pa->Coefficient) { pa = pa->NextItem; pb = pb->NextItem; }
            else
            {
                _Item* NextItem = pa->NextItem;
                ItemList.Separate(pa);
                FreeItemList.PushBack(pa);
                pa = NextItem;
                pb = pb->NextItem;
            }
        }
    }

    if(pa) return *this;

    while(pb) { PushBack(pb->Exponent, -pb->Coefficient); pb = pb->NextItem; }
    return *this;
}

在《例子二》中有四個地方不一樣，可是都只差一點點
如果全部改成 switch 或 if，對速度的影響會很大
這時候我們可以用 Template 改成以下的樣子

《例子二》之《版本二》

class LJJ_Add
{
public:
    static Coef_Type Action1(const Coef_Type &a) { return a; }
    static void Action2(Coef_Type &a, const Coef_Type &b) { a += b; }
    static Coef_Type Action3(const Coef_Type &a, const Coef_Type &b) { return a + b; }
};

class LJJ_Sub
{
public:
    static Coef_Type Action1(const Coef_Type &a) { return -a; }
    static void Action2(Coef_Type &a, const Coef_Type &b) { a -= b; }
    static Coef_Type Action3(const Coef_Type &a, const Coef_Type &b) { return a - b; }
};

template<typename Func>
void _Copy(const Polynomial& B)
{
    _Item* p1 = B.ItemList.Head;

    if(p1==0)
        ItemList.Reset();
    else
        while(p1)
        {
            PushBack(p1->Exponent, Func::Action1(p1->Coefficient));
            p1 = p1->NextItem;
        }
}
void Copy(const Polynomial& B) { _Copy<LJJ_Add>(B); }
void InverseCopy(const Polynomial& B) { _Copy<LJJ_Sub>(B); }

template<typename Func>
void _Polynomial_operator_Add_Sub_Equal_Polynomial (const Polynomial &B)
{
    if(ItemList.Head == 0) { _Copy<Func>(B); return; }
    if(B.ItemList.Head == 0) return;

    _Item* pa = ItemList.Head;
    _Item* pb = B.ItemList.Head;

    while(pa && pb)
    {
        if(pa->Exponent > pb->Exponent) { pa = pa->NextItem; }
        else if(pa->Exponent < pb->Exponent)
        {
            ItemList.InsertBefore(NewItem(pb->Exponent, Func::Action1(pb->Coefficient)), pa);
            pb = pb->NextItem;
        }
        else
        {
            Func::Action2(pa->Coefficient, pb->Coefficient);
            if(pa->Coefficient) { pa = pa->NextItem; pb = pb->NextItem; }
            else
            {
                _Item* NextItem = pa->NextItem;
                ItemList.Separate(pa);
                FreeItemList.PushBack(pa);
                pa = NextItem;
                pb = pb->NextItem;
            }
        }
    }

    if(pa) return;

    while(pb) { PushBack(pb->Exponent, Func::Action1(pb->Coefficient)); pb = pb->NextItem; }
    return;
}

Polynomial& Polynomial::operator+= (const Polynomial &B)
{ _Polynomial_operator_Add_Sub_Equal_Polynomial<LJJ_Add>(B); return *this; }

Polynomial& Polynomial::operator-= (const Polynomial &B)
{ _Polynomial_operator_Add_Sub_Equal_Polynomial<LJJ_Sub>(B); return *this; }

而且這樣做還可以有別的邊際效應 (參考以下的《例子三》)
整體來說，使用 Template 對於縮短程式碼以及簡化維護是很有幫助的

《例子三》

template<typename Func>
Polynomial _Polynomial_Add_Sub_Coefficient (const Polynomial &A, const Coef_Type &b)
{
    Polynomial Result = A;
    if(Result.ItemList.Tail->Exponent)
        Result.PushBack(0, b);
    else
        Func::Action2(Result.ItemList.Tail->Coefficient, b);
    return Result;
}

Polynomial operator+ (const Polynomial &A, const Coef_Type &b)
{ return _Polynomial_Add_Sub_Coefficient<LJJ_Add>(A, b); }

Polynomial operator- (const Polynomial &A, const Coef_Type &b)
{ return _Polynomial_Add_Sub_Coefficient<LJJ_Sub>(A, b); }

template<typename Func>
inline Polynomial _Polynomial_Add_Sub_Polynomial (const Polynomial &A, const Polynomial &B)
{
    Polynomial Result;

    _Item* pa = A.ItemList.Head;
    _Item* pb = B.ItemList.Head;

    while(pa && pb)
    {
        if(pa->Exponent > pb->Exponent) { Result.PushBack(pa); pa = pa->NextItem; }
        else if(pa->Exponent < pb->Exponent)
        {
            Result.PushBack(pb->Exponent, Func::Action1(pb->Coefficient)); pb = pb->NextItem;
        }
        else
        {
            Coef_Type c = Func::Action3(pa->Coefficient, pb->Coefficient);
            if(c) Result.PushBack(pa->Exponent, c);
            pa = pa->NextItem;
            pb = pb->NextItem;
        }
    }

    while(pa) { Result.PushBack(pa); pa = pa->NextItem; }
    while(pb) { Result.PushBack(pb); pb = pb->NextItem; }
    return Result;
}

Polynomial operator+ (const Polynomial &A, const Polynomial &B)
{ return _Polynomial_Add_Sub_Polynomial<LJJ_Add>(A, B); }

Polynomial operator- (const Polynomial &A, const Polynomial &B)
{ return _Polynomial_Add_Sub_Polynomial<LJJ_Sub>(A, B); }

以下是《例子一》的 Template 版

《例子一》之《版本三》

class LJJ_POLY_Assign
{ public: static void Action(_Item* &p2, Coef_Type &Co) { p2->Coefficient = Co; } };
class LJJ_POLY_Add {public:static void Action(_Item* &p2, Coef_Type &Co) {p2->Coefficient += Co;}};
class LJJ_POLY_Sub {public:static void Action(_Item* &p2, Coef_Type &Co) {p2->Coefficient -= Co;}};
class LJJ_POLY_Mul {public:static void Action(_Item* &p2, Coef_Type &Co) {p2->Coefficient *= Co;}};
class LJJ_POLY_Div {public:static void Action(_Item* &p2, Coef_Type &Co) {p2->Coefficient /= Co;}};
class LJJ_POLY_Mod {public:static void Action(_Item* &p2, Coef_Type &Co) {p2->Coefficient %= Co;}};
    
template <typename Func>
void _ModifyItemValue(Expo_Type Exp, Coef_Type Co)
{
    if(ItemList.Head==0) { PushBack(Exp, Co); return; }

    _Item* p2 = ItemList.Head;
    if(p2->Exponent < Exp) { ItemList.PushFront(NewItem(Exp, Co)); return; }

    while(p2->Exponent > Exp)
        if(p2->NextItem) p2 = p2->NextItem; else break;

    if(p2->Exponent > Exp)
        PushBack(Exp, Co);
    else if(p2->Exponent == Exp)
        Func::Action(p2, Co);
    else
        ItemList.InsertBefore(NewItem(Exp, Co), p2);
}

void AssignItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Assign>(Exp, Co); }
void AddItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Add>(Exp, Co); }
void SubItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Sub>(Exp, Co); }
void MulItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Mul>(Exp, Co); }
void DivItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Div>(Exp, Co); }
void ModItemValue(Expo_Type Exp, Coef_Type Co) { _ModifyItemValue<LJJ_POLY_Mod>(Exp, Co); }

---

ps. 後來發現像 LJJ_POLY_Add、LJJ_POLY_Sub、LJJ_POLY_Mul、… 這些類別
　　在 C++ 中有一個專門的術語叫作 Policy Class (策略類別)
　　另外還有一個相關的技巧叫作 Traits (特徵萃取)
　　看看以後是否有機會再作說明
　　(2008/4/20)

回首頁　　　　　回目錄