STL-list的使用及其模拟实现

      在C++标准库中,list 是一个双向链表容器,用于存储一系列元素。与 vector 和 deque 等容器不同,list 使用带头双向循环链表的数据结构来组织元素,因此list插入删除的效率非常高。

list的使用

list的构造函数

list迭代器

list的成员函数

list的模拟实现

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

    list_node(const T& x=T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(x)
    {}
};
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* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    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;
    }

};

/*template<class T>
struct _list_const_iterator {
    typedef list_node<T> node;
    typedef _list_const_iterator<T> self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    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;
    }

};*/
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 _list_const_iterator<T> const_iterator;
    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
    /*reverse_iterator rbegin()
    {
        return reverse_iterator(_head->_prev);
    }

    reverse_iterator rend()
    {
        return reverse_iterator(_head);
    }*/
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    iterator begin() {
        //iterator it(_head->next);
        //return it;
        return iterator(_head->_next);
    }
    const_iterator begin() const{
        return const_iterator(_head->_next);
    }
    iterator end() {
        //iterator it(_head);
        //return it;
        return iterator(_head);
    }
    const_iterator end() const{
        return const_iterator(_head);
    }
    void empty_init() {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    list() {
        empty_init();
    }

    template <class Iterator>
    list(Iterator first, Iterator last)
    {
        empty_init();
        while (first != last) 
        {
            push_back(*first);
            ++first;
        }
    }
    // lt2(lt1)
    /*list(const list<T>& lt) {
        empty_init();
        for (auto e : lt) {
            push_back(e);
        }
    }*/
    void swap(list<T>& tmp) {
        std::swap(_head, tmp._head);
    }
    list(const list<T>& lt) {
        empty_init();

        list<T> tmp(lt.begin(), lt.end());
        swap(tmp);
    }
    //lt1=lt3
    list<T>& operator=(list<T> lt) {
        swap(lt);
        return *this;
    }
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }
    void clear() {
        iterator it = begin();
        while (it != end()) {
            //it = erase(it);
            erase(it++);
        }
    }
    void push_back(const T& x) {
        /*node* tail = _head->_prev;
        node* new_node = new node(x);

        tail->_next = new_node;
        new_node->_prev = tail;
        new_node->_next = _head;
        _head->_prev = new_node;*/
        insert(end(), x);

    }
    void push_front(const T& x) {
        insert(begin(), x);
    }
    void pop_back() {
        erase(--end());
    }
    void pop_front() {
        erase(begin());
    }
    void insert(iterator pos,const T& x) {
        node* cur = pos._node;
        node* prev = cur->_prev;

        node* new_node = new node(x);
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;
    }
    //会导致迭代器失效 pos
    iterator erase(iterator pos, const T& x=0) {
        assert(pos != end());
        node* prev = pos._node->_prev;
        node* next = pos._node->_next;
        prev->_next = next;
        next->_prev = prev;
        delete pos._node;

        return iterator(next);
    }
private:
    node* _head;
};

迭代器和成员函数的模拟实现

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* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    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;
    }

};

/*template<class T>
struct _list_const_iterator {
    typedef list_node<T> node;
    typedef _list_const_iterator<T> self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    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;
    }

};*/

迭代器共有两种:

1.迭代器要么就是原生指针
2.迭代器要么就是自定义类型对原生指针的封装,模拟指针的行为

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时,编译器就会实例化出一个普通迭代器对象;当我们使用const迭代器时,编译器就会实例化出一个const迭代器对象。这样就不用专门写两种不同类型的迭代器,泛型编程减少了代码的复用,提高了效率。

list的构造函数

void empty_init() {
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
}
list() {
    empty_init();
}

list的拷贝构造

template <class Iterator>
list(Iterator first, Iterator last)
{
    empty_init();
    while (first != last) 
    {
        push_back(*first);
        ++first;
    }
}

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

    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

list的析构函数

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

赋值运算符重载

//lt1=lt3
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

list的插入和删除


void push_back(const T& x) {
    /*node* tail = _head->_prev;
    node* new_node = new node(x);

    tail->_next = new_node;
    new_node->_prev = tail;
    new_node->_next = _head;
    _head->_prev = new_node;*/
    insert(end(), x);

}
void push_front(const T& x) {
    insert(begin(), x);
}
void pop_back() {
    erase(--end());
}
void pop_front() {
    erase(begin());
}
void insert(iterator pos,const T& x) {
    node* cur = pos._node;
    node* prev = cur->_prev;

    node* new_node = new node(x);
    prev->_next = new_node;
    new_node->_prev = prev;
    new_node->_next = cur;
    cur->_prev = new_node;
}
//会导致迭代器失效 pos
iterator erase(iterator pos, const T& x=0) {
    assert(pos != end());
    node* prev = pos._node->_prev;
    node* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;

    return iterator(next);
}

