【C++】list容器功能模拟实现

这篇具有很好参考价值的文章主要介绍了【C++】list容器功能模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

介绍

        上一次介绍了list队容器的迭代器模拟,这次模拟实现list的简单功能,尤其要注意构造函数、析构函数、以及赋值运算符重载的实现。

        list容器需要接纳所有类型的数据,因此,结构设置与迭代器设置同理,需要引入结点,数据。

    //结点结构

    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _last;
        T _data;
        ListNode(const T& x = T())
            :_next(nullptr)
            , _last(nullptr)
            , _data(x)
        { }
    };

    //list容器基本元素

    template<class T>
    class list
    {
    public:
        typedef ListNode<T> Node;  
        typedef _list_iterator<T> iterator;

    private:
        Node* _node;  //此结点为哨兵结点,前指头结点,后指尾结点,里面没有数据
    };


一,构造函数

        构造函数只需构造“ 哨兵结点 ”即可,因为这里使用链式结构存储,因此构造函数没有顺序结构那样的逻辑。代码如下:

list()
{
    _node = new Node;
    _node->_last = _node;
    _node->_next = _node;
}

        拷贝构造的实现可直接运用赋值运算符,这里要注意,由于这里的设计设计到动态空间的申请,所以实现时需进行深拷贝。

        这里,我们先实现push_back尾插功能,代码如下:

//尾插功能

void push_back(const T& x = T()) 
{
    Node* node = new Node;
    node->_data = x;
    node->_next = _node;
    node->_last = _node->_last;
    _node->_last->_next = node;
    _node->_last = node;
}

        下面是赋值运算符和拷贝构造的实现,唯一要注意的是在使用赋值运算符前,要先确定“ 哨兵结点 ”,即普通的构造函数。

//赋值运算符重载
list<T>& operator=(list<T>& L)
{
    Node* node = (L._node)->_next;
    while (node != L._node)
    {
        push_back(node->_data);
        node = node->_next;
    }
    return *this;
}

//拷贝构造函数

list(list<T>& L)
{

    //哨兵结点的构造
    _node = new Node;
    _node->_last = _node;
    _node->_next = _node;

    //赋值运算符的使用
    *this = L;
}

        下面进行样例代码测试:

void test1()
{
    list<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    list<int> v2;
    v2 = v1;
    list<int> v3(v1);
    std::cout << "List v2: ";
    for (auto e : v2)
    {
        std::cout << e << "  ";
    }
    std::cout << std::endl;
    std::cout << "List v3: ";
    for (auto e : v3)
    {
        std::cout << e << "  ";
    }
    std::cout << std::endl;
}

 测试数据结果:

【C++】list容器功能模拟实现,c++,list,开发语言


二,析构函数

        析构函数的设计只需诼渐释放所有结点即可,包括“ 哨兵结点 ”。代码如下:

~list()
{
    Node* t = _node->_next;
    while (t != _node)
    {
        Node* next = t->_next;
        delete t;
        t = next;
    }
    delete t;    //最后释放哨兵结点
    t = nullptr;
}


三,list容器接口

        这里实现begin()、end()、push_back(这个接口上面已实现,这里不做演示)、pop_back、push_front、pop_front。代码如下:

iterator begin()  //获取头结点
{
    return _node->_next;
}
iterator end()  //获取尾结点
{
    return _node;
}
void pop_back()  //尾删
{
    assert(_node->_next != _node);
    Node* node = _node->_last->_last;
    delete _node->_last;
    _node->_last = node;
    node->_next = _node;
}
void push_front(const T& x = T())  //头插
{
    Node* node = new Node;
    node->_data = x;
    node->_next = _node->_next;
    node->_last = _node;
    _node->_next->_last = node;
    _node->_next = node;
}
void pop_front()  //头删
{
    assert(_node->_next != _node);
    Node* node = _node->_next->_next;
    delete _node->_next;
    _node->_next = node;
    node->_last = _node;
}

        list容器常用功能有clear()、swap()、erase、insert。接口参数与实现如下:

void clear()
{
    Node* t = _node->_next;
    while (t != _node)
    {
        Node* next = t->_next;
        delete t;
        t = next;
    }
    t = nullptr;
}
void swap(list<T>& L)
{
    std::swap(_node, L._node);
}
iterator insert(iterator pos, const T& x = T())
{
    Node* node = new Node;
    node->_data = x;
    node->_next = pos.node;
    node->_last = (pos.node)->_last;
    node->_next->_last = node;
    node->_last->_next = node;
    return node;
}
iterator erase(iterator pos)
{
    assert(pos.node != _node);
    Node* next = (pos.node)->_next;
    Node* last = (pos.node)->_last;
    delete pos.node;
    next->_last = last;
    last->_next = next;
    return next;
}

        下面进行样例代码测试:

