STL中list的模拟实现

目录

list模拟实现

list节点

list的push_back()函数

list的迭代器操作（非const）

list的迭代器操作（const）

list迭代器const 非const优化

list的insert()函数

list的erase()函数

list的pop_back() push_front() pop_front()

list的clear()函数

list的empty()_Init函数与构造函数

list的拷贝构造

list的析构函数

list的赋值运算符重载

list的initializer_list

 项目文件

4.list与vector的对比

list模拟实现

list节点

首先看节点：list底层是一个带头双向循环链表

template <class T>
class list_Node{
public:
    T _data;
    list_Node<T>* _prev;
    list_Node<T>* _next;
    
    list_Node(const T& data)
    :_data(data),
    _prev(nullptr),
    _next(nullptr)
    {
        
    }
};
template <class T>
class list{
public:
    typedef list_Node<T> Node;
    list(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }

private:
    Node* _head;
}; 
}

list的push_back()函数

void push_back(const T& x){
    Node* newnode = new Node(x);
    Node* tail = _head->_prev;
    
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
    //insert(end(), x);
}

list的迭代器操作（非const）

list在物理上空间不是连续的，因此不可以像vector一样使用

typedef Node* iterator

Node* 不符合遍历的行为

List_iterator封装Node*

再通过重载运算符控制它的行为

因此这里我们可以使用一个类来封装使用

template <class T>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    T& operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    T* operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

注意： T* operator->()的意义，比如下面的例子

    struct Pos{
        int _x;
        int _y;
        
        Pos(int x = 0,int y = 0)
        :_x(x),
        _y(y)
        {
            
        }
    };
    
    nanyi::list<Pos> ls2;
    ls2.push_back(Pos(100,200));
    ls2.push_back(Pos(300,400));
    ls2.push_back(Pos(500,600));
    
    nanyi::list<Pos>::iterator it1 = ls2.begin();
    while (it1 != ls2.end()) {
        //cout << (*it1)._x << ":" << (*it1)._y << endl;
        // 为了可读性，省略了一个->
        cout << it1->_x << ":" << it1->_y << endl;
        //cout << it1.operator->()->_row << ":" << it1.operator->()->_col << endl;
        
        ++it1;
    }
    cout << endl;
    return 0;

list类中

iterator begin(){
    //iterator it(_head->_next);
	//return it;
    return iterator(_head->_next);
}

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

list的迭代器操作（const）

const迭代器不能在普通迭代器前加const修饰，比如这种情况

const迭代器的目标是 迭代器本身可以修改，指定的内容不能修改，类似const T* p

一旦加了不可以使用++it

因此我们重新写一个const类进行封装，我们只需改变解引用即可，使得指向内容不能修改

template <class T>
class const_List_iterator{
public:
    typedef list_Node<T> Node;
    typedef const_List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    const_List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    const T& operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    const T* operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

list类中

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

代码是没有问题的，但是我们也可以发现，这样非常的冗余 有些函数是没有变化的，确多写了一遍，有没有什么办法能解决这种冗余呢？

他们的区别主要是返回参数不同，返回是否有const对象

因此我们可以增加模版参数，让编译器完成任务

list迭代器const 非const优化

template <class T,class Ref,class Ptr>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    Ref operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    Ptr operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

list的insert()函数

    iterator insert(iterator pos , const T& x){
        Node* cur = pos._node;
        Node* newnode = new Node(x);
        Node* prev = cur->_prev;
        
        newnode->_next = cur;
        newnode->_prev = prev;
        prev->_next = newnode;
        cur->_prev  = newnode;
        return iterator(newnode);
    }

由于不牵涉扩容问题 这里不存在迭代器失效

 

list的erase()函数

    iterator erase(iterator pos){
        assert(pos);
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;
        // prev cur next
        
        prev->_next = next;
        next->_prev = prev;
        delete cur;
        cur = nullptr;
        return iterator(next);
    }

这里存在迭代器失效，因此我们和库里一样返回下一个节点迭代器

list的pop_back() push_front() pop_front()

    void pop_back(){
        erase(--end());
    }
    
    void push_front(const T& x){
        insert(begin(), x);
    }
    
    void pop_front(){
        erase(begin());
    }

list的clear()函数

    void clear(){
        auto it = begin();
        while (it != end()) {
            it = erase(it);
            //不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
        }
    }

list的empty()_Init函数与构造函数

由于我们经常使用申请头节点，因此我们把头节点封装成一个函数，便于调用

