C++中的list模擬實(shí)現(xiàn)解讀

更新時(shí)間：2025年09月18日 09:02:01 作者：一枝小雨

文章詳解C++ list模擬實(shí)現(xiàn),采用雙向循環(huán)鏈表結(jié)構(gòu),通過迭代器封裝與運(yùn)算符重載實(shí)現(xiàn)容器功能,涵蓋構(gòu)造、拷貝、內(nèi)存管理及異常安全等關(guān)鍵點(diǎn),并討論了測試與改進(jìn)方向,如移動(dòng)語義和STL兼容性

list 模擬實(shí)現(xiàn)詳解

1. 基本框架與節(jié)點(diǎn)結(jié)構(gòu)

list的底層實(shí)現(xiàn)通常采用帶頭雙向循環(huán)鏈表，每個(gè)節(jié)點(diǎn)包含指向前后節(jié)點(diǎn)的指針和數(shù)據(jù)域。

namespace practice_list
{
    template<class T>
    struct __list_node
    {
        __list_node<T>* _next;    // 指向下一個(gè)節(jié)點(diǎn)的指針
        __list_node<T>* _prev;    // 指向前一個(gè)節(jié)點(diǎn)的指針
        T _data;                  // 存儲(chǔ)的數(shù)據(jù)

        // 節(jié)點(diǎn)構(gòu)造函數(shù)，使用默認(rèn)參數(shù)初始化
        __list_node(const T& x = T())
            : _data(x)           // 初始化數(shù)據(jù)域
            , _next(nullptr)     // 初始化next指針
            , _prev(nullptr)     // 初始化prev指針
        {}
    };
}

關(guān)鍵點(diǎn)說明：

使用模板類實(shí)現(xiàn)泛型編程，支持任何數(shù)據(jù)類型
節(jié)點(diǎn)包含前后指針，實(shí)現(xiàn)雙向鏈表結(jié)構(gòu)
構(gòu)造函數(shù)使用默認(rèn)參數(shù)，方便創(chuàng)建頭節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)

2. 迭代器初步實(shí)現(xiàn)

迭代器是讓鏈表能夠像容器一樣被遍歷的關(guān)鍵，它封裝了節(jié)點(diǎn)指針并重載了相關(guān)運(yùn)算符。

2.1 簡單迭代器實(shí)現(xiàn)

template<class T>
struct __list_iterator
{
    typedef __list_node<T> Node;
    Node* _node;  // 封裝節(jié)點(diǎn)指針

    // 構(gòu)造函數(shù)，通過節(jié)點(diǎn)指針初始化迭代器
    __list_iterator(Node* node)
        :_node(node)
    {}

    // 解引用操作符重載，返回節(jié)點(diǎn)數(shù)據(jù)的引用
    T& operator*()
    {
        return _node->_data;
    }

    // 前置++操作符重載，移動(dòng)到下一個(gè)節(jié)點(diǎn)
    __list_iterator<T>& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    // 不等于操作符重載，用于比較兩個(gè)迭代器
    bool operator!=(const __list_iterator<T>& it)
    {
        return _node != it._node;
    }
};

關(guān)鍵點(diǎn)說明：

迭代器本質(zhì)上是對(duì)節(jié)點(diǎn)指針的封裝
通過重載運(yùn)算符實(shí)現(xiàn)指針-like的行為
operator*返回?cái)?shù)據(jù)引用，使我們可以通過迭代器修改數(shù)據(jù)
operator++讓迭代器移動(dòng)到下一個(gè)節(jié)點(diǎn)
operator!=用于比較迭代器是否指向相同節(jié)點(diǎn)

3. 基礎(chǔ)list類實(shí)現(xiàn)

3.1 類定義與迭代器類型聲明

template<class T>
class list
{
    typedef __list_node<T> Node;
public:
    // 聲明迭代器類型
    typedef __list_iterator<T> iterator;
    
    // 獲取指向第一個(gè)元素的迭代器
    iterator begin()
    {
        return iterator(_head->_next);  // 匿名對(duì)象寫法
    }
    
    // 獲取尾后迭代器（指向頭節(jié)點(diǎn)）
    iterator end()
    {
        return iterator(_head);  // 匿名對(duì)象寫法
    }
    
    // 構(gòu)造函數(shù)，初始化帶頭雙向循環(huán)鏈表
    list()
    {
        _head = new Node;      // 創(chuàng)建頭節(jié)點(diǎn)
        _head->_next = _head;  // 頭節(jié)點(diǎn)的next指向自己
        _head->_prev = _head;  // 頭節(jié)點(diǎn)的prev指向自己
    }
    
