C++ [STL之list的使用]

news/2024/11/8 14:45:11/

list使用

本文已收录至《C++语言和高级数据结构》专栏！
作者：ARMCSKGT

在这里插入图片描述

前言

vector是一片连续的空间，在数据访问上性能较好，但是任意位置插入删除性能较低，头插头删性能亦是如此；此时在这种需要频繁插入的场景下，显然链表是一种更好的选择，STL中实现了带头双选循环链表，本次我们来介绍该如何使用STL中的链表list！
list

正文

本文理论依据来自于官方文档：STL容器list文档！
首先在使用list前，需要声明头文件 < list > 且声明命名空间std！
list是通过模板实例的泛型容器，需要指定类型进行实例化！

默认成员函数

构造函数类

构造函数类

  • 默认构造
    –构造一个空对象，里面没有任何数据(底层上只有一个头节点)
  • 构造n个值为val的链表对象
    –插入n个值实例类型的val值，构造一个对象
  • 迭代器区间构造
    – 通过其他容器迭代器或指针构造一个list对象
  • 列表初始化(C++11)
    – 对于支持C++11的编译器支持像数组一样使用列表{ }初始化
  • 拷贝构造
    – 拷贝另一个list，从而构造一个一模一样的list对象
#include <iostream>
#include <list>
using namespace std;void Print(const list<int>& obj) //打印函数
{for (const auto& x : obj){cout << x << " ";}cout << endl;
}int main()
{list<int> l1; //默认构造list<int> l2(5, 1); //构造5个值为1(int类型)的链表对象Print(l2);int arr[] = { 5,4,3,2,1 };list<int> l3(arr, arr + 5); //指针作为迭代器区间构造Print(l3);vector<int> v = { 6,7,8,9,10 };list<int> l4(v.begin(),v.end()); //容器迭代器区间构造Print(l4);list<int> l5 = {11,12,13,14,15}; //列表初始化构造(C++11)Print(l5);list<int> l6(l5); //拷贝构造Print(l6);return 0;
}

演示

赋值重载

赋值重载与拷贝构造类似，只不过赋值的前提是对象已存在，拷贝构造是初始化对象！

void Print(const list<int>& obj)
{for (const auto& x : obj){cout << x << " ";}cout << endl;
}int main()
{vector<int> v = { 5,4,3,2,1 };list<int> l1(v.begin(),v.end()); //容器迭代器构造list<int> l2(5, 1);Print(l2);l2 = l1;Print(l2);return 0;
}

赋值重载

析构函数

析构函数在list对象声明周期结束时调用，释放所有节点(包括头节点)！
析构函数

迭代器

list迭代器比较特殊，知道链表的小伙伴应该都懂链表不是一片连续的空间，所以不能像顺序表那样支持迭代器随机访问！(即it+1，it+2…)

同样的，链表的迭代器也分三种(理论上四种)：

  • 正向迭代器
  • 反向迭代器
  • const迭代器(正向和反向)
    迭代器
    const迭代器不支持修改当前指向的值，每一种迭代器不能混用，各自使用各自的迭代器类型！
int main()
{vector<int> v = { 5,4,3,2,1 };list<int> l1(v.begin(),v.end());list<int>::iterator it = l1.begin();list<int>::reverse_iterator rit = l1.rbegin();while (it != l1.end()){cout << *it << endl;++it;		}cout << endl;while (rit != l1.rend()){cout << *rit << endl;++rit;		}return 0;
}

迭代器演示
虽然list迭代器不支持随机访问，但是也支持通过++和- -遍历链表，甚至可以反向遍历，可见迭代器的强大之处！

迭代器在链表中的位置：
迭代器在链表中的位置

容量操作类

数据查询类

链表没有提前开空间这样的说法，对于数据只能查询以及对现有数据操作！
数据量查询

  • empty：查询链表是否为空，为空返回真
  • size：返回当前节点的个数
  • max_size：返回当前实例对象可容纳最大节点数(这个函数常用来检查申请空间的合法性即配合resize使用，查看申请的空间是否合法)
