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

list类模拟实现

list类的模拟实现

目录

  1. 结点
  2. 框架
  3. 迭代器
    1. 初次尝试
    2. const迭代器

完整代码

1.结点

一个结点需要包含:储存的数据,上一个结点的地址,下一个结点的地址。

template<class T>
struct __list_node
{
    __list_node<T>* _prev;
    __list_node<T>* _next;
    T _data;

    __list_node(const T& x = T())	//T()是匿名类型,如果没有传参,编译器会调用相应类型的构造函数
        :_data(x)
        ,_prev(nullptr)
        ,_next(nullptr)
    {}
};
  • 由于我们后面会在类外访问,所以为了避免麻烦就写成struct,这样成员属性都是public的。
  • 使用模板,方便适配各种数据类型

2.框架

list类包含哨兵结点的指针

template<class T>
class list
{
public:
    typedef __list_node<T> Node;
    
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    
private:
    Node* _head;
};    
  • 因为是双向循环链,所以哨兵结点的指针都指向自己

3.迭代器

list的迭代器的实现,是模拟list实现的重中之重

3.1初次尝试

  • list迭代器的本质还是指针
  • 我们将指针的封装,内部进行运算符重载
template<class T>
struct __list_iterator
{
    typedef __list_node<T> Node;
    typedef __list_iterator<T> Self;
    Node* _node;

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

    T& operator*()
    {
        return _node->_data;
    }

    T* operator->()
    {
        return &_node->_data;
    }

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

    Self operator++(int)
    {
        Self tmp(*this);
        //_node = _node->_next;
        ++(*this);
        return tmp;
    }

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

    Self operator--(int)
    {
        Self tmp(*this);
        //_node = _node->_next;
        --(*this);
        return tmp;
    }

    bool operator!=(const Self& it)const
    {
        return _node != it._node;
    }

    bool operator==(const Self& it)const
    {
        return _node == it._node;
    }
};
  • 就是将++/–的操作通过运算符重载,变成在结点间移动的操作。

3.2const迭代器

  • list的迭代器不像vector/string类的迭代器,它不可以直接在迭代器的前面加const修饰
  • 指针被const修饰后,不能通过指针来修改数据,意味着operator*operator->的作用失效,但其他函数还能继续使用
  • 如果再专门写一份const的迭代器,那么代码就太过冗余了
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 operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

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

    Self operator++(int)
    {
        Self tmp(*this);
        //_node = _node->_next;
        ++(*this);
        return tmp;
    }

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

    Self operator--(int)
    {
        Self tmp(*this);
        //_node = _node->_next;
        --(*this);
        return tmp;
    }

    bool operator!=(const Self& it)const
    {
        return _node != it._node;
    }

    bool operator==(const Self& it)const
    {
        return _node == it._node;
    }
};
  • 这样,如果是const迭代器,就传const修饰的指针和引用。

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

相关文章:

  • Spring Security 门神中的战斗机
  • 若依框架部署到服务器后头像资源访问404
  • 实时数据处理:技术支持和优势
  • 提升网站速度与性能优化的有效策略与实践
  • C数组手动输入问题
  • 基于web的便捷饭店点餐小程序的设计与实现(lw+演示+源码+运行)
  • 从0学习React(7)
  • Maven(18)如何使用Maven打包项目?
  • 1通道10GSPS或2通道5G 14 bit数字化仪
  • 跟着小土堆学习pytorch(六)——神经网络的基本骨架(nn.model)
  • 命令如诗,步入Linux的晨曦:指令初学者的旅程(下)
  • 日期差值题目(也可能是最容易看懂的了)
  • UG NX二次开发(C#)-计算圆柱面与其他平面的夹角
  • 第十二课 Vue中的事件修饰符
  • ubuntu系统docker容器中的torch,使用宿主机的gpu
  • 如何将原本打开Edge呈现出的360浏览器,更换成原本的Edge页面或者百度等其他页面
  • JavaFX WebView + Vue初始化加载数据解决方案
  • 基于javaweb的流浪宠物管理系统的设计与实现源码(springboot)
  • 大数据-197 数据挖掘 机器学习理论 - scikit-learn 泛化能力 交叉验证
  • 视频设备一体化监控运维方案
  • openGauss开源数据库实战十四
  • Flink难点和高频考点:Flink的反压产生原因、排查思路、优化措施和监控方法
  • 性能测试——Jmeter实战
  • DAIN-SQL,DAIL-SQL,C3-SQL和 DIN-SQL 技术的理解和异同点
  • LSTM——长短期记忆神经网络
  • Linux 调度SCHED_FIFO或SCHED_RR