C++ STL之list的使用及模拟实现

文章目录

  • 1. 介绍
  • 2. list类的使用
    • 2.1 list类对象的构造函数
    • 2.2 list类对象的容量操作
    • 2.3 list类对象的修改操作
    • 2.4 list类对象的访问及遍历操作
  • 3. list类的模拟实现

1. 介绍

英文解释：

在这里插入图片描述

也就是说：

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

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

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

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

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

图示：

在这里插入图片描述

想要具体了解其底层数据结构可以参照：线性表之双向链表

2. list类的使用

template < class T, class Alloc = allocator<T> > class list;

list 是类模板。使用其定义变量时，首先需要实例化。

例如：

实例化类型解释
list整型容器，每个元素的类型为 int。
list<char*>char* 指针容器，每个元素的类型为 char*。
list<vector>list 类模板嵌套实例化的容器，元素类型为 vector。

2.1 list类对象的构造函数

(constructor)构造函数代码功能说明
explicit list (const allocator_type& alloc = allocator_type());（默认构造函数）构造一个空的容器，没有任何元素。
explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());（填充构造函数）构造一个具有 n 个元素的容器。每个元素都是 val 的副本。
template <class InputIterator>
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());		（范围构造函数）构造一个与范围[first, last)中的元素数量相同的容器，每个元素都是从该范围中的相应元素构造而来，顺序相同。
list (const list& x);（拷贝构造函数）构造一个与 x 中的每个元素副本相同顺序的容器。

实例：

// constructing lists
#include <iostream>
#include <list>

int main()
{
    // 按照上述描述的顺序使用的构造函数
    std::list<int> first;                                // empty list of ints
    std::list<int> second(4, 100);                       // four ints with value 100
    std::list<int> third(second.begin(), second.end());  // iterating through second
    std::list<int> fourth(third);                       // a copy of third

    // the iterator constructor can also be used to construct from arrays:
    int myints[] = { 16,2,77,29 };
    std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    std::cout << "The contents of fifth are: ";
    for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
        std::cout << *it << ' ';

    std::cout << '\n';

    return 0;
}

输出结果：

在这里插入图片描述

2.2 list类对象的容量操作

函数名称代码功能说明
emptybool empty() const;返回 list 容器是否为空（即其大小是否为0）。
sizesize_type size() const;返回 list 容器中元素的个数。
max_sizesize_type max_size() const;返回 list 容器中可以容纳的最大元素的数量。

2.3 list类对象的修改操作

函数名称代码功能说明
assigntemplate <class InputIterator>
void assign (InputIterator first, InputIterator last);
void assign (size_type n, const value_type& val);		对 list 容器进行赋值，替换其当前内容，并相应地修改其大小。
push_frontvoid push_front (const value_type& val);在 list 容器开头插入一个新元素 val。
pop_frontvoid pop_front();删除 list 容器中第一个元素。
push_backvoid push_back (const value_type& val);在 list 容器最后插入一个新元素 val。
pop_backvoid pop_back();删除 list 容器中最后一个元素。
insertiterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);		在指定位置 position 之前插入新元素 val、n 个 val或者迭代器区间[first, last)范围的元素。
eraseiterator erase (iterator position);
iterator erase (iterator first, iterator last);		删除 position 位置的元素或者迭代器区间[first, last)范围的元素。
swapvoid swap (list& x);与另一个相同类型的 list 容器 x 交换内容。存在一个同名的非成员函数 swap，重载该算法的意义是优化交换时间。
resizevoid resize (size_type n, value_type val = value_type());改变容器的大小，使其包含 n 个元素。如果 n 小于当前容器的大小，则内容将被缩减为其前 n 个元素，并移除超出范围的元素。如果 n 大于当前容器的大小，则通过在末尾插入所需数量的元素来扩展内容，使其大小达到 n。如果指定了 val，则新元素将被初始化为 val 的副本；否则，它们将进行值初始化。
clearvoid clear();从 list 容器中移除所有元素，使容器的大小变为0。

2.4 list类对象的访问及遍历操作

函数名称代码功能说明
frontreference front();
const_reference front() const;		返回 list 容器中第一个元素的引用。
backreference back();
const_reference back() const;		返回 list 容器中最后一个元素的引用。

遍历操作

#include <iostream>
#include <list>