int main()
{list<int> obj(10,5); //初始化10个值为5的节点cout << "empty：" << obj.empty() << endl;cout << "size：" << obj.size() << endl;cout << "max_size：" << obj.max_size() << endl;return 0;
}

数据量查询

节点数量修改

list支持resize控制节点个数，resize支持增多节点和减少节点，对于增多的节点设置为val值，val有缺省参数，根据需要可进行设置初始化！
resize

int main()
{list<int> obj = { 1,2,3,4,5 };cout << "size：" << obj.size() << endl;obj.resize(10);cout << "size：" << obj.size() << endl;obj.resize(3);cout << "size：" << obj.size() << endl;return 0;
}

resize

数据访问

链表不支持下标访问，提供了额外对头尾节点访问的函数front和back，并且拥有引用和const引用重载函数应对不同的场景！
front和back

int main()
{list<int> obj = { 668,778,888,998,1080 };cout << "front：" << obj.front() << endl;cout << "back：" << obj.back() << endl;return 0;
}

front和back

不过list常用的遍历方式还是通过迭代器遍历，而且list因为迭代器所以支持范围for遍历！

增删类

因为链表插入删除效率非常高，所以增删类接口比较多，在这里介绍几种常用的接口！
增删接口

头插头删

头插push_front() 和 头删pop_front() 只需要对头节点next(后继节点)指针操作即可！

int main()
{list<int> obj = { 1,2,3,4,5 };Print(obj);obj.pop_front();Print(obj);obj.push_front(668);Print(obj);return 0;
}

push_front和pop_front

尾插尾删

头插push_back() 和 头删pop_back() 也只需要对头节点prev(前驱节点)指针操作即可！

int main()
{list<int> obj = { 1,2,3,4,5 };Print(obj);obj.pop_back();Print(obj);obj.push_back(668);Print(obj);return 0;
}

push_back和pop_back

重新分配

assign函数有点类似于 = 赋值重载，区别于赋值的是该函数可以跨容器达到赋值的效果(利用迭代器区间)，assign函数会先将list对象清空再重新插入值！

assign函数有两个版本：

  • 分配n个值为val的节点(类似于带参构造函数)
  • 迭代器区间分配
int main()
{list<int> obj = { 1,2,3,4,5 };Print(obj);obj.assign(10, 5); //分配5个值为10的节点Print(obj);int arr[] = { 668 ,778,888,998,1080 };obj.assign(arr,arr+5); //分配arr数组区间Print(obj);return 0;
}

assign

任意位置插入

insert函数支持在迭代器位置插入节点，有三个版本：
insert

  • 在position迭代器位置下插入值为val的节点(返回新插入节点的迭代器)
  • 在position迭代器位置下插入n个值为val的节点
  • 在position迭代器位置下插入一段区间
int main()
{list<int> obj = { 1,2,3,4,5 };auto it = ++obj.begin(); //记录2位置迭代器Print(obj);it = obj.insert(it, 668); //在2位置插入668更新迭代器为668节点Print(obj);obj.insert(it, 888); //在668位置插入888Print(obj);int arr[] = { 6,7,8,9,10 };obj.insert(obj.begin(), arr, arr + 5); //在头节点1位置插入arr数组区间Print(obj);return 0;
}

insert演示
虽然insert函数不会导致迭代器失效，但是insert在插入单节点的函数上支持更新迭代器，必要时建议及时更新迭代器！

任意位置删除

erase函数有两种版本，删除函数需要注意迭代器失效问题，因为删除当前迭代器位置的节点后该位置节点内存已经被释放，所以两个版本的删除函数都会返回删除后的下一个节点迭代器！
erase

int main()
{list<int> l1 = { 1,2,3 };list<int> l2 = { 1,2,3,4,5,6,7,8,9,10 };Print(l1);Print(l2);auto it1 = l1.begin();auto it2 = l2.begin();++it2; ++it2; ++it2;//迭代器挪动到4位置下it1 = l1.erase(it1); //删除手节点 - 更新迭代器it2 = l2.erase(l2.begin(),it2); //删除1-3区间节点(左闭右开) - 更新迭代器Print(l1);Print(l2);return 0;
}