void test2()
{
    list<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    list<int>::iterator it = ++v.begin();
    v.insert(it, 9);
    v.erase(v.begin());
    for (auto e : v)
    {
        std::cout << e << "  ";
    }
    std::cout << std::endl;
}

测试数据结果如下:

【C++】list容器功能模拟实现,c++,list,开发语言

        其它细节逻辑可自行测试,这里不再一一演示。

        总:list容器的模拟实现跟部分容器可能有些难度,这里注重要注意类型使用和转换,迭代器的模拟以及构造赋值与析构。功能实现的逻辑基本与链式逻辑一样。文章来源地址https://www.toymoban.com/news/detail-819637.html

到了这里,关于【C++】list容器功能模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】容器篇(二)——List的基本概述以及模拟实现

    前言: 在上期,我们学习了STL库中的第一个容器--vector ,今天我将给大家介绍的是 库中的另外一个容器--List。其实,有了之前学习 vector 的知识,对于List 的学习成本就很低了。 目录 (一)基本介绍 1、基本概念 2、list 与 forward_list 的比较 3、特点 (二)list的使用 1、list的

    2024年02月06日
    浏览(45)
  • 【C++】反向迭代器的模拟实现通用(可运用于vector,string,list等模拟容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 我们要写出一个通用的反向迭代器模拟而且在保证代码简介不繁琐的的情况下,一定程度上使用我们自己模拟的已经封装好的iterator迭代器可以简化许多步骤,首先我们要知

    2024年02月14日
    浏览(56)
  • 深入篇【C++】手搓模拟实现list类(详细剖析底层实现原理)&&模拟实现正反向迭代器【容器适配器模式】

    1.一个模板参数 在模拟实现list之前,我们要理解list中的迭代器是如何实现的。 在vector中迭代器可以看成一个指针,指向vector中的数据。它的解引用会访问到具体的数据本身,++会移动到下一个数据位置上去,这些都是因为vector具有天生的优势:空间上是连续的数组,这样指

    2024年02月15日
    浏览(46)
  • 【STL】“list“容器从使用到模拟实现

    🎉博客主页:小智_x0___0x_ 🎉欢迎关注:👍点赞🙌收藏✍️留言 🎉系列专栏:C++初阶 🎉代码仓库:小智的代码仓库 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是 双向链表结构 ,双向链表中每个元素存储在

    2024年02月16日
    浏览(87)
  • STL容器 -- list的模拟实现(配详细注释)

    C++ STL(Standard Template Library,标准模板库)提供了一组通用的模板类和函数,用于实现常用的数据结构和算法。其中之一是 std::list,它实现了一个双向链表。 std::list 是一个容器,用于存储一系列的值。与数组和向量等连续存储的容器不同,std::list 使用链表作为底层数据结构

    2024年02月16日
    浏览(49)
  • 【C++模拟实现】list的模拟实现

    作者:爱写代码的刚子 时间:2023.9.3 前言:本篇博客关于list的模拟实现和模拟实现中遇到的问题 list模拟实现的部分代码 list模拟实现中的要点 const_iterator的实现 我们选择使用模版参数,复用iterator的类,设置三个模版参数: templateclass T,class Ref,class Ptr 并且 typedef __list_iter

    2024年02月09日
    浏览(55)
  • 【C++】list模拟实现

    个人主页 : zxctscl 如有转载请先通知 在前面一篇博客中分享了list的相关介绍 【C++】list介绍,这次来模拟实现一下list。 成员变量: 无参构造: 插入: 在库里面定义节点需要全部公有时用到的就是struct: 这里我们也用相同方法自己定义出一个节点: 然后在写list类时候就要

    2024年04月11日
    浏览(38)
  • C++ list 模拟实现

      目录 1. 基本结构的实现 2.  list() 3. void push_back(const T val) 4. 非 const 迭代器 4.1 基本结构  4.2 构造函数  4.3 T operator*() 4.4  __list_iterator operator++() 4.5 bool operator!=(const __list_iterator it) 4.6 T* operator-() 5. const 迭代器  6. begin()  end() ​编辑 7. iterator insert(iterator pos, const T v

    2024年02月08日
    浏览(51)
  • C++ list模拟实现

    源码中的list实现为 带头双向链表   list类的对象有两个成员:指向头结点的指针_head,统计数据个数的_size 在模拟实现list之前,需要先模拟实现 结点类,迭代器类 结点类:三个成员,_data _prev _next , 实现成struct (也是类,不过与class不同的是,它的成员都是公开的,都可以

    2024年02月11日
    浏览(47)
  • (C++) list底层模拟实现

     个人主页:Lei宝啊  愿所有美好如期而遇 首先,list底层是一个带头双向循环链表,再一个,我们还要解决一个问题,list的迭代器,vector和string的迭代器可以直接++,是因为他们的地址空间是连续的,而链表不是,所以链表的迭代器封装的不是原生指针,我们需要想办法解决

    2024年01月21日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包