当前位置： 首页 > article >正文

(C++ STL)list类的简单模拟实现与源码展示

article 2024/11/12 2:52:17

list类的简单模拟实现

  • 一、前言
  • 二、ListNode 单个节点的成员变量
  • 三、ListIterator 迭代器
  • 四、ReverseListIterator 迭代器
  • 五、list 的成员变量与初始化
  • 六、list 部分函数实现
    • insert
    • erase
  • 七、list 源代码

以下代码环境为 VS2022 C++。

一、前言

list类 本质上是数据结构中的双向带头链表。（可参考：双向链表的讲解与实现）

不过要注意的是，list类 的本身并不支持随机访问，迭代器要求的前后 ++、-- 也不支持，导致这个重担交给了 list 的迭代器，使得它迭代器的设计要比 vector、string 的复杂不少。

接下来我们来简单实现 list类 和 部分对应函数。

参考：legacy.cplusplus.com中的 std::list

二、ListNode 单个节点的成员变量

在 list.hpp 中：

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

        ListNode<T>* _pPrev;	// 前一个节点地址
        ListNode<T>* _pNext;	// 后一个节点地址

        T _val;
    };
}

将 list 的节点单独封装为一个类，便于后续组合操作。

三、ListIterator 迭代器

在 namespace my 中：

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;

        typedef ListIterator<T, Ref, Ptr> Self;
        typedef Ref reference;
        typedef Ptr pointer;

        ListIterator(Node* pNode = nullptr)
            :_pNode(pNode)
        {
            ;
        }

        ListIterator(const Self& listIter)
            :_pNode(listIter._pNode)
        {
            ;
        }

        reference operator*()
        {
            return _pNode->_val;
        }

        reference operator*() const
        {
            return _pNode->_val;
        }

        pointer operator->()
        {
            return &_pNode->_val;
        }

        pointer operator->() const
        {
            return &_pNode->_val;
        }

        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self temp = _pNode;
            _pNode = _pNode->_pNext;
            return temp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPrev;
            return *this;
        }

        Self operator--(int)
        {
            Self temp = _pNode;
            _pNode = _pNode->_pPrev;
            return temp;
        }

        bool operator!=(const Self& listIter) const
        {
            return _pNode->_val != listIter._pNode->_val;
        }

        bool operator==(const Self& listIter) const
        {
            return _pNode->_val == listIter._pNode->_val;
        }

        Node* _pNode;
    };

ListIterator 设计了三个模版关键字，class T, class Ref, class Ptr，这是考虑到 const_iterator 的返回类型。

例如：当返回 operator*() 的返回值时，使用 iterator 返回的是 T 的 引用，也就是 T&，
但使用 const_iterator 返回的是 const T&，两者只差一个 const 权限。pointer、Self 同理。

当然，也可以选择重新设计一个 const_iterator类，这里只是用模版减少了工作量。

四、ReverseListIterator 迭代器

在 namespace my 中：

    // 反向迭代器
    template<class Iter>
    struct ReverseListIterator
    {
        typedef ReverseListIterator<Iter> Self;

        typedef typename Iter::reference reference;
        typedef typename Iter::pointer pointer;

        ReverseListIterator(const Iter& it = Iter())
            :_it(it)
        {
            ;
        }

        ReverseListIterator(const Self& listIter)
            :_it(listIter._it)
        {
            ;
        }

        reference operator*()
        {
            return *_it;
        }

        reference operator*() const
        {
            return *_it;
        }

        pointer operator->()
        {
            return _it->_val;
        }

        pointer operator->() const
        {
            return _it->_val;
        }

        Self& operator++()
        {
            --_it;
            return *this;
        }

        Self operator++(int)
        {
            Self temp = *this;
            --_it;
            return temp;
        }

        Self& operator--()
        {
            ++_it;
            return *this;
        }

        Self operator--(int)
        {
            Self temp = *this;
            ++_it;
            return temp;
        }

        bool operator!=(const Self& listIter) const
        {
            return (*_it) != (*listIter._it);
        }

        bool operator==(const Self& listIter) const
        {
            return (*_it) == (*listIter._it);
        }

        Iter _it;
    };

反向迭代器组合了 ListIterator类，毕竟 iterator 的 + + 等价 reverse_iterator 的 - -，而它的 - - 等价 reverse_iterator 的 + +。

五、list 的成员变量与初始化