在这里插入图片描述
迭代器失效情况：
迭代器失效
对于单节点删除，如果不更新迭代器，肯定会造成野指针访问，但对于区间删除，因为是左避右开，所以删不到闭区间的迭代器，所以不更新迭代器影响不大，但是如果删除的区间是全部，则还是需要更新迭代器！
这里可以发现it1如果更新迭代器则指向下一个节点迭代器！

其他操作

清空函数

clear可以将链表清空，也就是逐个释放节点，只留下头节点(区别于析构函数，clear不会释放对象)！

int main()
{list<int> obj = { 1,2,3 };cout << "size:" << obj.size() << endl;obj.clear();cout << "size:" << obj.size() << endl;return 0;
}

clear

交换函数

list有属于自己的交换函数，同时库中的函数也支持对list进行交换！

int main()
{list<int> l1 = { 1,2,3 };list<int> l2 = { 4,5,6 };cout << "l1:"; Print(l1);cout << "l2:"; Print(l2);cout << endl;l1.swap(l2); //list对象swap函数交换cout << "l1:"; Print(l1);cout << "l2:"; Print(l2);cout << endl;std::swap(l1, l2); //库函数交换cout << "l1:"; Print(l1);cout << "l2:"; Print(l2);cout << endl;return 0;
}

在这里插入图片描述
list自带的swap和库中的swap都支持容器的交换！

拼接

splice支持将一个list对象中的一个节点或者一段节点从原list对象上截取下来链接在调用对象上！
splice有三个版本：

  • 将一个list截取插入到另一个list中的position迭代器位置
  • 将一个list的一个迭代器节点截取插入另一个list中的position迭代器位置
  • 将一个list的迭代器区间截取插入到另一个list中的position迭代器位置
    splice
int main()
{list<int> l1 = { 1,2,3 };list<int> l2 = { 4,5,6 };l1.splice(l1.begin(), l2); //将l2插入l1中cout << "l1:"; Print(l1);cout << "l2:"; Print(l2);cout << endl;list<int> l3 = { 1,2,3 };list<int> l4 = { 7,8,9 };l3.splice(l3.begin(),l4,l4.begin()); //将l4中的头节点插入l3中cout << "l3:"; Print(l3);cout << "l4:"; Print(l4);cout << endl;list<int> l5 = { 1,2,3 };list<int> l6 = { 448,558,668,778,888 };l5.splice(l5.begin(), l6, ++l6.begin(), l6.end()); //将l5的558-888插入l6中cout << "l5:"; Print(l5);cout << "l6:"; Print(l6);cout << endl;return 0;
}

splice演示
splice函数每次执行都需要另一个list对象的引用，哪怕只截取一个节点，说明在函数内部需要对节点进行剥离和缝合！

splice函数原理：
出自SLT源码剖析

移除指定值元素

remove类似于find+erase，find先找到这个值返回其迭代器供erase删除，该函数会根据给定的val值找到此值并删除，如果该值不存在，则什么也不做！
remove

int main()
{list<int> l1 = { 1,2,3 };l1.remove(2); //删除2l1.remove(5); //删除非list中的元素则执行无效Print(l1);return 0;
}

remove示例

排序

list自带排序算法，但效率非常低！

一般如果要对list排序，可以先将数据拷贝到vector，然后使用库函数sort快速排序后再拷贝会list，虽然有两次拷贝，但是排序性能仍然超过直接对list排序！

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;int main()
{list<int> l1;list<int> l2;for (int i = 1; i < 10000000; ++i) //一千万降序数{l1.push_back(i);l2.push_back(i);}//排升序	time_t t = clock(); //记录开始时间l1.sort(); //list排序cout << "list sort:" << clock() - t << endl;t = clock();vector<int> v(l2.begin(),l2.end());std::sort(v.begin(), v.end()); //库函数排序l2.assign(v.begin(), v.end()); //将排完序的元素分配回listcout << "lib sort:" << clock() - t << endl;return 0;
}

