list的使用和模拟实现

目录

1.list的介绍及使用

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

2.为什么使用迭代器?

3.list的模拟实现

3.1完整代码

3.2代码解析

4.list与vector的对比


1.list的介绍及使用

1.1 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 list的使用

list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。以下为list中一些常见的重要接口

1.2.1 list的构造

构造函数

接口说明

list (size_type n, const value_type& val = value_type())

构造的list中包含n个值为val的元素

list ()

构造空的list

list (const list& x)

拷贝构造函数

list (InputIterator first, InputIterator last)

用两个迭代器[firs, last)区间中的元素构造list

1.2.2 list iterator的使用

此处,可暂时将迭代器理解成一个指针,该指针指向list中的某个节点

函数声明

接口说明

begin+end

返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin+rend

返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin的前一个位置

1. beginend为正向迭代器,对迭代器执行++操作,迭代器向后移动
2. rbegin(end)rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

1.2.3 list capacity

函数声明

接口说明

empty

检查list是否为空,是返回true,否则返回false

size

返回list中有效节点的个数

1.2.4 list element access

函数声明

接口声明

front

返回list的第一个节点中值的引用

back

返回list的最后一个节点中值的引用

1.2.5 list modifiers

函数声明

接口说明

push_front

在list首元素前插入值为val的元素

pop_front

删除list中第一个元素

push_back

在list尾部插入值为val的元素

pop_back

删除list中最后一个元素

insert

在list position位置的元素

erase

删除list position位置的元素

swap

交换两个list中的元素

clear

清空list中的有效元素

2.为什么使用迭代器?

容器类使用迭代器进行访问和遍历的主要原因包括以下几点:

  1. 抽象数据结构访问接口:通过迭代器,容器类可以提供一种统一的、抽象的方法来访问和操作容器中的元素。这样,无论容器内部的数据结构是什么,用户都可以使用相同的方式来访问和操作元素,提高了代码的可复用性和可维护性。
  2. 封装容器的内部实现细节:容器的内部实现可能采用各种不同的数据结构,例如数组、链表、树等。通过迭代器,容器可以隐藏内部实现细节,只提供迭代器的接口给用户使用,从而保护容器内部数据的完整性和安全性。
  3. 支持灵活的遍历方式:迭代器提供了多种灵活的遍历方式,例如正向遍历、反向遍历、随机遍历等。这使得用户可以根据实际需求选择最适合的遍历方式,提高了代码的灵活性和效率。
  4. 方便的算法和函数库使用:许多算法和函数库都是基于迭代器的,例如STL中的算法库、boost库等。通过使用迭代器,可以方便地在容器上应用这些算法和函数,提高了开发效率和代码的重用性。

综上所述,使用迭代器可以提供一种统一的、抽象的方法来操作容器中的元素,封装容器的内部实现细节,提供灵活的遍历方式,并支持方便的算法和函数库的使用。这使得容器的访问和遍历更加方便、灵活和高效

3.list的模拟实现

3.1完整代码

