C++ std::list超详细指南:基础实践(手搓list)

目录

一.核心特性

1.双向循环链表结构

2.头文件:#include

3.时间复杂度

4.内存特性

二.构造函数

三.list iterator的使用

1.学习list iterator之前我们要知道iterator的区分

​编辑

 2.begin()+end()

3.rbegin()+rend() 

 四.list关键接口

1.empty()

2. size()

3.front()

4. back()

5.push_front()

6. pop_front()

7.push_back()

8. pop_back()

9.insert ()

10.erase()

11.swap()

12.clear()

五.list的迭代器失效

六.模拟实现list

1.List.h 

2.test.cpp

 七.list与vector的对比


一.核心特性


1.双向循环链表结构

每个节点包含前驱和后继指针

2.头文件#include <list>

3.时间复杂度

任意位置插入/删除:O(1)

随机访问:O(n)

排序:O(n log n)

4.内存特性

非连续内存存储

每个元素需要额外存储两个指针(前驱+后继)

内存占用 ≈ sizeof(T)2 + 2指针大小

二.构造函数


int main()
{list<T> lst1;            // 空链表list<T> lst2(n);         // n个默认初始化元素list<T> lst3(n, value);  // n个value副本list<T> lst4(begin, end);// 迭代器范围构造list<T> lst5(init_list); // 初始化列表 C++11list<T> lst6(lst4);      // 拷贝构造
}

三.list iterator的使用


1.学习list iterator之前我们要知道iterator的区分

功能上区分:

iterator普通迭代器
reverse_iterator反向迭代器
const_iterator只读迭代器
const_reverse_iterator只读反向迭代器

性质上区分:

名称代表容器支持操作
单向迭代器(ForwardIterator)Forward_list(单链表),unordered_map++
双向迭代器(BidirectionalIterator)list(链表),map,set++/--
随机迭代器(RandomAccessIterator)vector,string,deque++/--/+/-

通过底层结构决定可以实现哪些算法

比如算法库里的sort要求使用随机迭代器,list就无法使用这个算法

对于算法库里的reverse和find可以正常使用 

可以得知,功能是向上兼容得 

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

 2.begin()+end()

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

3.rbegin()+rend() 

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

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";  //4 3 2 1++it;}cout << endl;
  • begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  • rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

 四.list关键接口


1.empty()

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

	list<int> lt;cout<<lt.empty()<<endl;   //1lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.empty();    //0

2. size()

返回list中有效节点的个数

	list<int> lt;cout<<lt.size()<<endl;   //0lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.size();    //4

3.front()

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

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.front();    //1

4. back()

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

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.back();    //4

5.push_front()

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

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);    //5 1 2 3 4

6. pop_front()

删除list中第一个元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_front();    //2 3 4

7.push_back()

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

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);    //1 2 3 4 5

8. pop_back()

删除list中最后一个元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_back();    //1 2 3 

9.insert ()

在list position 位置中插入值为val的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::list<int>::iterator it;it=lt.begin();int k = 3;while (k--){++it;}lt.insert(it, 30); 1 2 3 30 4

10.erase()

删除list position位置的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::list<int>::iterator it;it=lt.begin();int k = 2;while (k--){++it;}lt.erase(it);  //1 2 4

11.swap()

交换两个list中的元素

	std::list<int> first(3, 100);   // 100 100 100std::list<int> second(5, 200);  // 200 200 200 200 200first.swap(second);   // 200 200 200 200 200

12.clear()

清空list中的有效元素

	std::list<int> mylist;mylist.push_back(1101);   //1101mylist.clear();mylist.push_back(2202);   //2202return 0;

五.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


1.List.h 