sort
使用库函数sort需要声明头文件algorithm和std命名空间，此结果是在release模式下运行！
库函数对容器操作一般都是使用迭代器！

逆置

list对象自带reverse逆置函数，库中也有reverse函数，作用是将当前序列反过来！
list自带的reverse直接调用即可，库中的reverse则是通过容器迭代器作为参数进行逆置！

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;int main()
{list<int> obj = { 1,2,3,4,5,6,7,8,9,10 };Print(obj);obj.reverse(); //list自带逆置Print(obj);std::reverse(obj.begin(), obj.end()); //库函数逆置Print(obj);return 0;
}

reverse
同样的，使用库函数reverse需要声明头文件algorithm和命名空间std！

去掉重复元素

unique函数支持对元素，但是在去重之前需要进行排序，因为其底层原理是两个相邻的重复元素会删除一个，而需要将所有相同的元素相邻就需要sort排序！

同样的，如果数据量小我们可以直接使用list的排序和去重，如果数据量较大建议拷贝到vector排序然后拷贝会list再去重！

int main()
{list<int> obj = { 1,2,5,3,7,1,6,5,9,8,7,2 };Print(obj);obj.unique(); //不排序直接去重没有任何效果Print(obj);obj.sort(); //排序再去重才会有效果obj.unique();Print(obj);return 0;
}

unique
算法库algorithm中也有unique，同样的适用于所有容器，因为使用迭代器操作！

合并

merge函数支持将一个list合并(移动)到另一个list中(而并非复制)，与splice函数类似，只不过merge是将list中的全部节点按升序或降序的方式链入被插入对象中，该函数有两种形式：
merge

  • 第一种是合并一个list，并按升序插入其中
  • 第二种支持控制升序和降序，我们可以选择将list按升序插入其中，也可以按降序插入其中(使用greater和less控制)
int main()
{list<int> l1 = {6,10};list<int> l2 = { 1,2,5 };Print(l1);l1.merge(l2); //将l2按默认规则链入l1中Print(l1);list<int> l3 = {3,4,9,8,7};l1.merge(l3, less<int>()); //将l3按升序规则链入l1中Print(l1);return 0;
}

merge

关于查找

  • list没有提供查找函数，因为对于链表的查找只能用迭代遍历的方式进行，所以用库中的find足以！
  • 库中的find也是基于迭代器的遍历查找，也适用于所有支持迭代器的容器，find如果查找到了就会返回该元素的迭代器，如果没找到则返回传入的开区间(end())迭代器，如果有多个重复的值则返回正向序列上第一个符号条件的值！
//find的使用
find(迭代器开区间(起始区间)，迭代器闭区间(结束区间)，查找元素);

find底层原理：

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{while (first!=last) {if (*first==val) return first;++first;}return last;
}

使用展示：

int main()
{list<int> obj = { 1,2,5,3,7,1,6,5,9,8,7,2 };list<int>::iterator it = std::find(obj.begin(), obj.end(), 2); //找到了就返回迭代器cout << *it << endl;it = std::find(obj.begin(), obj.end(), 10);cout << (it == obj.end()) << endl; //没找到返回开区间return 0;
}

find
find属于库函数，需要algorithm算法头文件和是他的命名空间！

最后

list的使用介绍到这里就结束了，相信学会了list在需要频繁增删数据的场景下我们那个轻松应对，对于vector和list两者各有优劣，应对不同的场景我们需要合理应用甚至结合使用；list的底层实现非常值得我们去研究，C++下一节将为大家介绍list模拟实现，揭开迭代器的背后秘密！

本次 <C++ list的使用> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

C-PLUS-PLUS

🌟其他文章阅读推荐🌟
C++ <STL之vector模拟实现> -CSDN博客
C++ <STL之vector的使用> -CSDN博客
C++ <STL之string的使用> -CSDN博客
C++ <STL之string模拟实现> -CSDN博客
🌹欢迎读者多多浏览多多支持!🌹

​​

​​

​
​


http://www.ppmy.cn/news/97819.html

相关文章

TA-lib第三方库安装问题

