【C++】List模拟实现过程中值得注意的点

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

【C++】List模拟实现过程中值得注意的点,C++,c++,开发语言

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

1.List迭代器

2.适配器

3.迭代器失效

4.模拟实现源码


前言

本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题,都是一些需要注意的细节问题,希望与大家共勉。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================文章来源地址https://www.toymoban.com/news/detail-814743.html

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================


1.List迭代器

在之前模拟实现『 String和Vector』时,我们都采用的『 原生指针』实现迭代器,那么到List这里还可以么?

这我们就要搞清楚『 迭代器存在的意义』。

我们希望可以通过迭代器来实现对某一容器的遍历访问,例如对迭代器++或--;

迭代器:让使用者可以不必关心容器的底层实现,可以用简单统一的方式对容器内的数据进行访问。

之前的String和Vector我们可以简单的利用原生指针实现迭代器是因为String和Vector底层的物理空间是连续的,所以++和--当然可以访问到对应的对象。

可到了List中,List的底层是带头双向循环链表,链表的物理空间并『 不连续』,所以我们需要对迭代器进行一定的『 封装』,让迭代器『 符合统一的迭代器使用规则』。

如何封装呢?

提示:比如重载各种运算符,++运算符的底层可以为链表的p=p->next;

注意:end迭代器是最后一个元素的下一个位置,所以end一般指向的是『 头节点』。 

  • 头节点不存储数据。

【C++】List模拟实现过程中值得注意的点,C++,c++,开发语言 

// List的节点类
template<class T>
struct ListNode
{
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    ListNode(const T& val = T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(val)
    {}
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class __list_iterator
{
public:
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> Self;
    Node* _node;
    __list_iterator(Node* x)
        :_node(x)
    {}

    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;
        return tmp;
    }
    Self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    Self& operator--(int)
    {
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }
    bool operator==(const Self& s)
    {
        return _node == s._node;
    }
};

2.适配器

我们知道迭代器一般需要两个形式,一种为非const迭代器,一种为const迭代器用来满足不同的使用场景,但你有没有发现上面的代码,似乎只有一种形式???

其实并不是,如果我们按照以前的写法,应为:

//非const迭代器类
template<class T>
class __list_iterator
{
public:
    typedef ListNode<T> Node;
    typedef __list_iterator<T> Self;
    Node* _node;
    __list_iterator(Node* x)
        :_node(x)
    {}

    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;
        return tmp;
    }
    Self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    Self& operator--(int)
    {
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }
    bool operator==(const Self& s)
    {
        return _node == s._node;
    }
};
//const迭代器类
template<class T>
class __list_const_iterator
{
public:
	typedef ListNode<T> Node;
	typedef __list_const_iterator<T> self;
	Node* _node;
	__list_const_iterator(Node* x)
		:_node(x)
	{}

    const T& operator*()
    {
        return _node->_data;
    }
    const T* operator->()
    {
        return &_node->_data;
    }
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);

		_node = _node->_next;

		return tmp;
	}
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	self operator--(int)
	{
		self tmp(*this);

		_node = _node->_prev;

		return tmp;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

但这样看起来代码非常冗余,那么有没有什么方式来简化代码呢?

其实模板的用法不仅有vector<int>这类,还可以这么使用:

【C++】List模拟实现过程中值得注意的点,C++,c++,开发语言


所以,编译器可以通过模板自动推演出当前使用场景为const迭代器还是非const迭代器。

这种方式可以唤作为『 适配器』,当然这部分后面还会有涉及。


3.迭代器失效

在之前学习vector时我们发现了迭代器失效的问题,对于vector来讲迭代器失效往往发生在扩容之后,那么对于List来讲,是不需要扩容的,那么List会不会发生迭代器失效的问题呢?

List可能会在『 erase』操作之后,迭代器失效。

我们来分析一下:

vector迭代器失效的原因是因为扩容导致迭代器使用前后底层指针位置发生了改变,换句话说就是开辟了新的空间,指针指向了新的地址,而迭代器没有更新从而导致迭代器失效。

而List并不会扩容,也不会开辟新的连续的空间,所以对于插入来说无从谈起迭代器失效,而erase是会导致迭代器失效的,因为删除了该位置的对象,迭代器底层指针成为野指针,但并不会影响其他迭代器,只需要重新赋值即可,比如设计为删除当前迭代器位置对象,并指向下一位置:

// 删除pos位置的节点,返回该节点的下一个位置
iterator erase(iterator pos)
{
    assert(pos != end());//list是带头双向循环链表,当pos是end()位置时,证明没有可删除的节点了

    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;

    delete cur;
    return next;
}

4.->操作符的重写

->操作符的重写是一个特例,大家只需要记住即可,因为这是STL设计者故意设计为这样的。

Ptr operator->()//为什么返回的是地址??
{
    return &_node->_data;
}

那放在实际的场景中我们使用一下看看: 

struct AA
{
    int _a1;
    int _a2;

    AA(int a1 = 1, int a2 = 1)
        :_a1(a1)
        , _a2(a2)
    {}
};

void test_list5()
{
    list<AA> lt;
    AA aa1;
    lt.push_back(aa1);

    lt.push_back(AA());

    AA aa2(2, 2);
    lt.push_back(aa2);

    lt.push_back(AA(2, 2));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << it->_a1 << ":" << it->_a2 << endl;
        //这里打印的是_a2的内容并不是_a2的地址
        ++it;
    }
    cout << endl;
}