    // 尾插函數(shù)
    void push_back(const T& x)
    {
        Node* tail = _head->_prev;  // 找到當(dāng)前尾節(jié)點(diǎn)
        Node* newnode = new Node(x); // 創(chuàng)建新節(jié)點(diǎn)
        
        // 鏈接新節(jié)點(diǎn)與前一個(gè)節(jié)點(diǎn)（尾節(jié)點(diǎn)）
        tail->_next = newnode;
        newnode->_prev = tail;
        
        // 鏈接新節(jié)點(diǎn)與后一個(gè)節(jié)點(diǎn)（頭節(jié)點(diǎn)）
        newnode->_next = _head;
        _head->_prev = newnode;
    }

private:
    Node* _head;  // 頭節(jié)點(diǎn)指針
};

關(guān)鍵點(diǎn)說明：

list類維護(hù)一個(gè)頭節(jié)點(diǎn)指針_head
begin()返回第一個(gè)有效元素的迭代器（頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）
end()返回尾后迭代器（指向頭節(jié)點(diǎn)本身）
構(gòu)造函數(shù)初始化一個(gè)空鏈表，頭節(jié)點(diǎn)指向自己
push_back()在鏈表尾部插入新節(jié)點(diǎn)

3.2 測試函數(shù)

void test_list1()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

4. 完整迭代器實(shí)現(xiàn)

更完整的迭代器實(shí)現(xiàn)需要考慮const迭代器、前后移動(dòng)等功能。

4.1 進(jìn)階迭代器設(shè)計(jì)

// 使用三個(gè)模板參數(shù)支持普通迭代器和const迭代器
// T: 數(shù)據(jù)類型, Ref: 引用類型, Ptr: 指針類型
template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef __list_node<T> Node;
    typedef __list_iterator<T, Ref, Ptr> Self;  // 自身類型別名
    Node* _node;

    __list_iterator(Node* node)
        :_node(node)
    {}

    // 解引用操作符，返回Ref類型（T&或const T&）
    Ref operator*()
    {
        return _node->_data;
    }

    // 前置++
    Self& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    // 后置++（int參數(shù)用于區(qū)分前置和后置）
    Self operator++(int)
    {
        Self ret = _node;  // 保存當(dāng)前狀態(tài)
        ++(*this);         // 調(diào)用前置++
        return ret;        // 返回之前保存的狀態(tài)
    }

    // 前置--
    Self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    // 后置--
    Self operator--(int)
    {
        Self ret = _node;
        --(*this);
        return ret;
    }

    // 不等于操作符
    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }

    // 等于操作符
    bool operator==(const Self& it)
    {
        return !(_node != it._node);
    }

    // 箭頭操作符，用于訪問成員
    Ptr operator->()
    {
        return &(_node->_data);
    }
};

關(guān)鍵點(diǎn)說明：

使用三個(gè)模板參數(shù)實(shí)現(xiàn)普通迭代器和const迭代器的統(tǒng)一實(shí)現(xiàn)
添加了前后移動(dòng)操作（++和--的前置和后置版本）
實(shí)現(xiàn)了箭頭操作符，用于直接訪問成員變量
使用Self類型別名簡化代碼編寫

5. 完整list類實(shí)現(xiàn)

5.1 類型定義與構(gòu)造函數(shù)

template<class T>
class list
{
    typedef __list_node<T> Node;
private:
    Node* _head;  // 頭節(jié)點(diǎn)指針
    
public:
    // 普通迭代器類型
    typedef __list_iterator<T, T&, T*> iterator;
    // const迭代器類型
    typedef __list_iterator<T, const T&, const T*> const_iterator;

    // 構(gòu)造函數(shù)
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    
    // 析構(gòu)函數(shù)
    ~list(){
        clear();     // 清空所有節(jié)點(diǎn)
        delete _head;        // 刪除頭節(jié)點(diǎn)
        _head = nullptr;
    }
    
    // 獲取起始迭代器
    iterator begin()
    {
        return iterator(_head->_next);
    }
    
    // 獲取尾后迭代器
    iterator end()
    {
        return iterator(_head);
    }
    
    // 獲取const起始迭代器
    const_iterator begin() const
    {
        return const_iterator(_head->_next);
    }
    
    // 獲取const尾后迭代器
    const_iterator end() const
    {
        return const_iterator(_head);
    }

5.2 拷貝構(gòu)造與賦值重載

    // 拷貝構(gòu)造函數(shù)
    list(const list<T>& lt)
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        
        // 遍歷源鏈表，插入數(shù)據(jù)
        const_iterator it = lt.begin();
        while (it != lt.end())
        {
            push_back(*it);
            ++it;
        }
        
