C++之list的自我实现

发布于：2025-06-10 ⋅ 阅读:(21) ⋅ 点赞:(0)

list


在这里插入图片描述

引言

在C++标准库中，std::list作为双向链表容器，提供了高效的插入和删除操作。本文将深入解析双向链表的三大核心组件：节点类、迭代器类和链表类，通过代码实例详细说明list的底层原理到底是什么。

一、节点类：ListNode

1.1 类定义与作用

template<class T>
struct ListNode {
    ListNode(const T& val = T())
        :_pPre(nullptr), _pNext(nullptr), _val(val) 
    { }
    
    ListNode<T>* _pPre;  // 指向前驱节点
    ListNode<T>* _pNext; // 指向后继节点
    T _val;              // 存储的数据值
};

核心作用：作为链表的基本单元，封装节点数据和指针关系

1.2 关键特性

  • 双向指针：_pPre和_pNext实现双向链接
  • 默认构造函数：支持无参创建空节点
  • 值初始化：通过T()提供默认值初始化
  • 模板化设计：支持任意数据类型存储

二、迭代器类：ListIterator

2.1 类定义与模板参数

template<class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
    
    PNode _pNode; // 封装的节点指针
};

模板参数解析：

  • T：节点数据类型
  • Ref：引用类型（T&或const T&）
  • Ptr：指针类型（T或const T）

2.2 核心功能函数

2.2.1 访问操作符
Ref operator*() { return _pNode->_val; }   // 解引用获取值
Ptr operator->() { return &_pNode->_val; } // 访问成员指针
2.2.2 迭代器移动
// 前置++
Self& operator++() {
    _pNode = _pNode->_pNext;
    return *this;
}

// 后置++
Self operator++(int) {
    Self tmp(_pNode);
    _pNode = _pNode->_pNext;
    return tmp;
}

// 前置--
Self& operator--() {
    _pNode = _pNode->_pPre;
    return *this;
}
2.2.3 比较操作符
bool operator!=(const Self& s) { 
    return _pNode != s._pNode; 
}

bool operator==(const Self& s) { 
    return _pNode == s._pNode; 
}

2.3 设计要点

  • 行为模拟：通过运算符重载模拟指针行为
  • 泛型支持：同一模板支持普通/常量迭代器
  • 位置封装：隐藏节点指针实现细节

三、链表类：list

3.1 核心成员与类型定义

template<class T>
class list {
    typedef ListNode<T> Node;
    typedef Node* PNode;
    
    size_t _size;    // 元素计数器
    PNode _pHead;    // 哨兵头节点
};

3.2 构造与析构函数

3.2.1 头节点创建
void CreateHead() {
    _pHead = new Node; // 创建头节点
    _pHead->_pNext = _pHead; // 自环结构
    _pHead->_pPre = _pHead;
    _size = 0;
}

哨兵节点作用：统一空/非空链表操作，简化边界处理

3.2.2 构造函数组
list() { CreateHead(); } // 默认构造

// 填充构造
list(int n, const T& value = T()) {
    CreateHead();
    for(int i=0; i<n; ++i) 
        push_back(value);
}

// 拷贝构造
list(const list<T>& lt) {
    CreateHead();
    for(auto e : lt) push_back(e);
}
3.2.3 赋值与析构
// 拷贝交换赋值
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

// 析构函数
~list() {
    clear();        // 清空元素
    delete _pHead;  // 释放头节点
    _pHead = nullptr;
}

3.3 迭代器访问接口

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

iterator begin() { return _pHead->_pNext; } // 首元素
iterator end() { return _pHead; }           // 尾后位置

const_iterator begin() const { 
    return const_iterator(_pHead->_pNext); 
}

3.4 容量操作

size_t size() const { return _size; }  // 元素计数
bool empty() const { return 0 == _size; } // 判空

3.5 关键操作函数