#pragma once  // 防止头文件重复包含
#include<assert.h>  // 断言检查// 实现双向链表及相关迭代器
class bit
{// 链表节点结构体模板template<class T>struct list_node{T _data;         // 节点存储的数据list_node<T>* _next; // 后继指针list_node<T>* _prev; // 前驱指针// 节点构造函数(默认构造空对象)list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};// 链表迭代器结构体模板(支持普通/const迭代器)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->_data; }// 成员访问操作符(返回数据指针)// 使得 it->member 等价于 (&it->)_data->memberPtr 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) const { return _node != s._node; }bool operator==(const self& s) const { return _node == s._node; }};// 链表类模板template <class T>class list{typedef list_node<T> Node; // 节点类型简写public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/  //两个代码相似度太高,所以通过增加模板参数实现// 迭代器类型定义(通过模板参数实现const重载)typedef list_iterator<T, T&, T*> iterator;          // 普通迭代器typedef list_iterator<T, const T&, const T*> const_iterator; // const迭代器// 获取起始迭代器(指向第一个有效节点)iterator begin() { return _head->_next; }// 获取结束迭代器(哨兵节点)iterator end() { return _head; }// const版本迭代器const_iterator begin() const { return _head->_next; }const_iterator end() const { return _head; }// 初始化哨兵节点(构建空链表)void empty_init() {_head = new Node;       // 申请头节点_head->_next = _head;   // 初始状态自环_head->_prev = _head;_size = 0;              // 大小置零}// 默认构造函数list() { empty_init(); }// 初始化列表构造(支持花括号初始化)list(std::initializer_list<T> il) {empty_init();for (auto& e : il) {   // 遍历列表插入元素push_back(e);}}// 拷贝构造函数(深拷贝)list(const list<T>& lt) {empty_init();for (auto& e : lt) {   // 遍历插入每个元素push_back(e);}}// 赋值运算符(拷贝交换惯用法)list<T>& operator=(list<T> lt) {swap(lt); // 交换资源return *this;}// 析构函数(清理节点)~list() {clear();        // 删除所有数据节点delete _head;   // 释放哨兵节点_head = nullptr;}// 清空链表(保留哨兵节点)void clear() {auto it = begin();while (it != end()) {   // 逐个删除节点it = erase(it);}}// 交换两个链表内容void swap(list<T>& lt) {std::swap(_head, lt._head); // 交换头指针std::swap(_size, lt._size);  // 交换大小}// 尾插(复用insert实现)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); //直接调用insert}// 头插void push_front(const T& x) { insert(begin(), x); }// 在pos位置前插入新节点iterator insert(iterator pos, const T& x) {Node* cur = pos._node;  // 当前节点Node* prev = cur->_prev; // 前驱节点Node* newnode = new Node(x); // 创建新节点// 调整指针链接newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;        // 更新大小return newnode; // 返回新节点位置}// 尾删void pop_back() { erase(--end()); }// 头删void pop_front() { erase(begin()); }// 删除pos位置节点(注意:原代码此处返回类型应为iterator)iterator erase(iterator pos) {assert(pos != end()); // 不能删除哨兵节点Node* prev = pos._node->_prev; // 前驱节点Node* next = pos._node->_next; // 后继节点// 调整链接关系prev->_next = next;next->_prev = prev;delete pos._node; // 释放节点--_size;          // 更新大小return next; // 返回下一位置的迭代器}// 获取元素数量size_t size() const { return _size; }// 判断是否为空bool empty() const { return _size == 0; }private:Node* _head;    // 哨兵头节点size_t _size;   // 元素个数};
};// 打印容器内容(泛型模板)
template<class Container>
void print_container(const Container& con) {// 使用const迭代器遍历(保证内容不被修改)// const iterator -> 迭代器本身不能修改// const_iterator -> 指向内容不能修改typename Container::const_iterator it = con.begin(); // typename指明依赖类型//auto it = con.begin();或者使用autowhile (it != con.end()) {std::cout << *it << " ";++it;}std::cout << std::endl;// 范围for遍历(C++11特性)for (auto e : con) {std::cout << e << " ";}std::cout << std::endl;
}

2.test.cpp

#include <iostream>
#include <list>
#include<algorithm>using namespace std;
#include"list.h"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;for (auto e : lt){cout << e << " ";}cout << endl;/*it = lt.begin();lt.erase(it + 3);*/// 不支持,要求随机迭代器//sort(lt.begin(), lt.end());string s("dadawdfadsa");cout << s << endl;sort(s.begin(), s.end());cout << s << endl;
}
void test_list3()
{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);for (auto e : lt){cout << e << " ";}cout << endl;auto it = lt.begin();int k = 3;while (k--){++it;}lt.insert(it, 30);for (auto e : lt){cout << e << " ";}cout << endl;int x = 0;cin >> x;it = find(lt.begin(), lt.end(), x);if (it != lt.end()){lt.erase(it);}for (auto e : lt){cout << e << " ";}cout << endl;
}
void test_list4()
{// 直接构造list<int> lt0({ 1,2,3,4,5,6 });// 隐式类型转换list<int> lt1 = { 1,2,3,4,5,6,7,8 };const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };print_container(lt1);
}int main()
{//test_list3();//test_list4();test_list1();}

 七.list与vector的对比

vectorlist
底 层 结 构动态顺序表,一段连续空间带头结点的双向循环链表
随 机 访 问支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素效率O(N)
插 入 和 删 除任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更
任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1)
空 间 利 用 率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭 代 器原生态指针对原生态指针(节点指针)进行封装
 