在 namespace my 中：

    template<class T>
    class list
    {
    public:

        typedef ListNode<T>* PNode;
        typedef ListNode<T> Node;

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

        typedef ReverseListIterator<iterator> reverse_iterator;
        typedef ReverseListIterator<const_iterator> const_reverse_iterator;

    private:

        PNode CreateNode(const T& value = T())
        {
            return new Node(value);
        }

        PNode CreateHead()
        {
            PNode temp = CreateNode();
            temp->_pNext = temp;
            temp->_pPrev = temp;
            return temp;
        }

        PNode _pHead = CreateHead();	// 走初始化列表时会执行
        size_t _size;
	};

考虑到 list类 必须要带头，这里直接声明在初始化时候带头，方便后续操作。

六、list 部分函数实现

insert

这里只实现一个。

参考：std::list::insert

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{
    PNode cur = pos._pNode;
    PNode prev = pos._pNode->_pPrev;
    PNode newNode = CreateNode(val);

    newNode->_pPrev = prev;
    newNode->_pNext = cur;

    prev->_pNext = newNode;
    cur->_pPrev = newNode;

    ++_size;
    return newNode;
}

erase

参考：std::list::erase

这里只实现一个。

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{
    PNode cur = pos._pNode;
    PNode prev = cur->_pPrev;
    PNode next = cur->_pNext;

    prev->_pNext = next;
    next->_pPrev = prev;

    --_size;
    delete cur;
    pos = nullptr;
    return next;
}

其他实现了的函数不是复用就是代码量小，就不单独拎出来介绍了。

七、list 源代码

#pragma once

#include<iostream>

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

        ListNode<T>* _pPrev;	// 前一个节点地址
        ListNode<T>* _pNext;	// 后一个节点地址

        T _val;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;

        typedef ListIterator<T, Ref, Ptr> Self;
        typedef Ref reference;
        typedef Ptr pointer;

        ListIterator(Node* pNode = nullptr)
            :_pNode(pNode)
        {
            ;
        }

        ListIterator(const Self& listIter)
            :_pNode(listIter._pNode)
        {
            ;
        }

        reference operator*()
        {
            return _pNode->_val;
        }

        reference operator*() const
        {
            return _pNode->_val;
        }

        pointer operator->()
        {
            return &_pNode->_val;
        }

        pointer operator->() const
        {
            return &_pNode->_val;
        }

        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self temp = _pNode;
            _pNode = _pNode->_pNext;
            return temp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPrev;
            return *this;
        }

        Self operator--(int)
        {
            Self temp = _pNode;
            _pNode = _pNode->_pPrev;
            return temp;
        }

        bool operator!=(const Self& listIter) const
        {
            return _pNode->_val != listIter._pNode->_val;
        }

        bool operator==(const Self& listIter) const
        {
            return _pNode->_val == listIter._pNode->_val;
        }

        Node* _pNode;
    };

    // 反向迭代器
    template<class Iter>
    struct ReverseListIterator
    {
        typedef ReverseListIterator<Iter> Self;

        typedef typename Iter::reference reference;
        typedef typename Iter::pointer pointer;

        ReverseListIterator(const Iter& it = Iter())
            :_it(it)
        {
            ;
        }

        ReverseListIterator(const Self& listIter)
            :_it(listIter._it)
        {
            ;
        }

        reference operator*()
        {
            return *_it;
        }

        reference operator*() const
        {
            return *_it;
        }

        pointer operator->()
        {
            return _it->_val;
        }

        pointer operator->() const
        {
            return _it->_val;
        }

        Self& operator++()
        {
            --_it;
            return *this;
        }

        Self operator++(int)
        {
            Self temp = *this;
            --_it;
            return temp;
        }

        Self& operator--()
        {
            ++_it;
            return *this;
        }

        Self operator--(int)
        {
            Self temp = *this;
            ++_it;
            return temp;
        }

        bool operator!=(const Self& listIter) const
        {
            return (*_it) != (*listIter._it);
        }

        bool operator==(const Self& listIter) const
        {
            return (*_it) == (*listIter._it);
        }

        Iter _it;
    };

    //list类
    template<class T>
    class list
    {
    public:

        typedef ListNode<T>* PNode;
        typedef ListNode<T> Node;

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

        typedef ReverseListIterator<iterator> reverse_iterator;
        typedef ReverseListIterator<const_iterator> const_reverse_iterator;

    public:

        //-----------------------------------------------

        list()
        {
            ;
        }

        list(int n, const T& value = T())
        {
            for (int i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }

        list(std::initializer_list<T> il)
        {
            for (const auto& e : il)
            {
                push_back(e);
            }
        }

        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        list(const list<T>& list1)
        {
            for (auto& e : list1)
            {
                push_back(e);
            }
        }

        static void swap(list<T> list1, list<T> list2)
        {
            std::swap(list1._pHead, list2._pHead);
            std::swap(list1._size, list2._size);
        }

        list<T>& operator=(list<T> list1)
        {
            swap(*this, list1);
            return *this;
        }

        ~list()
        {
            clear();
            delete _pHead;
            _pHead = nullptr;
        }

        //-----------------------------------------------

        iterator begin()
        {
            return _pHead->_pNext;
        }

        iterator end()
        {
            return _pHead;
        }

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

        const_iterator end() const
        {
            return _pHead;
        }

        reverse_iterator rbegin()
        {
            return iterator(_pHead->_pPrev);
        }

        reverse_iterator rend()
        {
            return iterator(_pHead);
        }

        const_reverse_iterator rbegin() const
        {
            return const_iterator(_pHead->_pPrev);
        }

        const_reverse_iterator rend() const
        {
            return const_iterator(_pHead);
        }

        //-----------------------------------------------

        size_t size() const
        {
            return _size;
        }

        bool empty() const
        {
            return _size == 0;
        }

        //-----------------------------------------------

        T& front()
        {
            return _pHead->_pNext;
        }

        const T& front()const
        {
            return _pHead->_pNext;
        }

        T& back()
        {
            return _pHead->_pPrve;
        }

        const T& back() const
        {
            return _pHead->_pPrve;
        }

        //-----------------------------------------------

        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());
        }

        iterator insert(iterator pos, const T& val);

        iterator erase(iterator pos);

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

    private:

        PNode CreateNode(const T& value = T())
        {
            return new Node(value);
        }

        PNode CreateHead()
        {
            PNode temp = CreateNode();
            temp->_pNext = temp;
            temp->_pPrev = temp;
            return temp;
        }

        PNode _pHead = CreateHead();
        size_t _size;
    };
};

