【C++】list的模拟实现

🌇个人主页：平凡的小苏
📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。
🛸C++专栏：C++内功修炼基地
> 家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问，感谢你们的转发！ 关注我，关注我，关注我，你们将会看到更多的优质内容！！

在这里插入图片描述

一、list的介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

  2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素

二、迭代器的功能分类

1、单向迭代器：只能++，不能–。例如单链表，哈希表；

2、双向迭代器：既能++也能–。例如双向链表；

3、随机访问迭代器：能+±-，也能+和-。例如vector和string。

迭代器是内嵌类型（内部类或定义在类里）

三、list的迭代器失效问题

对于list：插入操作是不会失效的，但是删除操作是会失效的，因为删除操作会进行释放节点

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，

因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删

除节点的迭代器，其他迭代器不会受到影响。

错误代码：

void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
        //其赋值
            l.erase(it); 
        ++it;
    }
}

修改正确的代码：

void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it++); // it = l.erase(it);
    }
}

四、list的迭代器模拟实现

4.1普通迭代器

迭代器的主要作用：解引用获取数据、++、–

我在模拟实现string、vector时都是用的原生指针，没有将迭代器用类进行封装，这是为了简易化，但是STL标准库也是用用类封装了迭代器。而我在模拟实现list迭代器时，不能用原生指针了，因为list的节点地址时不连续的，不能使用原生指针。

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->_val;
        }

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

        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;
        }
        bool operator!=(const Self &it)const
        {
            return _node != it._node;
        }

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

在这里插入图片描述

这是用类封装了迭代器的作用，while循环的判断条件在迭代器的类里面进行了运算符重载，解引用也进行了运算符重载 否则自定义类型是做不到用运算符的，这样做的目的是为了我们不暴露迭代器的底层实现给使用者，用统一的方式像指针一样就能访问迭代器，这就是封装的强大之处。

4.2 const迭代器

const迭代器的错误写法：

typedef __list_iterator<T> iterator;
const list<T>::iterator it=lt.begin();

因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。（重载operator++()为const operator++()也不行,因为const版本++还是改变不了）

正确写法：想实现const迭代器，不能在同一个类里面动脑筋，需要再写一个const版本迭代器的类。

//用类封装const迭代器
template <class T>
struct __list_const_iterator
{
    typedef list_node<T> node;
    //用节点的指针进行构造
    __list_const_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器运算符的重载
    const T& operator*()const
    {
        return _pnode->_data;
    }
    __list_const_iterator<T>& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    {
        //return _pnode->_next;//返回类型错误的
        _pnode = _pnode->_next;
        return *this;//返回的是迭代器
    }
    __list_const_iterator<T>& operator--()
    {
        _pnode = _pnode->_prev;
        return *this;
    }
    bool operator!=(const __list_const_iterator<T>& it)const
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封装一个节点的指针
};
 
typedef __list_const_iterator<T> const_iterator;

这样写会让代码显得冗余。STL库中是通过类模板多给一个参数来实现，这样，同一份类模板就可以生成两种不同的类型的迭代器（以下为仿STL库的模拟实现）：

在这里插入图片描述

4.3 反向迭代器

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

template <class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;

    ReverseIterator(Iterator it)
        :_it(it)
        {}

    Ref operator*()
    {
        Iterator tmp = _it;
        --tmp;
        return *tmp;
    }

    Ptr operator->()
    {
        return &operator*();
    }

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

    Self& operator--()
    {
        ++_it;
        return *this;
    }
    bool operator!=(const Self& rit)const
    {
        return _it != rit._it;
    }

    bool operator==(const Self& rit)const
    {
        return _it == rit.it;
    }
private:
    Iterator _it;
};

五、list和vector区别

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

1.底层结构

list:带头结点的双向循环链表

vector:动态顺序表，一段连续空间

2.迭代器失效

list:带头结点的双向循环链表

vector:在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效

3.使用场景

list：大量插入和删除操作，不关心随机访问

vector：需要高效存储，支持随机访问，不关心插入删除效率

4.随机访问

list：不支持随机访问，访问某个元素效率O(N)

vector：支持随机访问，访问某个元素效率****O(1)

5.插入和删除

list：任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)

vector：任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低

六、list的模拟实现源码