迭 代 器 失 效在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使 用 场 景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

 学到C++11时需要补充一些新的接口。

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

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

相关文章

【免费】2004-2017年各地级市进出口总额数据

2004-2017年各地级市进出口总额数据 1、时间&#xff1a;2004-2017年 2、来源&#xff1a;城市年鉴 3、指标&#xff1a;进出口贸易总额 4、范围&#xff1a;286个地级市 5、指标说明&#xff1a;进出口总额是指一个国家在特定时期内&#xff08;通常为一年&#xff09;所…

谈谈 undefined 和 null

*** 补充 null 和 ‘’

【第15届蓝桥杯】软件赛CB组省赛

个人主页&#xff1a;Guiat 归属专栏&#xff1a;算法竞赛真题题解 文章目录 A. 握手问题&#xff08;填空题&#xff09;B. 小球反弹&#xff08;填空题&#xff09;C. 好数D. R格式E. 宝石组合F. 数字接龙G. 爬山H. 拔河 正文 总共8道题。 A. 握手问题&#xff08;填空题&…

【计算机视觉】工业表计读数(2)--表计检测

1. 简介 工业表计&#xff08;如压力表、电表、气表等&#xff09;在工控系统、能源管理等领域具有重要应用。然而&#xff0c;传统人工抄表不仅工作量大、效率低&#xff0c;而且容易产生数据误差。近年来&#xff0c;基于深度学习的目标检测方法在工业检测中展现出极大优势&…

提示词工程(Prompt Engineering)

https://www.bilibili.com/video/BV1PX9iYQEry 一、懂原理&#xff0c;要知道 为什么有的指令有效&#xff0c;有的指令无效为什么同样的指令有时有效&#xff0c;又是无效怎么提升指令有效的概率 大模型应用架构师想什么&#xff1f; 怎样能更准确&#xff1f;答&#xff1…

从Instagram到画廊:社交平台如何改变艺术家的展示方式

从Instagram到画廊&#xff1a;社交平台如何改变艺术家的展示方式 在数字时代&#xff0c;艺术家的展示方式正在经历一场革命。社交平台&#xff0c;尤其是Instagram&#xff0c;已经成为艺术家展示作品、与观众互动和建立品牌的重要渠道。本文将探讨社交平台如何改变艺术家的…

Typora 使用教程(标题,段落,字体,列表,区块,代码,脚注,插入图片,表格,目录)

标题 一个#是一级标题, 2个#是二级标题, 以此类推, 最多可达六级标题 示例 输入#号和标题后回车即可 注意: #和标题内容之间需要存在空格(一个或多个均可), 没有空格就会变成普通文字 标题快捷键 Ctrl数字 1-6 可以快速调成对应级别的标题 (选中文本/把光标放在标题上再按…

关于deepseek R1模型分布式推理效率分析

1、引言 DeepSeek R1 采用了混合专家&#xff08;Mixture of Experts&#xff0c;MoE&#xff09;架构&#xff0c;包含多个专家子网络&#xff0c;并通过一个门控机制动态地激活最相关的专家来处理特定的任务 。DeepSeek R1 总共有 6710 亿个参数&#xff0c;但在每个前向传播…

力扣hot100二刷——二叉树

第二次刷题不在idea写代码&#xff0c;而是直接在leetcode网站上写&#xff0c;“逼”自己掌握常用的函数。 标志掌握程度解释办法⭐Fully 完全掌握看到题目就有思路&#xff0c;编程也很流利⭐⭐Basically 基本掌握需要稍作思考&#xff0c;或者看到提示方法后能解答⭐⭐⭐Sl…

网络安全 --- 基于网络安全的 Linux 最敏感目录及文件利用指南

