您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ 模板深度實戰：從順序表到鏈表、棧、隊列的泛型容器實現

編輯：關於C++

模板是 C++ 泛型編程的基石，使邏輯代碼與數據類型解耦。本文通過完整實現順序表、鏈表、棧、隊列四大經典容器，展示模板類設計、模板模板參數適配器、類型萃取優化等核心技術。

一、泛型順序表 `SeqList<T>`

動態數組封裝，支持擴容、增刪改查、排序。關鍵點：

_data 指向動態數組，_size/_capacity 追蹤狀態。
CheckCapacity 2倍擴容策略。
TypeTraits 區分 POD 與非 POD 類型，memcpy 加速 POD 拷貝。

// 類型萃取輔助
struct TrueType  { int Get() { return 1; } };
struct FalseType { int Get() { return -1; } };

template<typename T> struct TypeTraits { typedef FalseType IsPodType; };
template<> struct TypeTraits<int>    { typedef TrueType IsPodType; };
template<> struct TypeTraits<double> { typedef TrueType IsPodType; };
template<> struct TypeTraits<char>   { typedef TrueType IsPodType; };

// SeqList 核心片段
template<typename T>
class SeqList {
    T* _data;
    int _size, _capacity;
    void CheckCapacity(int n) { /* 2倍擴容 + 拷貝 */ }
    void Copy(T* dest, T* src, int sz, TrueType)  { memcpy(dest, src, sz*sizeof(T)); }
    void Copy(T* dest, T* src, int sz, FalseType) { for(int i=0;i

二、模板模板參數適配器：棧與隊列
利用 template<template<class> class Container = SeqList> 將底層容器類型參數化，實現「容器適配器」模式。

棧 Stack<T, Container>（基於順序表尾插尾刪 O(1)）
template<typename T, template<class> class Container = SeqList>
class Stack {
    Container<T> _con;
public:
    void Push(const T& v) { _con.PushBack(v); }
    void Pop() { _con.PopBack(); }
    T& Top() { return _con[_con.Size()-1]; }
    bool Empty() { return _con.Size() == 0; }
    void Display() { while(!Empty()) { cout<

隊列 Queue<T, Container>（基於鏈表尾插頭刪 O(1)）
template<typename T, template<class> class Container = LinkList>
class Queue {
    Container<T> _con;
public:
    void Push(const T& v) { _con.PushBack(v); }
    void Pop() { _con.PopFront(); }
    T& Front() { return _con.Front(); }
    T& Back() { return _con.Back(); }
    bool Empty() { return _con.Empty(); }
};

三、泛型雙向鏈表 LinkList<T>
節點結構含 _prev/_next 指針，支持雙向遍歷、頭尾 O(1) 操作、指定位置插入刪除。關鍵實現：

    拷貝構造/賦值採用 Copy-and-Swap（swap(_head, rhs._head)）。
    Insert(pos, val) 區分頭插、尾插、中間插入三種邊界。
    Sort() 採用冒泡排序優化版（記錄最後交換位置縮減範圍）。


template<typename T>
struct Node {
    T _data;
    Node* _next;
    Node* _prev;
    Node(const T& d) : _data(d), _next(nullptr), _prev(nullptr) {}
};

template<typename T>
class LinkList {
    Node* _head;
    Node* _tail;
public:
    void PushBack(const T& d) { /* 尾插，維護 _tail */ }
    void PushFront(const T& d) { /* 頭插，維護 _head */ }
    void Insert(Node* pos, const T& v) { /* pos 後插入 */ }
    void InsertBefore(Node* pos, const T& v) { /* pos 前插入 */ }
    void Remove(const T& v) { /* 找到節點，斷鏈刪除 */ }
    // ... Sort, Display, Size 等
};

四、類型萃取實戰：SeqList::Copy 優化
利用編譯期類型判斷，POD 類型走 memcpy，非 POD 走逐元素拷貝構造/賦值，兼顧性能與正確性。
// 用法示例
string s1[10] = {"abcd", "bcde"};
string s2[10];
Copy(s1, s2, 10); // 自動推導為 FalseType，逐元素拷貝

int a1[10] = {1,2,3};
int a2[10];
Copy(a1, a2, 10); // 自動推導為 TrueType，memcpy 极速拷貝


五、測試驗證
void TestSeqList() {
    SeqList<int> seq;
    seq.PushBack(1); seq.PushBack(2); seq.PushBack(3);
    seq.Insert(1, 99); // 1 99 2 3
    seq.Display();
}

void TestStack() {
    Stack<int> st; // 底層默認 SeqList
    st.Push(1); st.Push(2); st.Push(3);
    st.Display(); // 3 2 1
}

void TestQueue() {
    Queue<int> q; // 底層默認 LinkList
    q.Push(1); q.Push(2); q.Push(3);
    cout << q.Front() << " " << q.Back(); // 1 3
}


六、總結與避坑指南

    模板代碼放頭文件：實現必須可見於調用點，否則鏈接報錯「未定義引用」。
    typename vs class：模板參數列表中通用；依賴類型名稱前必須加 typename（如 typename Container::iterator）。
    模板模板參數語法：template<class> class Container 表示接受單類型參數的模板。
    類型萃取：C++17 可直接用 std::is_trivially_copyable_v 替代手寫 TypeTraits。
    迭代器失效：順序表擴容/插刪會導致指針/引用/迭代器失效，鏈表僅失效被刪除節點的迭代器。

掌握這些模板容器實現，不僅能深入理解 STL 設計哲學，更能在面試與高性能庫開發中遊刃有餘。