TA-lib第三方库安装问题

因为学习的需要&#xff0c;用到Talib库做写指标分析&#xff0c;但是百度了好久&#xff0c;说是去要某某网站下载对应版本的文件进行本地安装&#xff0c;但是把…404 Not found 然后通过查找&#xff0c;Ta-lib库的安装已经迁移到这里了 https://github.com/TA-Lib/ta-lib-p…
阅读更多...
三秒教会你如何使用scrcpy手机无线投屏到电脑

三秒教会你如何使用scrcpy手机无线投屏到电脑

简介 scrcpy 是一款免费开源的投屏软件&#xff0c;可以将安卓手机屏幕投放在 Windows、macOS、GNU/Linux 上&#xff0c;并可以直接使用鼠标在投屏窗口中进行交互和录制。此应用程序镜像通过 USB 或TCP/IP连接的 Android 设备&#xff08;视频和音频&#xff09;&#xff0c;并…
阅读更多...
如何理解ORB_SLAM2算法中一个特征点在y方向的位置是以金字塔尺度为半径的多行中？

如何理解ORB_SLAM2算法中一个特征点在y方向的位置是以金字塔尺度为半径的多行中？

文章目录 首先看下vRowIndices里面存储了什么？右图像的坐标系右图上每个图像金字塔中提取到的特征点数据经过处理后每行中有多少个特征点每个特征点分别属于那些行？左目特征点的后选匹配点讲一下代码实现的细节算法原理vector<vector<size_t> > vRowIndices(nRow…
阅读更多...
轩辕：首个千亿级中文金融对话模型

轩辕：首个千亿级中文金融对话模型

背景 目前开源的大语言模型或多或少存在以下痛点&#xff1a; 缺少专门针对中文进行优化过的的大语言模型。 支持中文的开源模型的参数规模偏小&#xff0c;没有超过千亿。比如清华和智谱AI的ChatGLM-6B目前只开源了6B参数模型&#xff0c;盘古alpha也只开源了13B的模型。 支…
阅读更多...
Flume学习笔记

Flume学习笔记

1 简介 (1) Apache Flume是一个分布式、可信任的数据采集、日志收集弹性系统(框架)&#xff0c;用于高效收集、汇聚和移动大规模日志信息从多种不同的数据源到一个集中的数据存储中心(HDFS、Hbase或者本地文件系统) (2) 可信任是指保证消息有效的处理和传递&#xff1a; 如果…
阅读更多...
C语言中的类型转换

C语言中的类型转换

C语言中的类型转换 隐式类型转换 整型提升 概念&#xff1a; C语言的整型算术运算总是至少以缺省&#xff08;默认&#xff09;整型类型的精度来进行的为了获得这个精度&#xff0c;表达式中字符和短整型操作数在使用之前被转换为普通整型&#xff0c;这种转换成为整型提升 如…
阅读更多...
rust 初识基础： 变量、数据类型、函数、所有权、枚举

rust 初识基础： 变量、数据类型、函数、所有权、枚举

了解到 rust 和 WebAssembly 的结合使用&#xff0c;可以构建前端应用&#xff0c;而且性能也比较好。初步学习使用 rust 是预编译静态类型语言。 安装 rust 官网下载 rust-CN , 大致了解下为什么选择&#xff1a;高性能、可靠性、生产力。 打开控制台啊&#xff0c;执行安装…
阅读更多...
MySQL高级篇复盘笔记（一）【存储引擎、索引、SQL优化、视图、触发器、MySQL管理】

MySQL高级篇复盘笔记（一）【存储引擎、索引、SQL优化、视图、触发器、MySQL管理】

❤ 作者主页&#xff1a;欢迎来到我的技术博客&#x1f60e; ❀ 个人介绍&#xff1a;大家好&#xff0c;本人热衷于Java后端开发&#xff0c;欢迎来交流学习哦&#xff01;(&#xffe3;▽&#xffe3;)~* &#x1f34a; 如果文章对您有帮助&#xff0c;记得关注、点赞、收藏、…
阅读更多...
最新文章

Copyright @ 2022~2023