int main()
{
	std::list<int> lt(10, 100);

	// 1. 迭代器遍历
	for (std::list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
		std::cout << *it << " ";
	std::cout << '\n';

	// 2. 范围for遍历
	for (auto e : lt)
		std::cout << e << " ";
	std::cout << '\n';

	return 0;
}

运行结果：

在这里插入图片描述

解释

  1. 迭代器遍历：
  • 首先，通过lt.begin()获取列表的起始迭代器，lt.end()获取列表的结束迭代器。
  • 使用std::list<int>::iterator it定义一个迭代器变量，并将其初始化为列表的起始迭代器。
  • 使用迭代器变量it进行循环迭代，从列表的起始位置迭代到结束位置（不包括结束位置）。
  • 在循环中，通过*it访问当前迭代器指向的元素，并输出到标准输出流std::cout中。
  1. 范围for循环遍历：
  • 使用auto关键字和范围for循环语法，遍历列表lt中的每个元素。
  • 在每次迭代中，将当前元素赋值给变量e。
  • 在循环体内，输出变量e的值到标准输出流std::cout中。

3. list类的模拟实现

#pragma once
#include<iostream>
using namespace std;

namespace my_list
{   
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_pPre(nullptr)
            ,_pNext(nullptr)
            ,_val(val)
        {}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class List_iterator
    {
        typedef ListNode<T>* PNode;
        typedef List_iterator<T, Ref, Ptr> Self;
    public:
        List_iterator(PNode pNode = nullptr)
        {
            _pNode = pNode;
        }

        List_iterator(const Self& l)
        {
            _pNode = l._pNode;
        }

        Ref operator*()
        {
            return _pNode->_val;
        }

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

        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }

        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }

        bool operator==(const Self& l)
        {
            return _pNode == l._pNode;
        }
        
        PNode GetNode()
        {
            return _pNode;
        }

    private:
        PNode _pNode;
    };

    // 反向迭代器——对正向迭代器的接口进行包装
    template<class Iterator, class Ref, class Ptr>
    struct Reverse_iterator
    {
        Iterator _it;
        typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

        Reverse_iterator() {}

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

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

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

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

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

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

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

        bool operator!=(const Self& s)
        {
            return _it != s._it;
        }

        bool operator==(const Self& s)
        {
            return _it == s._it;
        }
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        typedef List_iterator<T, T&, T*> iterator;
        typedef List_iterator<T, const T&, const T&> const_iterator;
        typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

    public:
        
        ///
        // List Iterator
        iterator begin()
        {
            return _pHead->_pNext;
        }

        iterator end()
        {
            return _pHead;
        }
        
        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }

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

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

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

        const_reverse_iterator rbegin() const
        {
            return const_reverse_iterator(end());
        }

        const_reverse_iterator rend() const
        {
            return const_reverse_iterator(begin());
        }

        ///
        // List 构造/赋值
        list()
        {
            CreateHead();
        }

        list(int n, const T& value = T())
        {
            CreateHead();
            while (n--)
            {
                push_back(value);
            }
            _size = n;
        }

        list(int n, T& value = T())
        {
            CreateHead();
            while (n--)
            {
                push_back(value);
            }
            _size = n;
        }

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

        list(const list<T>& l)
        {
            CreateHead();
            for (auto it : l)
            {
                push_back(it);
                _size++;
            }
        }

        void swap(list<T>& l)
        {
            std::swap(this->_pHead, l._pHead);
            std::swap(this->_size, l._size);
        }
        
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }

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

        ///
        // List Capacity
        size_t size()const
        {
            return _size;
        }

        bool empty()const
        {
            return _size == 0;
        }


        
        // List Access
        T& front()
        {
            assert(!empty());
            return _pHead->_pNext->_val;
        }
       
        const T& front()const
        {
            assert(!empty());
            return _pHead->_pNext->_val;
        }

        T& back()
        {
            assert(!empty());
            return _pHead->_pPre->_val;
        }

        const T& back()const
        {
            assert(!empty());
            return _pHead->_pPre->_val;
        }


        
        // 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)
        {
            PNode tmp = new Node(val);
            PNode cur = pos.GetNode();
            PNode pre = cur->_pPre;
            tmp->_pNext = cur;
            tmp->_pPre = pre;
            pre->_pNext = tmp;
            cur->_pPre = tmp;
            _size++;
            return tmp;
        }

        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            PNode cur = pos.GetNode();
            PNode next = cur->_pNext;
            PNode pre = cur->_pPre;
            delete cur;
            pre->_pNext = next;
            next->_pPre = pre;
            _size--;
            return next;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        
    private:
        // 创建头结点
        void CreateHead()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead->_pPre = _pHead;
        }

        PNode _pHead;
        size_t _size = 0;
    };
};

注意

这里实现的反向迭代器类模板同样也可以适配到vector类和string类中。

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

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