    void empty_Init(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }
    list(){
        empty_Init();
    }

list的拷贝构造

如果我们不显示写拷贝构造 ，那么编译器会默认生成一个浅拷贝

浅拷贝生成的ls2，与ls1的地址相同，对ls1操作也会对ls2有影响

因此我们需要显示的写拷贝构造

    //拷贝构造
    list(const list<T>& ls){
        empty_Init();
        for (const auto& e : ls) {
            //范围for不确定类型，加引用
            push_back(e);
        }
        
    }

 

list的析构函数

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

list的赋值运算符重载

    //ls2 = ls1
    list<T>& operator=(list<T> ls){
        std::swap(_head, ls._head);
        return *this;
    }

list的initializer_list

可以将花括号内容，直接赋值给对象

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

 项目文件

//
//  list.hpp
//  List
//
//  Created by 南毅 on 2024/5/28.
//

#include <iostream>
using namespace std;

namespace nanyi {
template <class T>
class list_Node{
public:
    T _data;
    list_Node<T>* _prev;
    list_Node<T>* _next;
    
    list_Node(const T& data)
    :_data(data),
    _prev(nullptr),
    _next(nullptr)
    {
        
    }
};

template <class T,class Ref,class Ptr>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    Ref operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    Ptr operator->(){
        return &(_node->_data);
    }
public:
    Node* _node;
    
};

//template <class T>
//class const_List_iterator{
//public:
//    typedef list_Node<T> Node;
//    typedef const_List_iterator Self;
//    
//    //不需要写析构函数，这个节点又不是这个类的
//    //一个类一般不写析构，也就不需要显示写深拷贝
//    const_List_iterator(Node* node)
//    :_node(node)
//    {
//        
//    }
//    
//    //日期类返回一个日期，那么迭代器返回一个迭代器
//    //++it
//    Self& operator++(){
//        _node = _node->_next;
//        return *this;
//    }
//    //--it
//    Self& operator--(){
//        _node = _node->_prev;
//        return *this;
//    }
//    //it++
//    Self operator++(int)//加参数 区分前置后置
//    {
//        Self tmp(*this);
//        _node = _node->_next;
//        return tmp;
//    }
//    //it--
//    Self operator--(int){
//        Self tmp(*this);
//        _node = _node->_prev;
//        return tmp;
//    }
//    
//    
//    const T& operator*(){
//        return _node->_data;
//    }
//    
//    bool operator!=(const Self& it){
//        return _node != it._node;
//    }
//    
//    bool operator==(const Self& it){
//        return _node == it._node;
//    }
//    
//    const T* operator->(){
//        return &(_node->_data);
//    }
//private:
//    Node* _node;
//    
//};

template <class T>
class list{
public:
    typedef list_Node<T> Node;
    typedef List_iterator<T,T&,T*> iterator;
    typedef List_iterator<T,const T&,const T*> const_iterator;
    //typedef const_List_iterator<T> const_iterator;
    void empty_Init(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }
    list(){
        empty_Init();
    }
    

    void clear(){
        auto it = begin();
        while (it != end()) {
            it = erase(it);
            //不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
        }
    }
    //拷贝构造
    list(const list<T>& ls){
        empty_Init();
        for (const auto& e : ls) {
            push_back(e);
        }
        
    }
    
    //析构
    ~list(){
        clear();
        delete _head;
        _head = nullptr;
    }
    
    void push_back(const T& x){
//        Node* newnode = new Node(x);
//        Node* tail = _head->_prev;
//        
//        tail->_next = newnode;
//        newnode->_prev = tail;
//        newnode->_next = _head;
//        _head->_prev = newnode;
        
        insert(end(), x);
    }
    
    void pop_back(){
        erase(--end());
    }
    
    void push_front(const T& x){
        insert(begin(), x);
    }
    
    void pop_front(){
        erase(begin());
    }
    
    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);
    }
    
    iterator insert(iterator pos , const T& x){
        Node* cur = pos._node;
        Node* newnode = new Node(x);
        Node* prev = cur->_prev;
        
        newnode->_next = cur;
        newnode->_prev = prev;
        prev->_next = newnode;
        cur->_prev  = newnode;
        return iterator(newnode);
    }
    
    iterator erase(iterator pos){
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;
        // prev cur next
        
        prev->_next = next;
        next->_prev = prev;
        delete cur;
        cur = nullptr;
        return iterator(next);
    }
    
    //ls2 = ls1
    list<T>& operator=(list<T> ls){
        std::swap(_head, ls._head);
        return *this;
    }
    
    list (initializer_list<T> il){
        empty_Init();
        for (const auto& e : il) {
            push_back(e);
        }
    }
public:
    Node* _head;
};
}