template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{
    PNode cur = pos._pNode;
    PNode prev = pos._pNode->_pPrev;
    PNode newNode = CreateNode(val);

    newNode->_pPrev = prev;
    newNode->_pNext = cur;

    prev->_pNext = newNode;
    cur->_pPrev = newNode;

    ++_size;
    return newNode;
}

template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{
    PNode cur = pos._pNode;
    PNode prev = cur->_pPrev;
    PNode next = cur->_pNext;

    prev->_pNext = next;
    next->_pPrev = prev;

    --_size;
    delete cur;
    pos = nullptr;
    return next;
}

http://www.kler.cn/a/289743.html

相关文章：

  • 股票投资学习路线图
  • Linux应用——线程池
  • Android 如何实现不编译指定的apk，不加载系统应用
  • Git - 命令杂谈 - fetch与push
  • 全球海工供应链，中国建造！第十一届全球FPSOFLNGFSRU大会在上海隆重召开
  • 《Python网络安全项目实战》项目4 编写网络扫描程序
  • 【大模型测评】2024大语言模型综合能力测评报告（免费下载）
  • “三年级英语”暴增5亿搜索量？需求来了！附2个极品AI吸粉玩法！
  • 第3章-04-Python库BeautifulSoup安装与讲解
  • Gateway的基本概念
  • Django + websocket 连不上
  • 内部知识库：企业智慧资产的安全守护者
  • 低秩近似概念
  • Dev C++：简单步骤下载与安装指南
  • DHCPv6 浅析 配置示例
  • 基于vue框架的超市商品管理系统m9o29（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。
  • Redis Desktop Manager 0.8.8.384 安装与使用详解
  • Spire.PDF for .NET【文档操作】演示：创建 PDF 文档
  • python-实战4拆分pdf文件
  • 小土堆pytorch
  • CSS实现水滴效果图
  • 【Linux】进程间的关系（第十三篇）
  • oracle日期加减方式
  • 【区块链 + 物联网】智慧路灯计费和融资区块链解决方案 | FISCO BCOS应用案例
  • H265视频转换H264视频对应m3u8格式地址播放完整案例
  • IP地址查询功能详解—构建风险画像与代理识别