相关文章

解决国内 github.com 打不开的准确方法

解决国内 github.com 打不开的准确方法

** 下载watt toolkit&#xff0c; 选择‘github’&#xff0c;点击‘一键加速’&#xff0c;很简单方便 **
阅读更多...
第137期 Oracle的数据生命周期管理（20240123）

第137期 Oracle的数据生命周期管理（20240123）

数据库管理137期 2024-01-23 第137期 Oracle的数据生命周期管理&#xff08;20240123&#xff09;1 ILM2 Heat Map3 ADO4 优点5 对比总结 第137期 Oracle的数据生命周期管理&#xff08;20240123&#xff09; 作者&#xff1a;胖头鱼的鱼缸&#xff08;尹海文&#xff09; Orac…
阅读更多...
（学习日记）2024.01.22：各类型占用字节 与 指针

（学习日记）2024.01.22：各类型占用字节 与 指针

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…
阅读更多...
SSM：Spring + Spring MVC + MyBatis 的整合

SSM：Spring + Spring MVC + MyBatis 的整合

SSM 前言整合 前言 在完成 Spring 、Spring MVC 与 MyBatis 基础知识的学习后&#xff0c;下面简单介绍 SSM 框架的整合使用。 整合 SSM&#xff0c;是 Java 开发中常用的一个 Web 框架组合&#xff0c;用于构建基于 Spring 和 MyBatis 的 Web 应用&#xff08; Spring MVC …
阅读更多...
Zabbix分布式监控系统

Zabbix分布式监控系统

实验过程 ps&#xff1a; 阿里云盘Xnode1获取 xnode1 https://www.alipan.com/s/HgLXfoeBWG2 提取码: eb70 1、xnode1克隆两台虚拟机并修改ip zabbix-server192.168.224.3 zabbix-agent192.168.224.4 2、修改主机名 [rootlocalhost ~]# hostnamectl set-hostname zabbix-se…
阅读更多...
旧衣服回收小程序开发

旧衣服回收小程序开发

随着人们的消费理念逐渐提升&#xff0c;每个家庭的闲置衣物每年就能够达到30公斤左右&#xff0c;这也促进了我国旧衣回收行业的发展。近几年我国的旧衣回收市场规模在300-400亿元&#xff0c;发展潜力较大。 旧衣回收行业是当下的环保型商业模式&#xff0c;商业价值较为可观…
阅读更多...
JavaScript递归函数如何匹配上下级id和pid的数据（for...of,foreach.reduce）

JavaScript递归函数如何匹配上下级id和pid的数据（for...of,foreach.reduce）

目录 一、for...of 二、forEach 三、reduce 递归函数是一种在编程中常用的方法&#xff0c;用于解决一些需要重复操作的问题。在JavaScript中&#xff0c;递归函数可以用来匹配上下级id和pid的数据结构&#xff0c;例如树形结构或者父子关系的数据。 一、for...of 首先…
阅读更多...
ARM安装与项目结构

ARM安装与项目结构

1. 安装环境 参考E:\peixunQianrushi\arm\ziliao\FS4412新版&#xff08;学生资料&#xff09;\环境相关资料 这边建议全部默认路径 安装注意事项&#xff1a; 1、在接下来的安装过程中&#xff0c;对于使用win10、win8的操作系统的用户&#xff0c;所有的安装请均以管理员身份…
阅读更多...
【渗透测试】nmap基本使用方法整理

【渗透测试】nmap基本使用方法整理

nmap作用介绍 nmap是一款工具&#xff0c;用于收集信息时使用。通过nmap可以快速的扫描目标的端口操作系统使用的服务等。以便于后续的渗透测试。 但是值得注意的是&#xff0c;nmap误报是个超正常的事情&#xff0c;还是要人为的去判断一下。 单机快速端口扫描 我们默认扫…
阅读更多...
P9568 [SDCPC2023] Computational Geometry 题解

P9568 [SDCPC2023] Computational Geometry 题解

P9568 [SDCPC2023] Computational Geometry 题解 感谢战学长的帮助。 解法 本题的关键是将多边形 Q Q Q 分割为两部分&#xff0c;一部分是由点 a , b , c a,b,c a,b,c 组成的三角形&#xff0c;另一部分是由从 b b b 到 c c c 这 k 1 k 1 k1 个点组成的凸多边形。注…
阅读更多...
回归问题波士顿房价预测

回归问题波士顿房价预测

