C++模板類：實現通用數據結構和演算法

一、模板類的概念

模板是C++中的一種特殊的數據類型，可以將類型作為參數進行操作。模板類是使用模板創建的，提供了一種通用的數據結構和演算法的實現方式。模板類的定義一般包括模板參數列表、類的定義和成員函數實現。

template 
class Stack {
  private:
    int top;
    T data[100];
  public:
    Stack() { top = -1; }
    void push(T val) { data[++top] = val; }
    T pop() { return data[top--]; }
};

上面的代碼定義了一個名為Stack的模板類，它使用一個類型T作為數據類型參數來創建一個通用的棧數據結構。在類定義中，我們使用了類型T定義了一個名為data的數組來保存棧的數據項，以及一個整數top作為棧的頂部指針，表示棧中最後一個入棧的數據項的下標。

二、模板類的使用

使用模板類時，需要在類名後跟上一對尖括弧，尖括弧中包含對應的數據類型。例如，要使用上面定義的Stack模板類作為一個保存int類型的棧，可以這樣定義:

Stack<int> intStack;

上面的代碼創建了一個名為intStack的Stack對象，它的底層數據類型被指定為int。

要壓入一個整數值，比如42，可以調用對象的push函數：

intStack.push(42);

要彈出一個數據項，可以調用對象的pop函數：

int x = intStack.pop();

這會返回42，並將棧頂的指針下移一位。

同樣地，如果要創建一個保存double類型的棧，可以這樣定義：

Stack<double> doubleStack;

使用具有不同數據類型模板類對象的代碼可以共享相同的代碼基礎，而不必更改該代碼的每個實例來適應各種數據類型。

三、自定義演算法和數據結構實現

模板類非常適合用於自定義的演算法和數據結構實現，這些實現可以用於各種類型的數據。例如，下面的代碼展示了如何使用堆排序演算法來對任意類型的數組進行排序：

template <typename T, int size>
class Array {
  private:
    T data[size];
  public:
    Array(const T arr[]) {
        for (int i = 0; i < size; ++i) {
            data[i] = arr[i];
        }
    }
    void heapSort() {
        buildHeap(data, size);
        for (int i = size - 1; i > 0; --i) {
            std::swap(data[0], data[i]);
            siftDown(data, 0, i);
        }
    };
    // 具體的堆排序演算法實現略去
};

這裡的Array類是使用模板創建的，它還包括一個大小為size的data數組，以及一個從data數組中構造新Array對象的構造函數。heapSort函數使用數組中的元素實現堆排序演算法，並將排序結果存儲在原始的data數組中。

要使用上面的代碼來排序一個int類型的數組，可以這樣定義：

int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
Array<int, sizeof(arr)/sizeof(int)> intArr(arr);
intArr.heapSort();

要將一個自定義類型的數組用自定義的排序演算法進行排序，只需要將T替換為該自定義類型即可：

class Person {
  public:
    std::string name;
    int age;
    // 具體的成員和構造函數略去
};
bool operator<(const Person &a, const Person &b) {
    return a.age < b.age;
}
Person arr[] = {{"Alice", 20}, {"Bob", 18}, {"Charlie", 25}};
Array<Person, sizeof(arr)/sizeof(Person)> personArr(arr);
personArr.heapSort();

在這個例子中，我們對一個保存Person對象的數組進行了堆排序，並根據每個對象的年齡屬性進行了排序。

四、模板特化

特化是C++中的一種機制，用於為特定的數據類型提供特殊的模板類實現。例如，在上面的Stack模板類中，我們可能想要為特定類型提供一個特殊的實現，可能不同於默認實現。這可以通過使用模板特化來實現。

特化是一種使用template<>結構創建的，用於定義全局函數或類模板的專門版本，它具有與標準定義不同的實現。這個具體版本可以是關於T類型的完全特定版本，也可以是與默認定義相同但在某些方面重載某些方法的泛化版本。

例如，我們可以創建一個特化的Stack模板類版本來處理字元數組：

template <>
class Stack<char*> {
  private:
    int top;
    char* data[100];
  public:
    Stack() { top = -1; }
    void push(char* val) { data[++top] = val; }
    char* pop() { return data[top--]; }
};

這是Stack模板類的特化版本，它使用一個指向字元數組char*的指針作為棧中的元素類型。特化版本的push和pop方法實現與普通版本不同。

要使用上面的代碼來創建一個保存char*類型的棧，可以這樣實現：

Stack<char*> charStack;
charStack.push("Hello");
charStack.push("World");
char* str = charStack.pop(); // str = "World"

五、模板類的限制

C++模板類提供了通用的數據結構和演算法實現，但有一些限制需要注意。

首先，模板類實現的所有方法必須包含在頭文件中。由於C++編譯器在編譯時需要知道模板類的實現，因此不能將實現放在單獨的源文件中。

其次，模板類不能被導出為動態庫。由於編譯器需要在編譯時將模板類的實現全部解析為彙編代碼，因此在動態鏈接時會出現問題。解決方案是將模板類和使用模板類的代碼一起編譯成可執行文件，這並不影響程序的性能。

最後，模板類不支持部分特化。這意味著，如果我們想用它將一個特定的數據類型映射到模板類的參數，則必須保證在映射過程中不丟失任何信息，因為這是唯一的選擇。

六、結論

通過使用C++模板類，我們可以實現通用的數據結構和演算法，這些實現可以適用於各種類型的數據。模板類的定義包括模板參數列表、類的定義和成員函數實現，使用時需要在類名後跟上尖括弧中包含的數據類型。我們還可以通過模板特化為特定類型提供特殊的實現。