4.list与vector的对比

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

 

 

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

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

相关文章

数据结构：希尔排序

数据结构：希尔排序

文章目录 前言一、排序的概念及其运用二、常见排序算法的实现 1.插入排序2.希尔排序总结 前言 排序在生活中有许多实际的运用。以下是一些例子&#xff1a; 购物清单&#xff1a;当我们去超市购物时&#xff0c;通常会列出一份购物清单。将购物清单按照需要购买的顺序排序&…
阅读更多...
【STM32F103】HC-SR04超声波测距

【STM32F103】HC-SR04超声波测距

【STM32F103】HC-SR04超声波测距 一、HC-SR041、工作原理2、其他参数及时序图 二、代码编写思路三、HAL配置四、代码实现五、实验结果 前言 本次实验主要实现用stm32f103HC-SR04实现超声波测距&#xff0c;将测距数值通过串口上传到上位机串口助手 一、HC-SR04 1、工作原理 (…
阅读更多...
String类型的二维数组怎么写

String类型的二维数组怎么写

今天做题遇到一个问题&#xff1a;就是需要写String类型的二维数组时&#xff0c;我蒙圈了。后来查了资料发现&#xff0c;String类型的二维数组其实是由若干个一维数组构成的。 1.先初始化一个二维数组&#xff1a;List<List<String>> list new ArrayList<&g…
阅读更多...
登录校验及全局异常处理器

登录校验及全局异常处理器

登录校验 会话技术 会话:用户打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束.在一次会话中可以包含多次请求和响应会话跟踪:一种维护浏览器状态的方法,服务器需要识别多次请求是否来自于同一浏览器,以便在同一次会话请求间共享数据会话跟踪方案 客户端…
阅读更多...
MT8781安卓核心板_MTK联发科Helio G99核心板规格参数

MT8781安卓核心板_MTK联发科Helio G99核心板规格参数

MT8781安卓核心板采用先进的台积电6纳米级芯片生产工艺&#xff0c;配备高性能Arm Cortex-A76处理器和Arm Mali G57 GPU&#xff0c;加上LPDDR4X内存和UFS 2.2存储&#xff0c;在处理速度和数据访问速度上都有着出色的表现。 MT8781还支持120Hz显示器&#xff0c;无需额外的DSC…
阅读更多...
Transformer模型学习(1)

Transformer模型学习(1)

Transformer模型&#xff0c;它自2017年被引入以来&#xff0c;已成为处理语言任务的主流技术。Transformer模型不仅在多个语言处理任务上取得了优异的成绩&#xff0c;而且还因为它的设计极大地推动了后续模型的发展&#xff0c;如今广泛应用于聊天机器人、翻译软件和文本生成…
阅读更多...
CS的下载+内网穿透

CS的下载+内网穿透

CS的下载 纵向渗透&#xff1a;NC 瑞士军刀菜刀是一个hyyp协议 NC是TCP NC连接后没有任何回显 先受控房 nc.exe -l -p 12345 然后攻击方 nc.exe ip port 12345 扫描端口 上传和 nc.exe 同一目录下的文件 跳板机工具和NC的实际操作以及Termite联合管理 和nc是一样的…
阅读更多...
2024年生成式AI使用趋势报告

2024年生成式AI使用趋势报告

生成式AI技术及产品发展概况 人工智能技术奇点降临&#xff0c;搜索成为大模型技术落地的“首站” 过去几十年&#xff0c;人工智能长期鲜有突破性的发展&#xff0c;直至2022年AI大模型技术奇点的出现&#xff0c;使得AI能力发生了颠覆性的变化&#xff0c;人工智能受到了前…
阅读更多...
cdo | 常用命令

cdo | 常用命令

整理一下平时经常会使用的cdo命令 如何来更改netcdf数据中的变量名呢&#xff1f; 假设我现在有一个sst月平均数据,希望将里面的变量名称sst修改为sst_new netcdf oisst_monthly { dimensions:lat 180 ;lon 360 ;time UNLIMITED ; // (476 currently)nbnds 2 ; variable…
阅读更多...
利用“记忆化搜索“解斐波那契数

利用“记忆化搜索“解斐波那契数

一、题目描述 求第 n 个斐波那契数。 二、 利用"记忆化搜索"解斐波那契数 什么是记忆化搜索&#xff1f;记忆化搜索就是带有备忘录的递归。 我们先来看一下使用递归来解斐波那契数的这个过程&#xff0c;假设求第5个斐波那契数F(5)。 由图可见&#xff0c;要重复计…
阅读更多...
【mysql数据库】mycat中间件

【mysql数据库】mycat中间件