目录 基于网络安全的 Linux 最敏感目录及文件利用指南 Linux 中最敏感的目录及文件 1. /etc 2. /root 3. /var/log 4. /proc 5. /tmp 6. /home 7. /boot 8. /dev 如何利用这些敏感文件 你可能没想到的知识点 总结 Linux 中最敏感的目录及文件 1. /etc 存放内容&a…

深入浅出:Java实现斐波那契数列的七种武器与性能调优指南

​​​ 引言:当数学之美邂逅算法之力 斐波那契数列——这个诞生于13世纪的数学瑰宝,在计算机科学中焕发出新的生命力。作为递归与动态规划的经典案例,它不仅是算法入门的必修课,更是性能优化的试金石。本文将带您深入探索Java实现斐波那契数列的七种核心方法,并揭秘不同…

音视频入门基础:RTP专题(17)——音频的SDP媒体描述

一、引言 在《音视频入门基础&#xff1a;RTP专题&#xff08;3&#xff09;——SDP简介》中对SDP协议进行了简介&#xff0c;以H.264为例介绍了视频的SDP的媒体描述。本文对该文章进行补充&#xff0c;以AAC为例&#xff0c;讲述音频的SDP媒体描述。 二、文档下载 《RFC 364…

MyBatis-Plus防全表更新与删除插件BlockAttackInnerInterceptor

防全表更新与删除插件 BlockAttackInnerInterceptor 是 MyBatis-Plus 框架提供的一个安全插件&#xff0c;专门用于防止恶意的全表更新和删除操作。该插件通过拦截 update 和 delete 语句&#xff0c;确保这些操作不会无意中影响到整个数据表&#xff0c;从而保护数据的完整性…

嵌入式开发之STM32学习笔记day06

基于STM32F103C8T6的开发实践——从入门到精通01 1. 引言 STM32系列微控制器是STMicroelectronics推出的一款高性能、低功耗的32位微控制器&#xff0c;广泛应用于嵌入式系统中。STM32F103C8T6是其中非常受欢迎的一款&#xff0c;凭借其强大的性能、丰富的外设接口和低廉的价格…

TCP/IP 协议精讲-精华总结版本

序言 本文旨在介绍一下TCP/IP涉及得所有基础知识&#xff0c;为大家从宏观上俯瞰TCP/IP提供一个基石&#xff0c;文档属于《TCP/IP图解&#xff08;第五版&#xff09;》的精简版本。 专业术语 缩写 全称 WAN Wide area network广域网 LAN Local area network局域网 TC…

Ubuntu22.04虚拟机里安装Yolov8流程

1. 安装pytorch sudo apt install nvidia-cuda-toolkit nvcc --version # 官方适配地址&#xff1a;https://download.pytorch.org/whl/torch/import torch print(torch.__version__) print(torch.cuda.is_available())2. 安装环境 # cuDNN 安装&#xff1a;https://develop…

stm32第五天按键的基础知识

一&#xff1a;按键连接示意图 按键控制LED灯 软件设计流程 初始化系统 o 初始化GPIO外设时钟 o 初始化按键和LED的引脚 • 检测按键输入电平来控制LED灯 o SW2控制灯开 。 SW3控制灯关 1&#xff1a;key.c工程 #include"key.h" #include"stm32f10x.h"v…

Xposed模块开发:运行时修改技术

1. Xposed框架核心原理 1.1 运行时架构解析 Android ART Hook机制&#xff1a; graph TD A[目标APP进程] --> B{系统Zygote} B -->|加载Xposed| C[XposedBridge] C --> D[模块1] C --> E[模块2] D --> F[Hook目标方法] E --> F 1.1.1 核心组件交…

【Python学习笔记】一些关于多线程,xls文件读取,PyQt5,PyInstaller打包等问题的解决方案记录

背景&#xff1a; 最近利用休息时间写了个小型exe程序&#xff0c;主要涉及的技术点有&#xff1a;多线程&#xff0c;读取xls文件&#xff0c;基于PyQt5的简单GUI页面&#xff0c;利用PyInstaller打包成exe。虽然有ChatGPT等协助&#xff0c;但难免还是在开发过程中遇到了一些…

基于javaweb的SpringBoot智能相册管理系统图片相册系统设计与实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…