清空list中所有元素

void clear() {
    iterator it = begin();
    while (it != end()) {
        //it = erase(it);
        erase(it++);
    }
}

list迭代器失效

      迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

      解决方法:可以使用 erase 函数的返回值,它会返回一个指向下一个有效元素的迭代器。

list和vector区别

底层实现:

      list 通常是一个双向链表,每个节点都包含了数据和指向前一个和后一个节点的指针。这使得在任何位置进行插入和删除操作都是高效的,但随机访问和内存占用可能相对较差。
     vector 是一个动态数组,元素在内存中是连续存储的。这使得随机访问非常高效,但插入和删除操作可能需要移动大量的元素,效率较低。

插入和删除:

     在 list 中,插入和删除操作是高效的,无论是在容器的任何位置还是在开头和结尾。这使得 list 在需要频繁插入和删除操作时非常适用。
     在 vector 中,插入和删除操作可能需要移动元素,特别是在容器的中间或开头。因此,当涉及大量插入和删除操作时,vector 可能不如 list 效率高。

随机访问:

list 不支持随机访问,即不能通过索引直接访问元素,必须通过迭代器逐个遍历。
vector 支持随机访问,可以通过索引快速访问元素,具有良好的随机访问性能。

迭代器失效:

在 list 中,插入和删除操作不会导致迭代器失效,因为节点之间的关系不会改变。
在 vector 中,插入和删除操作可能导致内存重新分配,从而使原来的迭代器失效。

综上所述,如果你需要频繁进行(头部和中间)插入和删除操作,而对于随机访问性能没有特别高的要求,可以选择list;如果想要随机访问以及尾插和尾删vector是更好的选择。 

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

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

相关文章

【Interconnection Networks 互连网络】Dragonfly Topology 蜻蜓网络拓扑

蜻蜓拓扑 Dragonfly Topology 1. 拓扑参数2. Topology Description 拓扑描述3. Topology Variations 拓扑变体 蜻蜓拓扑 Dragonfly Topology 1. 拓扑参数 Dragonfly拓扑参数&#xff1a; N N N: 网络中终端(terminal)的总数量 p p p: 连接到每个路由器的终端数量 a a a: 每…

Go语言并发控制

channel // cancelFn 数据通道关闭通知退出 func cancelFn(dataChan chan int) {for {select {case val, ok : <-dataChan:// 关闭data通道时&#xff0c;通知退出// 一个可选是判断data指定值时退出if !ok {fmt.Printf("Channel closed &#xff01;&#xff01;&…

Rest接口/Nginx日志记录和采集

文章目录 一、Rest接口日志二、Nginx日志三、采集日志四、夜莺查看Nginx日志五、夜莺查看Rest接口日志 一、Rest接口日志 记录日志字典定义 接口URL接口名称,类别,入参全记录,出参全记录,入参字段1:中文名1/入参字段2:中文名2,出参字段1:中文名1/test/api/login账户登录,登录…

java-单列集合List详解

一、List概述 ​​​​​​​List 接口继承自 Collection 接口。这意味着所有 List 类型的对象都是 Collection 类型的对象&#xff0c;它们共享 Collection 接口中定义的所有方法。 List集合的特点&#xff1a; 1、有序&#xff1a;存和取得元素顺序一致 2、有索引&#xf…

Java- Object根父类

在java中&#xff0c;所有的类都有一个公共的父类&#xff0c;这个java.lang.Object类 * * * Object所有类的根&#xff0c;成为超类。 1.证明Object是根 public class A_Object01 {public static void main(String[] args) {//证明Object是根//基本数据类型int a 0;Object…

【硬十宝典】——1.4【基础知识】电源完整性——理解与设计

定义&#xff1a; 电源完整性&#xff08;Power integrity&#xff09;简称PI&#xff0c;是确认电源来源及目的端的电压及电流是否符合需求。 电源完整性在现今的电子产品中相当重要。有几个有关电源完整性的层面&#xff1a;芯片层面、芯片封装层面、电路板层面及系统层面。…

18-Echarts 配置系列之:数据集 dataset

简介&#xff1a; 数据集&#xff08;dataset&#xff09;是专门用来管理数据的组件。简化在每一个系列中设置数据&#xff0c;这一个配置是在Echarts4 中开始支持。 通过数据集配置&#xff0c;避免为每一个系列创建一个数据&#xff0c;避免格式转化的痛苦。 简单举例&…

开启智慧之旅,AI与机器学习驱动的微服务设计模式探索

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 &#x1f680; 转载自热榜文章&#x1f525;&#xff1a;探索设计模式的魅力&#xff1a;开启智慧…