#pragma once
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
namespace sqy
{
    template <class T>
    struct list_node
    {
        list_node(const T &val = T())
            : _prev(nullptr), _next(nullptr), _val(val)
        {
        }

        list_node<T> *_prev;
        list_node<T> *_next;
        T _val;
    };
    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->_val;
        }

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

        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;
        }
        bool operator!=(const Self &it)const
        {
            return _node != it._node;
        }

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

    template <class Iterator, class Ref, class Ptr>
    class ReverseIterator
    {
    public:
        typedef ReverseIterator<Iterator, Ref, Ptr> Self;

        ReverseIterator(Iterator it)
            :_it(it)
        {}

        Ref operator*()
        {
            Iterator tmp = _it;
            --tmp;
            return *tmp;
        }

        Ptr operator->()
        {
            return &operator*();
        }

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

        Self& operator--()
        {
            ++_it;
            return *this;
        }
        bool operator!=(const Self& rit)const
        {
            return _it != rit._it;
        }

        bool operator==(const Self& rit)const
        {
            return _it == rit._it;
        }
    private:
        Iterator _it;
    };

    template <class T>
    class list
    {
        typedef list_node<T> Node;

    public:
        typedef __list_iterator<T, T &, T *> iterator;
        typedef __list_iterator<T, const T &, const T *> const_iterator;
        typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_head);
        }

        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }

        void empty_init()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            _size = 0;
        }

        void swap(list<T> &lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        // list<T> &operator=(list<T> lt)
        // {
        //     if(this != &lt)
        //     {
        //         clear();
        //         for(auto& t : lt)
        //         {
        //             push_back(t);
        //         }
        //     }
        // }

        //现代写法赋值运算符重载
        list<T> &operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

        list()
        {
            empty_init();
        }

        list(const list<T> &lt)
        {
            empty_init();
            for (auto &t : lt)
            {
                push_back(t);
            }
        }

        ~list()
        {
            clear();
            delete _head;
            _size = 0;
        }
        void push_back(const T &x)
        {
            // Node * tail = _head->_prev;
            // Node * newnode = new Node(x);
            // tail->_next = newnode;
            // newnode->_prev = tail;
            // newnode->_next = _head;
            // _head->_prev = newnode;
            // ++_size;
            insert(end(), x);
        }
        void push_front(const T &x)
        {
            // Node * tail = _head->_prev;
            // Node * newnode = new Node(x);
            // tail->_next = newnode;
            // newnode->_prev = tail;
            // newnode->_next = _head;
            // _head->_prev = newnode;
            // ++_size;
            insert(begin(), x);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }
        iterator insert(iterator pos, const T &x)
        {
            Node *newnode = new Node(x);
            Node *prev = pos._node->_prev;
            newnode->_prev = prev;
            prev->_next = newnode;
            newnode->_next = pos._node;
            pos._node->_prev = newnode;
            _size++;
            return pos;
        }

        iterator erase(iterator pos)
        {
            assert(_size != 0);
            Node *prev = pos._node->_prev;
            Node *tail = pos._node->_next;
            Node *cur = pos._node;
            prev->_next = tail;
            tail->_prev = prev;
            delete cur;
            --_size;
            return pos;
        }

        // 链表小接口
        bool empty() const
        {
            return _head->_next == _head;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it);
                ++it;
            }
        }
        size_t size() const
        {
            return _size;
        }

    private:
        Node *_head;
        size_t _size = 0; // 元素个数
    };

    void Test_list1()
    {
        list<int> lt;

        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        // list<int>::iterator it1 = lt2.begin();
        // while (it1 != lt2.end())
        // {
        //     cout << *it1 << " ";
        //     ++it1;
        // }
        // cout << endl;

        // list<int>::reverse_iterator rit = lt.rbegin();
        // while(rit != lt.rend())
        // {
        //     cout << *rit <<endl;
        //     ++rit;
        // }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/41970.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数据结构（王道）——数据结构之 二叉树的存储结构

数据结构（王道）——数据结构之 二叉树的存储结构

一、顺序存储 静态顺序存储 顺序存储的二叉树结构特性&#xff1a; 顺序存储的非完全二叉树特性 不完全二叉树的可能会浪费大量空间&#xff0c;所以一般顺序存储二叉树比较少用。 图示为什么很少用顺序存储来存二叉树 顺序存储的二叉树总结&#xff1a; 二、链式存储 二叉链表…
阅读更多...
集群基础4——haproxy负载均衡mariadb

集群基础4——haproxy负载均衡mariadb

文章目录 一、环境说明二、安装配置mariadb三、安装配置haproxy四、验证 一、环境说明 使用haproxy对mysql多机单节点进行负载均衡。 主机IP角色安装服务192.168.161.131后端服务器1mariadb&#xff0c;3306端口192.168.161.132后端服务器2mariadb&#xff0c;3306端口192.168.…
阅读更多...
springboot @Async 异步调用接口处理数据

springboot @Async 异步调用接口处理数据

Async 异步背景 新增的数据需要分发给下游业务系统&#xff0c;由于下游业务系统状态未知&#xff0c;所以需要异步发送数据给下游业务系统。 系统生效按钮--->controller新增-->异步调用servcie--->数据集成 在springboot框架中实现步骤 首先在启动类上加上Enable…
阅读更多...
JMeter接口测试之文件上传

JMeter接口测试之文件上传

最近用JMeter做接口测试&#xff0c;频繁遇到了文件上传的接口&#xff0c;与其他一般接口的处理方式不一样&#xff0c;想着分享下&#xff0c;希望能给测试同学一点启发。 文章将围绕三个部分进行展开&#xff1a; 一、用户场景 二、接口请求参数 三、JMeter脚本编写步骤 …
阅读更多...
leetcode 216. 组合总和 III

leetcode 216. 组合总和 III

2023.7.18 做了这道题 组合 之后&#xff0c;本题就很容易了&#xff0c;依旧是使用回溯。 其中需要统计一下总和sum值&#xff0c;以此来判断能否加入到最终数组中。下面上代码&#xff1a; class Solution { public:vector<vector<int>> ans;vector<int> …
阅读更多...
linux查看ipynb文件

linux查看ipynb文件

linux查看ipynb文件 使用jupyter查看 使用jupyter查看 安装 pip install jupyter添加配置好的环境到jupyter notebook的kernel中&#xff1a; python -m ipykernel install --user --name mmdet --display-name "mmdet"运行jupyter notebook &#xff08;在ipynb…
阅读更多...
MQTT 订阅选项的使用

MQTT 订阅选项的使用

在 MQTT 发布/订阅模式介绍这篇博客中&#xff0c;我们已经了解到&#xff0c;我们需要先向服务端发起订阅&#xff0c;才能从服务端接收对应的消息。如果说订阅时指定的主题过滤器决定了服务端将向我们转发哪些主题下的消息&#xff0c;那么订阅选项则是允许我们进一步定制服务…
阅读更多...
从零搭建vue+electron桌面应用

从零搭建vue+electron桌面应用

从零搭建vueelectron桌面应用 一、准备工作1.全局下载electron2.全局下载vue脚手架3.创建vue项目&#xff08;这里用的是vue2版本&#xff09;4.安装打包插件5.安装electron-builder&#xff0c;安装后可以直接生成主进程的配置文件6.在vue.config.js中添加以下配置 二、运行项…
阅读更多...
idea 自定义类注释模板和方法模板，无警告

idea 自定义类注释模板和方法模板，无警告

背景&#xff1a;idea&#xff1a;IntelliJ IDEA 2023.1.3 (Ultimate Edition) 效果&#xff1a;&#xff08;主要是没无参&#xff0c;不会换行&#xff09; 类&#xff1a; /** * author sss* date ${DATE} on ${TIME}* desc $NAME*/# 完全复制上面的&#xff0c;删除这一行…
阅读更多...
Git #01 操作记录

Git #01 操作记录

本篇内容 0. 前期配置1. 仓库1.1 上传本地代码到远程仓库 0. 前期配置 请提前配置好 git 的全局用户名&#xff1a; # xin&#xff1a;账号名 $ git config --global user.name "xin" # xin163.com&#xff1a;账号绑定的邮箱地址 $ git config --global user.emai…
阅读更多...
vue注意点：$attrs、$slots！插槽

vue注意点：$attrs、$slots！插槽

$attrs 当父组件给子组件传值&#xff0c;子组件并没有接收数据时&#xff0c;此时数据在$attrs中可以拿到&#xff0c;并且如果子组件不需要使用数据&#xff0c;而孙组件需要&#xff0c;则可以直接v-bind"$attrs"传给孙。 <-- 父组件 --> <div><…
阅读更多...
目标检测算法：FPN思想解读

目标检测算法：FPN思想解读

目标检测算法&#xff1a;FPN思想解读 说明 ​ FPN算法一种方法/思想&#xff0c;在许多的模型架构中都经常采用&#xff0c;也是提高模型精度的重要方法。 免责申明 ​ 有误写/错写/错误观点/错误解读&#xff0c;或者大家有其它见解&#xff0c;都可以在评论区指出&#xff0…
阅读更多...
0719_rasa网站的一些介绍

0719_rasa网站的一些介绍

it’s not a bot, it’s your brand rasa is the leading open generative conversational ai platform for creating and managing ai assistants at scale. learn more talk with sales top enterprises trust rasa american express adobe dell accenture report ho…
阅读更多...
scrapy---爬虫界的django

scrapy---爬虫界的django

1介绍 scrapy架构 引擎(EGINE)&#xff1a;引擎负责控制系统所有组件之间的数据流&#xff0c;并在某些动作发生时触发事件。大总管&#xff0c;负责整个爬虫数据的流动 调度器(SCHEDULER)用来接受引擎发过来的请求, 压入队列中, 并在引擎再次请求的时候返回. 可以想像成一个U…
阅读更多...
Debian 系统安装中文输入法-iTOP3588开发板

Debian 系统安装中文输入法-iTOP3588开发板

Debian 系统烧写完成之后&#xff0c;并没有中文输入功能。本文档将介绍如何安装 ibus pinyin 输入法。 首先安装 fcitx 对应的工具&#xff0c;如下图所示&#xff1a; apt-get install fcitx fcitx-tools fcitx-config* fcitx-frontend* fcitx-module* fcitx-ui-* presage …
阅读更多...
uniapp editor组件 如何上传图片

uniapp editor组件 如何上传图片

需求&#xff1a;我们在使用uniapp的editor组件时&#xff0c;主要是为了保持输入内容的格式。里面的文字可以有颜色、粗体、排列样式&#xff0c;可以插入图片。就像下面这样。 一、如何处理图片&#xff0c;好让它在 rich-text组件中显示 &#xff1f; 逻辑&#xff1a;我们…
阅读更多...
ARP解析MAC地址的全过程（ARP的工作机制）

ARP解析MAC地址的全过程（ARP的工作机制）

目录 ARP解析MAC地址的过程&#xff1a; 源码等资料获取方法 以太网环境下&#xff0c;同一个网段的主机之间需要互相知道对方的MAC地址&#xff0c;才能访问。 TCP/IP协议栈从上层到下层的封装过程中&#xff0c;第三层封装需要知道目的IP&#xff0c;第二层封装需要知道目…
阅读更多...
计算机毕业论文选题推荐|软件工程｜信息管理｜数据分析｜系列一

计算机毕业论文选题推荐|软件工程｜信息管理｜数据分析｜系列一

文章目录 导文题目导文 计算机毕业论文选题推荐|软件工程｜信息管理 （***语言）==使用其他任何编程语言 例如：基于（***语言）门窗账务管理系统的设计与实现 得到：基于JAVA门窗账务管理系统的设计与实现 基于vue门窗账务管理系统的设计与实现 等等 题目 基于requests多线程…
阅读更多...
Scala(二)

Scala(二)

第2章 变量和数据类型 2.1 注释 Scala注释使用和Java完全一样。 注释是一个程序员必须要具有的良好编程习惯。将自己的思想通过注释先整理出来&#xff0c;再用代码去体现。 1&#xff09;基本语法 &#xff08;1&#xff09;单行注释&#xff1a;// &#xff08;2&#xff0…
阅读更多...
动态规划——删除并获得点数

动态规划——删除并获得点数

题目链接 leetcode在线oj题——删除并获得点数 题目描述 给你一个整数数组 nums &#xff0c;你可以对它进行一些操作。 每次操作中&#xff0c;选择任意一个 nums[i] &#xff0c;删除它并获得 nums[i] 的点数。之后&#xff0c;你必须删除 所有 等于 nums[i] - 1 和 nums…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站