3.5.1 元素插入
void insert(iterator pos, const T& val) {
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;
    
    PNode newNode = new Node(val); // 创建新节点
    
    // 调整四向指针
    newNode->_pNext = cur;
    newNode->_pPre = prev;
    prev->_pNext = newNode;
    cur->_pPre = newNode;
    
    _size++; // 更新计数
}
3.5.2 元素删除
iterator erase(iterator pos) {
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;
    PNode next = cur->_pNext;
    
    // 跳过当前节点
    prev->_pNext = next;
    next->_pPre = prev;
    
    delete cur;  // 释放节点
    _size--;     // 更新计数
    
    return iterator(next); // 返回下一位置
}
3.5.3 清空操作
void clear() {
    iterator it = begin();
    while(it != end()) {
        it = erase(it); // 迭代删除
    }
}

3.6 复合操作接口

// 尾端操作
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }

// 首端操作
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }

// 高效交换
void swap(list<T>& lt) {
    std::swap(_pHead, lt._pHead);
    std::swap(_size, lt._size);
}

四、三大组件协作关系

4.1 组件交互流程

管理
创建
生成
操作
双向链接
list类
哨兵头节点
普通节点
迭代器

4.2 核心操作时间复杂度

操作 时间复杂度 实现函数
插入 O(1) insert()
删除 O(1) erase()
首尾插入 O(1) push_front/back
首尾删除 O(1) pop_front/back
随机访问 O(n) 迭代器遍历

五、设计亮点与最佳实践

  1. 哨兵节点(Sentinel Node)

    • 统一空/非空操作逻辑
    • 消除头尾特殊处理
    • 固定end()迭代器位置

  2. 写时复制(Copy-on-Write)优化

    list<T>& operator=(list<T> lt) {
    swap(lt); // 参数拷贝+交换
    return *this;
}

  3. 异常安全保证

    • 内存分配失败时保持原链表不变
    • 删除操作保证迭代器有效（返回下一位置）

  4. 迭代器失效策略

    • 仅删除元素的迭代器失效
    • 其他迭代器保持有效
    • 符合STL标准规范

全部代码实例

namespace zzh
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_pPre(nullptr)
            , _pNext(nullptr)
            , _val(val)
        { }
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };


    // List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        { }
        ListIterator(const Self& s)
            :_pNode(s._pNode)
        { }
        Ref operator*()
        {
            return _pNode->_val;
        }
        Ptr operator->()
        {
            return &_pNode->_val;
        }
        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }
        Self operator++(int)
        {
            Self tmp(_pNode);
            _pNode = _pNode->_pNext;
            return tmp;
        }
        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }
        Self operator--(int)
        {
            Self tmp(_pNode);
            _pNode = _pNode->_pPre;
            return tmp;
        }
        bool operator!=(const Self& s)
        {
            return _pNode != s._pNode;
        }
        bool operator==(const Self& s)
        {
            return _pNode == s._pNode;
        }

        PNode _pNode;
    };


    // list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
    public:
        // List的构造
        void CreateHead()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            _size = 0;
        }
        list()
        {
            CreateHead();
        }
        list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0;i < n;i++)
            {
                push_back(value);
            }
        }
        list(const list<T>& lt)
        {
            CreateHead();
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }
        ~list()
        {
            clear();
            delete _pHead;
            _pHead = nullptr;
        }

        // List Iterator
        iterator begin()
        {
            return iterator(_pHead->_pNext);
        }
        iterator end()
        {
            return iterator(_pHead);
        }
        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }
        const_iterator end() const
        {
            return const_iterator(_pHead);
        }

        // List Capacity
        size_t size() const
        {
            return _size;
        }
        bool empty() const
        {
            return _size == 0;
        }


        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }


        // 在pos位置前插入值为val的节点
        void insert(iterator pos, const T& val)
        {
            PNode cur = pos._pNode;
            PNode prev = cur->_pPre;
            PNode newnode = new Node(val);
            newnode->_pNext = cur;
            newnode->_pPre = prev;
            prev->_pNext = newnode;
            cur->_pPre = newnode;

            _size++;
        }
        iterator erase(iterator pos)
        {
            PNode cur = pos._pNode;
            PNode prev = cur->_pPre;
            PNode next = cur->_pNext;
            prev->_pNext = next;
            next->_pPre = prev;
            delete cur;
            _size--;
            return iterator(next);
        }
        void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        void swap(list<T>& lt)
        {
            std::swap(lt._pHead, _pHead);
            std::swap(lt._size, _size);
        }
    private:
        size_t _size;
        PNode _pHead;
    };
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布