2024年腾讯云免费服务器最新申请入口链接

腾讯云免费服务器申请入口 txybk.com/go/free 免费服务器可选轻量应用服务器和云服务器CVM&#xff0c;轻量配置可选2核2G3M、2核8G7M和4核8G12M&#xff0c;CVM云服务器可选2核2G3M和2核4G3M配置&#xff0c;腾讯云百科txybk.com分享2024年最新腾讯云免费服务器申请入口、限制…

YOLOv8操作指南-下载+配置环境

下载&#xff1a;github&#xff0c;进入搜索YOLOv8 就这个&#xff0c;点开 下载就可以了&#xff0c;然后解压一下 配置环境&#xff1a; 安装Pytorch 先看一下这个&#xff1a; 如果电脑有GPU的话&#xff1a; 判断自己电脑GPU&#xff1a;打开任务管理器 我的是英伟达3…

sherpa + ncnn 离线语音识别

目录结构 前言音视频格式转为wavsherpa-ncnn编译LinuxWindowswindows编译中遇到的问题问题“nmake -? failed with: no such file or directory”编译失败原因 成功编译截图 可执行程序说明模型下载语言识别测试LinuxWindows 参考文献 前言 小编需要实现离线音视频语言部分识…

vulfocus靶场couchdb 权限绕过 (CVE-2017-12635)

Apache CouchDB是一个开源数据库&#xff0c;专注于易用性和成为"完全拥抱web的数据库"。它是一个使用JSON作为存储格式&#xff0c;JavaScript作为查询语言&#xff0c;MapReduce和HTTP作为API的NoSQL数据库。应用广泛&#xff0c;如BBC用在其动态内容展示平台&…

完结撒花! java算法day60 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形 思路&#xff1a; 这道题和接雨水很像&#xff0c;不过有两点差别&#xff1a; 这道题需要找到一个位置前一个比他小的数和后一个比他小的数&#xff0c;而接雨水是找到前一个和后一个比他大的数。需要在原数组前后各补上0&#xff0c;防止忽略一些边缘…

Excel数据处理:高级筛选、查找定位、查找函数(VLOOKUP)

高级筛选 先去选中筛选区域 如果筛选的条件在同一行那么就是且的关系 如果筛选的条件不在同一行那么就是或的关系 查找定位空值 使用VLOOKUP函数

C语言中, 文件包含处理,#include< > 与 #include ““的区别

文件包含处理 指一个源文件可以将另外一个文件的全部内容包含进来 &#xff23;语言提供了#include命令用来实现文件包含的操作 #include< > 与 #include ""的区别 <> 表示系统直接按系统指定的目录检索 "" 表示系统先在 "" 指定…

PACS/RIS影像管理系统源码,医院影像科室PACS系统源码,三维医学影像系统源码 支持图像后处理与重建

PACS/RIS影像管理系统源码&#xff0c;支持图像后处理与重建 医院影像科室PACS系统源码&#xff0c;三维医学影像系统源码 PACS&#xff0c;全称为Picture Archiving and Communication Systems&#xff0c;中文意思是医学影像存档与通讯系统。它主要是应用在医院影像科室中&a…

java算法day4

删除链表的倒数第N个结点链表相交环形链表 删除链表的倒数第N个结点 解法&#xff1a;双指针&#xff08;快慢指针&#xff09; 首先一定要有删除结点的思想。所以这个题是用虚拟头结点比较方便。 先上模拟图&#xff0c;然后看流程&#xff1a; 这里后移根据不同的想法有不同…

java优先级队列(堆)详解

一、优先级概念 什么是优先级&#xff1a;比如女士优先&#xff0c;个子低的优先排到前面去&#xff0c;有一部分数据具备优先级&#xff0c;要以优先级的顺序将顺序存储起来。 前面介绍过队列&#xff0c;队列是一种先进先出(FIFO)的数据结构&#xff0c;但有些情况下&#…

OceanBase开发者大会2023届视频及PPT汇总

数据库技术趋势 我眼中的数据库技术 阳振坤OceanBase 首席科学家 观看视频 下载 PDF 未来&#xff0c;中国需要什么样的数据库&#xff1f; 周傲英华东师范大学副校长&#xff0c;CCF 会士 观看视频 下载 PDF 云原生技术趋势解读 Keith ChanCNCF 云原生计算基金会中国区总监 …

开发工具的使用

IDEA的安装与使用&常用快捷键 文章目录 IDEA的安装与使用&常用快捷键一、认识IntelliJ IDEA二、IDEA 的下载&卸载三、IEAD相关设置3.1 JDK的相关设置3.2 系统设置&#xff08;启动项/自动更新&#xff09;3.3 设置整体主题&#xff08;主题/字体/背景&#xff09;3…