MyCat 简介 Mycat 是数据库 中间件 。 1、 数据库中间件 中间件 是一类连接软件组件和应用的计算机软件&#xff0c; 以便于软件各部件之间的沟通 。 例子 Tomcat web 中间件 。 数据库 中间件 连接 java 应用程序和数据库 2、 为什么要用 Mycat ① Java 与数据库紧耦合 …
阅读更多...
Halcon 光度立体 缺陷检测

Halcon 光度立体 缺陷检测

一、概述 halcon——缺陷检测常用方法总结&#xff08;光度立体&#xff09; - 唯有自己强大 - 博客园 (cnblogs.com) 上周去了康耐视的新品发布会&#xff0c;我真的感觉压力山大&#xff0c;因为VM可以实现现在项目中的80% 的功能&#xff0c;感觉自己的不久就要失业了。同时…
阅读更多...
基于Python的校园预约打印网站的实现

基于Python的校园预约打印网站的实现

基于Python的校园预约打印网站的实现 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat、Maven 系统功能实现 注册 新用户首先要进行注册信息填写&#xff0c;填写完成以后进行登录即可使用此网站 打印社 分别有…
阅读更多...
vue3 前端实现导出下载pdf文件

vue3 前端实现导出下载pdf文件

这样的数据实现导出 yourArrayBufferOrByteArray 就是后端返回数据 // 创建Blob对象const blob new Blob([new Uint8Array(res)], { type: application/pdf })// 创建一个表示该Blob的URLconst url URL.createObjectURL(blob);// 创建一个a标签用于下载const a document.cr…
阅读更多...
使用Redis缓存实现短信登录逻辑，手机验证码缓存，用户信息缓存

使用Redis缓存实现短信登录逻辑，手机验证码缓存，用户信息缓存

引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 加配置 spring:redis:host: 127.0.0.1 #redis地址port: 6379 #端口password: 123456 #密码…
阅读更多...
三十二篇：转化决策为行动：探索决策支持系统的深层价值

三十二篇：转化决策为行动：探索决策支持系统的深层价值

转化决策为行动&#xff1a;探索决策支持系统的深层价值 1. DSS的精髓&#xff1a;定义与核心功能 1.1 定义与作用 在现代商业的快速演变中&#xff0c;决策支持系统&#xff08;Decision Support Systems, DSS&#xff09;已成为企业获得竞争优势的重要工具。DSS是一种利用先…
阅读更多...
全国产飞腾模块麒麟信安操作系统安全漏洞

全国产飞腾模块麒麟信安操作系统安全漏洞

1、背景介绍 目前在全国产飞腾模块上部署了麒麟信安操作系统&#xff0c;经第三方机构检测存在以下漏洞 操作系统版本为 内核版本为 openssh版本为 2、openssh CBC模式漏洞解决 首先查看ssh加密信息 nmap --script "ssh2*" 127.0.0.1 | grep -i cbc 可以通过修改/…
阅读更多...
Elasticsearch 认证模拟题 - 5

Elasticsearch 认证模拟题 - 5

一、题目 .在集群上有一个索引 food_ingredient&#xff0c;搜索需要满足以下要求&#xff1a; 三个字段 manufacturer&#xff0c;name&#xff0c;brand 都能匹配到文本 cake mix高亮 字段 name&#xff0c;并加标签排序&#xff0c;对字段 brand 正序&#xff0c;_score 降…
阅读更多...
快手发布大模型产品“可图”，超20种创新AI图像玩法限免上线

快手发布大模型产品“可图”，超20种创新AI图像玩法限免上线

近日&#xff0c;快手自研大模型产品“可图”&#xff08;Kolors&#xff09;正式对外开放&#xff0c;支持文生图和图生图两类功能&#xff0c;已上线20余种AI图像玩法。目前&#xff0c;用户可以通过“可图大模型”官方网站和微信小程序&#xff0c;免费使用各项AI图像功能。…
阅读更多...
12k Star！Continue：Github Copilot 开源本地版、开发效率和隐私保护兼得、丰富功能、LLM全覆盖！

12k Star！Continue：Github Copilot 开源本地版、开发效率和隐私保护兼得、丰富功能、LLM全覆盖！

原文链接&#xff1a;&#xff08;更好排版、视频播放、社群交流、最新AI开源项目、AI工具分享都在这个公众号&#xff01;&#xff09; 12k Star&#xff01;Continue&#xff1a;Github Copilot 开源本地版、开发效率和隐私保护兼得、丰富功能、LLM全覆盖&#xff01; &…
阅读更多...
最新文章

Copyright @ 2022~2023