线性回归API sklearn.linear_model.LinearRegression(fit_interceptTrue) 正规方程优化参数&#xff1a;fit_intercept&#xff0c;是否计算偏置属性&#xff1a;LinearRegression.coef_ &#xff08;回归系数&#xff09; LinearRegression.intercept_&#xff08;偏置&…
阅读更多...
2024.1.23 GNSS 零散知识 学习笔记

2024.1.23 GNSS 零散知识 学习笔记

1.天线种类 2.接收机 2.四大导航系统的介绍 3.卫星高度与轨道卫星种类 4.GNSS有哪些应用 5.在空间保持静⽌或匀速直线运动(⽆加速度)的坐标系称为惯性坐标系。 6.地⼼惯性坐标系实际上并没有满⾜能成为惯性坐标系的条件&#xff1a; ⾸先&#xff0c;地球及其质⼼都在围绕太阳…
阅读更多...
《WebKit 技术内幕》学习之九（2）： JavaScript引擎

《WebKit 技术内幕》学习之九（2）： JavaScript引擎

2　V8引擎 2.1　基础 V8是一个开源项目&#xff0c;也是一个JavaScript引擎的实现。它最开始是由一些语言方面的专家设计出来的&#xff0c;后被Google收购&#xff0c;成为了JavaScript引擎和众多相关技术的引领者。其目的很简单&#xff0c;就是为了提高性能。因为在当时之前…
阅读更多...
C++比较两个proto是否一样

C++比较两个proto是否一样

参考:https://stackoverflow.com/questions/3228107/google-protocol-buffers-compare/32351914#32351914 #include <google/protobuf/util/message_differencer.h>MessageDifferencer::Equals(msg1, msg2);
阅读更多...
dhcp服务器的ip池的待分配ip地址是否冲突的检测机制

dhcp服务器的ip池的待分配ip地址是否冲突的检测机制

看到有的资料说&#xff0c;dhcp服务器在分配ip地址时&#xff0c;要检测是否待分配的ip地址是否存在冲突&#xff0c;会向广播域发出&#xff0c;对应ip发出icmp的ping消息来验证是否冲突。特地用自己的公司的交换机验证一下&#xff0c;在交换机上镜像抓包观察一下。 wiresha…
阅读更多...
【C++】位图+布隆过滤器

【C++】位图+布隆过滤器

位图布隆过滤器 1.位图2.布隆过滤器 喜欢的点赞&#xff0c;收藏&#xff0c;关注一下把&#xff01; 1.位图 问: 给40亿个不重复的无符号整数&#xff0c;没排过序。给一个无符号整数&#xff0c;如何快速判断一个数是否在这40亿个数中。 可能你会想到下面这几种方式&#…
阅读更多...
【Python进阶编程】python编程高手常用的设计模式（持续更新中）

【Python进阶编程】python编程高手常用的设计模式（持续更新中）

Python编程高手通常熟练运用各种设计模式&#xff0c;这些设计模式有助于提高代码的可维护性、可扩展性和重用性。 以下是一些Python编程高手常用的设计模式&#xff1a; 1.单例模式&#xff08;Singleton Pattern&#xff09; 确保一个类只有一个实例&#xff0c;并提供全局…
阅读更多...
softmax回归实战-分类

softmax回归实战-分类

1.数据集 MNIST数据集 (LeCun et al., 1998) 是图像分类中广泛使用的数据集之一&#xff0c;但作为基准数据集过于简单。 我们将使用类似但更复杂的Fashion-MNIST数据集 (Xiao et al., 2017)。 import torch import torchvision from torch.utils import data from torchvisi…
阅读更多...
javaspringbootmysql开放实验室管理系统03361-计算机毕业设计项目选题推荐（附源码）

javaspringbootmysql开放实验室管理系统03361-计算机毕业设计项目选题推荐（附源码）

摘 要 随着社会的发展&#xff0c;社会的方方面面都在利用信息化时代的优势。互联网的优势和普及使得各种系统的开发成为必需。 本文以实际运用为开发背景&#xff0c;运用软件工程原理和开发方法&#xff0c;它主要是使用动态网页开发技术java作为系统的开发语言&#xff0c;M…
阅读更多...
如何把openwrt的ipk软件包安装到ubuntu上

如何把openwrt的ipk软件包安装到ubuntu上

前提&#xff1a;都是arm64的架构的软件包。 下载openwrt的ipk软件包 1. 从https://pkgs.org/ 查找下载软件包&#xff1a; 本文以swconfig软件包为例&#xff0c;下载swconfig和相关的依赖软件包&#xff1a; swconfig_12_aarch64_cortex-a72.ipk libuci20130104_2021-10-2…
阅读更多...
最新文章

Copyright @ 2022~2023