//ReverseIterator.h
#define _CRT_SECURE_NO_WARNINGS 1namespace bit
{template<class Iterator, class Ref, class Ptr>//Ref表示引用类型,Ptr表示指针类型struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;//重命名Iterator _it;//成员ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;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) const{return _it != s._it;}};
}
//list.h
#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include <assert.h>
#include "ReverseIterator.h"namespace bit
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(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;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._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 ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){//return _head->_next;//C++单参数类型支持隐式转换return iterator(_head->_next);//这两种写法是一样的}iterator end(){//return _head;//C++单参数类型支持隐式转换//虽然两种写法都是一样的,不过这种写法能更加明确的告诉我们返回的是迭代器类型的对象return iterator(_head);//匿名对象}const_iterator begin() const{//return _head->_next;//C++单参数类型支持隐式转换return const_iterator(_head->_next);//这两种写法是一样的}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}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);}_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;*///第二种写 -- 复用insert函数insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;--_size;delete cur;return next;//因为迭代器失效问题所以要返回下一个迭代器//为什么失效?因为删除之后迭代器原来的指向失效,需要返回下一个节点作为新的迭代器}size_t size(){return _size;}private:Node* _head;size_t _size;};struct A{A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};
}
//main.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <list>
using namespace std;
#include "list.h"void Print(const bit::list<int>& lt)
{bit::list<int>::const_iterator it = lt.begin();while (it != lt.end()){//(*it)++;cout << *it << " ";++it;}cout << endl;
}void test_list1()
{bit::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//因为链表的底层不一样,所以我们需要对其iterator进行封装然后重载运算符bit::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;Print(lt);
}void test_list2()
{bit::list<bit::A> lt;lt.push_back(bit::A(1, 1));lt.push_back(bit::A(2, 2));lt.push_back(bit::A(3, 3));lt.push_back(bit::A(4, 4));bit::list<bit::A>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;
}void test_list3()
{bit::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.push_back(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_front();lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;
}void test_list4()
{bit::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);bit::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;bit::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;
}void test_list5()
{bit::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//bit::list<int> lt1(lt);//for (auto e : lt1)//{//	cout << e << " ";//}//cout << endl;bit::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}void test_list6()
{bit::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);bit::list<int>::iterator it = lt.begin();while (it != lt.end()){if (*it == 2){it = lt.erase(it);}cout << *it << " ";++it;}cout << endl;
}int main()
{test_list6();return 0;
}

3.2代码解析

4.list与vector的对比

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

vector

list

底层结构

动态顺序表,一段连续空间

带头节点的双向循环链表

随机访问

支持随机访问,访问某个元素效率O(1)

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

插入和删除

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

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

空间利用率

底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高

底层节点动态开辟,小节点容易造成内存碎片,空间利用率低缓存利用率低

迭代器

原生态指针

对原生态指针(节点指针)进行封装

迭代器失效

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

插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响

使用场景

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

需要大量插入和删除操作,不关心随机访问

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据-玩转数据-Flink-Transform

一、Transform 转换算子可以把一个或多个DataStream转成一个新的DataStream.程序可以把多个复杂的转换组合成复杂的数据流拓扑. 二、基本转换算子 2.1、map&#xff08;映射&#xff09; 将数据流中的数据进行转换, 形成新的数据流&#xff0c;消费一个元素并产出一个元素…

iOS开发-WebRTC本地直播高分辨率不显示画面问题

iOS开发-WebRTC本地直播高分辨率不显示画面问题 在之前使用WebRTC结合ossrs进行推流时候&#xff0c;ossrs的播放端无法看到高分辨率画面问题。根据这个问题&#xff0c;找到了解决方案。 一、WebRTC是什么 WebRTC是什么呢&#xff1f; WebRTC (Web Real-Time Communicatio…

【学习FreeRTOS】第4章——FreeRTOS任务创建与删除

1.任务创建和删除的API函数 任务的创建和删除本质就是调用FreeRTOS的API函数 动态方式创建任务——xTaskCreate()静态方式创建任务——xTaskCreateStatic()删除任务——vTaskDelete() 动态创建任务&#xff1a;任务的任务控制块以及任务的栈空间所需的内存&#xff0c;均由 F…

[Kubernetes]Kubeflow Pipelines - 基本介绍与安装方法

1. 背景 近些年来&#xff0c;人工智能技术在自然语言处理、视觉图像和自动驾驶方面都取得不小的成就&#xff0c;无论是工业界还是学术界大家都在惊叹一个又一个的模型设计。但是对于真正做过算法工程落地的同学&#xff0c;在惊叹这些模型的同时&#xff0c;更多的是在忧虑如…

【论文阅读】Deep Instance Segmentation With Automotive Radar Detection Points

基于汽车雷达检测点的深度实例分割 一个区别&#xff1a; automotive radar 汽车雷达 &#xff1a; 分辨率低&#xff0c;点云稀疏&#xff0c;语义上模糊&#xff0c;不适合直接使用用于密集LiDAR点开发的方法 &#xff1b; 返回的物体图像不如LIDAR精确&#xff0c;可以…

Redis追本溯源(四)集群:主从模式、哨兵模式、cluster模式

文章目录 一、主从模式1.主从复制——全量复制2.主从复制——增量复制 二、哨兵模式1.实时监控与故障转移2.Sentinel选举领导者 三、cluster模式1.三种分片方案2.cluster模式 Redis 有多种集群搭建方式&#xff0c;比如&#xff0c;主从模式、哨兵模式、Cluster 模式。 一、主…

15.4 【Linux】可唤醒停机期间的工作任务

15.4.1 什么是 anacron anacron 并不是用来取代 crontab 的&#xff0c;anacron 存在的目的就在于我们上头提到的&#xff0c;在处理非24 小时一直启动的 Linux 系统的 crontab 的执行&#xff01; 以及因为某些原因导致的超过时间而没有被执行的调度工作。 其实 anacron 也是…

DERT:End-to-End Object Detection with Transformers

文章目录 摘要1、简介2、相关工作2.1、集合预测2.2、Transformer与并行解码2.3、目标检测 3、DETR模型3.1、目标检测集合预测损失3.2、DETR架构 4、实验4.1、与Faster R-CNN的对比4.2、消融4.3、分析4.4、用于全景分割的DETR 5、结论附录 AA.1、初步:多头注意层A.2、损失A.3、详…

Attacks in NLP

一、 Introduction NLP对抗攻击是人工智能对抗攻击的一个重要的组成部分&#xff0c;但是最近几年才逐渐开始兴起&#xff0c;究其原因在于NLP对抗攻击与传统computer vision或者audio对抗攻击有很大的不同&#xff0c;主要在于值空间的连续性&#xff08;CV、audio&#xff0…

SpringCloud整体架构概览

什么是SpringCloud 目标 协调任何服务&#xff0c;简化分布式系统开发。 简介 构建分布式系统不应该是复杂的&#xff0c;SpringCloud对常见的分布式系统模式提供了简单易用的编程模型&#xff0c;帮助开发者构建弹性、可靠、协调的应用程序。SpringCloud是在SpringBoot的基…

【Wamp】安装 | 局域网内设备访问

安装教程&#xff1a; https://wampserver.site/article/1.html 下载 https://www.wampserver.com/en/ 安装路径上不能有中文 安装好之后图标呈绿色 放入网页文件 将网页文件放置于wamp文件夹的www子文件夹 例如&#xff1a;\Wamp\program\www 修改http端口 WAMP服务器…

C# 使用FFmpeg.Autogen对byte[]进行编解码

C# 使用FFmpeg.Autogen对byte[]进行编解码&#xff0c;参考&#xff1a;https://github.com/vanjoge/CSharpVideoDemo 入口调用类&#xff1a; using System; using System.IO; using System.Drawing; using System.Runtime.InteropServices; using FFmpeg.AutoGen;namespace F…

虚拟世界探索:科技之下的未来可能性

随着科技的飞速发展&#xff0c;人们对于虚拟世界的憧憬和探索也日益加深。虚拟世界&#xff0c;那是一个超越现实的概念&#xff0c;一个充满想象力和创造力的领域。然而&#xff0c;虚拟世界究竟有可能实现吗&#xff1f;这是一个引人深思的问题。 虚拟世界&#xff0c;首先让…

激光切割机的操作中蛙跳技术是什么意思

其实&#xff0c;蛙跳技术就是指在激光切割机运行的过程中&#xff0c;机器换位置的方式。打个比方&#xff0c;你刚刚在这儿把孔1切好了&#xff0c;接下来就得跑到那儿把孔2切了。 在这个过程中&#xff0c;激光切割机就像是一只青蛙&#xff0c;要从一个位置跳到另一个位置。…

机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性

机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性 引言回顾&#xff1a;收敛速度&#xff1a;次线性收敛二次上界引理 梯度下降法在凸函数上的收敛性收敛性定理介绍证明过程 引言 本节将介绍梯度下降法在凸函数上的收敛性。 回顾&#xff1a; 收敛速度&#xff1a;次…

数据结构 | 二叉树的应用

目录 一、解析树 二、树的遍历 一、解析树 我们可以用解析树来表示现实世界中像句子或数学表达式这样的构造。 我们可以将((73)*(5-2))这样的数学表达式表示成解析树。这是完全括号表达式&#xff0c;乘法的优先级高于加法和减法&#xff0c;但因为有括号&#xff0c;所以在…

【Linux进阶之路】进程(上)

文章目录 前言一、操作系统加载过程二、进程1.基本概念2.基本信息①运行并观察进程②创建子进程③僵尸与孤儿进程&#xff08;父子进程衍生出来的问题&#xff09;1. 僵尸进程&#xff08;Zombie状态&#xff09;2. 孤儿进程 3.基本状态①操作系统的状态&#xff08;统一&#…

5.利用matlab完成 符号矩阵的转置和 符号方阵的幂运算(matlab程序)

1.简述 Matlab符号运算中的矩阵转置 转置向量或矩阵 B A. B transpose(A) 说明 B A. 返回 A 的非共轭转置&#xff0c;即每个元素的行和列索引都会互换。如果 A 包含复数元素&#xff0c;则 A. 不会影响虚部符号。例如&#xff0c;如果 A(3,2) 是 12i 且 B A.&#xff0…

【C++】红黑树模拟实现插入功能(包含旋转和变色)

红黑树模拟实现并封装为map和set 前言正式开始红黑树概念红黑树基本要求大致框架树节点树 调整红黑树使其平衡第一种&#xff1a;cur红&#xff0c;p红&#xff0c;g黑&#xff0c;u存在且为红第二种&#xff1a;cur红&#xff0c;p红&#xff0c;g黑&#xff0c;u不存在或为黑…

CentOS7安装Maven详细教程

&#x1f60a; 作者&#xff1a; Eric &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_47316183?typeblog &#x1f389; 主题&#xff1a;CentOS7安装Maven详细教程 ⏱️ 创作时间&#xff1a; 2023年08月06日 第一步&#xff1a;上传或下载安装包&#x…