正常来讲这里本来是应该有两个->的,第一个箭头是it->去调用重载的operator->返回AA* 的指针,第二个箭头是AA* 的指针去访问对象当中的成员变量_a2。

cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;//实际

但是为了程序可读性,所以编译器做了特殊识别处理,省略了一个箭头。 


5.模拟实现源码

#pragma once

#include<iostream>
#include<assert.h>

namespace F
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _data;
        ListNode(const T& val = T())
            :_next(nullptr)
            ,_prev(nullptr)
            ,_data(val)
        {}
    };


    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class __list_iterator
    {
    public:
        typedef ListNode<T> Node;
        typedef __list_iterator<T, Ref, Ptr> Self;
        Node* _node;
        __list_iterator(Node* x)
            :_node(x)
        {}

        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;
            return tmp;
        }
        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Self& operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }
        bool operator==(const Self& s)
        {
            return _node == s._node;
        }
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
    public:
        ///
        // List的构造
        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }
        list()
        {
            empty_init();
        }
        list(int n, const T& value = T())
        {
            empty_init();
            while (n--)
            {
                push_back(value);
            }
        }

        list(const list<T>& l)
        {
            empty_init();
            for (const auto& e : l)
            {
                push_back(e);
            }
        }
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }

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


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

        ///
        // List Capacity
        size_t size()const
        {
            size_t count = 0;
            const_iterator it = begin();
            while (it != end())
            {
                ++count;
                ++it;
            }
            return count;
        }
        bool empty()const
        {
            return _head->_next == _head;
        }


        
        // List Access
        T& front()
        {
            return *begin();
        }
        const T& front()const
        {
            return *begin();
        }
        T& back()
        {
            return *(--end());
        }
        const T& back()const
        {
            return *(--end());
        }


        
        // List Modify
        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的节点
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(val);

            prev->_next = newnode;
            newnode->_next = cur;
            newnode->_prev = prev;
            cur->_prev = newnode;

            //return iterator(newnode);
            return newnode;//单参数的构造函数支持隐式类型转换
        }
        // 删除pos位置的节点,返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos != end());//list是带头双向循环链表,当pos是end()位置时,证明没有可删除的节点了

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;

            delete cur;
            return next;
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        void swap(list<T>& l)
        {
            std::swap(_head, l._head);
        }
    private:
        Node* _head;
    };
};

模拟实现的主要目的在于学习优秀的代码,比如这里适配器的使用、优秀的框架设计。

注意为了迭代器统一使用:

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

这样我们就可以不需要知道迭代器的底层是如何实现的,只需要调用迭代器的接口就可以了,从而实现了通用的目的。


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

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

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

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

相关文章

  • 【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)
  • [C++]:12:模拟实现list

    1.节点结构: 1.SGI下的节点通过两个结构体实现。 2.基础的链表节点只包括前驱指针和后继指针。 3.链表节点去继承基础链表节点,新增节点数据。 4.优化掉指针类型带模板参数。 2.节点构造函数: 1.节点本身在这个地方是没有构造函数的。 2.观察下面的链表的结构和链表的

    2024年01月22日
    浏览(43)
  • 【C++】list的模拟实现

    list为任意位置插入删除的容器,底层为带头双向循环链表 begin() 代表第一个结点,end()代表最后一个结点的下一个 1. list_node 类设计 C++中,Listnode作为类名,而next和prev都是类指针,指针引用成员时使用-,而对象引用成员时使用 . 通过显示实例化,将两个类指针指定类型为T

    2024年02月02日
    浏览(44)
  • 《C++ list的模拟实现》

    本文主要介绍list容器的模拟实现 list示意图: 首先需要定义一个节点 的结构体 我们之前所理解的是:迭代器理解为像指针一样的东西,但是在list中有些不同 我们可以来观察一下STL源码中大佬是怎么封装的: 我们可以看到,只有一个成员,那就是一个结点的指针node,link_

    2024年02月07日
    浏览(42)
  • C++:list使用以及模拟实现

    list是一个类模板,加类型实例化才是具体的类 。 list是可以 在任意位置进行插入和删除 的序列式容器。 list的 底层是双向循环链表结构 ,链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 与其他序列式容器相比, list最大的

    2024年02月11日
    浏览(39)
  • 【C++学习手札】模拟实现list

    ​                                                        🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 : リナリア—まるりとりゅうが                                            

    2024年02月05日
    浏览(56)
  • C++ STL->list模拟实现

    list list文档 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。 list与forward_list非常相似:最主

    2024年02月20日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包