        // 使用范圍for，更簡潔
        /*for (auto e : lt)
        {
                push_back(*it);
        }*/
    }
    
    /* 賦值重載 */
    /*list<T>& operator=(const list<T>& lt)
    {
            if (this != &lt)
            {
                    clear();
                    for (auto e : lt)
                    {
                            push_back(e);
                    }
            }
            else
                    return *this;
    }*/
    // 賦值運(yùn)算符（簡潔寫法）
    list<T>& operator=(list<T> lt)  // 傳參調(diào)用拷貝構(gòu)造
    {
        swap(_head, lt._head);  // 交換頭指針
        return *this;           // 返回當(dāng)前對(duì)象
    }

5.3 元素訪問與修改函數(shù)

    // 尾插
    void push_back(const T& x)
    {
        /*
        Node* tail = _head->_prev;
        Node* newnode = new Node(x);
        // 鏈接newnode與newnode前一個(gè)節(jié)點(diǎn)tail
        tail->_next = newnode;
        newnode->_prev = tail;
        // 鏈接newnode與newnod后一個(gè)節(jié)點(diǎn)"頭節(jié)點(diǎn)"
        newnode->_next = _head;
        _head->_prev = newnode;
        */
        
        insert(end(), x);  // 在end()前插入
    }
    
    // 尾刪
    void pop_back()
    {
        /*Node* tail = _head->_prev;
        Node* newtail = tail->_prev;
        delete[] tail;
        _head->_prev = newtail;
        newtail->_next = _head;*/

        erase(--end());
        // erase(iterator(_head->_prev)); 這種寫法也可以
    }
    
    // 頭插
    void push_front(const T& x)
    {
        insert(begin(), x);  // 在begin()前插入
    }
    
    // 頭刪
    void pop_front()
    {
        erase(begin());  // 刪除第一個(gè)元素
    }
    
    // 在指定位置前插入
    void insert(iterator pos, const T& x)
    {
        Node* cur = pos._node;    // 當(dāng)前節(jié)點(diǎn)
        Node* prev = cur->_prev;  // 前一個(gè)節(jié)點(diǎn)
        Node* newnode = new Node(x);  // 新節(jié)點(diǎn)
        
        // 鏈接新節(jié)點(diǎn)與前一個(gè)節(jié)點(diǎn)
        prev->_next = newnode;
        newnode->_prev = prev;
        
        // 鏈接新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)
        newnode->_next = cur;
        cur->_prev = newnode;
    }
    
    // 刪除指定位置元素
    void erase(iterator pos)
    {
        assert(pos != end());  // 不能刪除頭節(jié)點(diǎn)
        
        Node* cur = pos._node;
        Node* next = cur->_next;
        Node* prev = cur->_prev;
        
        delete cur;  // 釋放節(jié)點(diǎn)內(nèi)存
        
        // 重新鏈接前后節(jié)點(diǎn)
        next->_prev = prev;
        prev->_next = next;
    }
    
    // 清空鏈表（保留頭節(jié)點(diǎn)）
    void clear()
    {
        iterator it = begin();
        while (it != end())
        {
        erase(it++);  // 使用后置++避免迭代器失效
        }
    }

};

6. 測試代碼與特殊用例

6.1 基本功能測試

void test_list1()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

6.2 結(jié)構(gòu)體訪問測試

struct Date
{
    int _year = 0;
    int _month = 1;
    int _day = 1;
};

void test_list2()
{
    list<Date> lt;
    lt.push_back(Date());
    lt.push_back(Date());

    list<Date>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
        ++it;
    }
    cout << endl;
}

關(guān)鍵點(diǎn)說明：

it->等價(jià)于it.operator->()，返回Date*
編譯器特殊處理了it->member，使其等價(jià)于(it.operator->())->member
這種語法糖提高了代碼的可讀性

6.3 const迭代器測試

void print_list(const list<int>& lt)
{
    list<int>::const_iterator it = lt.begin();
    while (it != lt.end())
    {
        // *it = 1;  // 錯(cuò)誤：不能修改const引用指向的值
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

6.4 拷貝構(gòu)造與賦值測試

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int> lt2(lt);  // 測試拷貝構(gòu)造函數(shù)
    print_list(lt2);
}

void test_list5()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int> lt2;
    lt2.push_back(10);
    lt2.push_back(20);
    lt2.push_back(30);
    lt2.push_back(40);
    
    lt = lt2;  // 測試賦值運(yùn)算符
    print_list(lt);
}