【C++标准模版库】list的介绍及使用

server/2024/10/20 9:52:17/

list

  • 一.list的介绍
  • 二.list的使用
    • 1.list 构造函数
    • 2.list 空间大小
    • 3.list 增删查改
    • 4.list 迭代器的使用
      • 1.正向迭代器
      • 2.反向迭代器
    • 5.list 其他成员函数
  • 三.vector与list关于sort性能的比较

list_1">一.list的介绍

  C++中的list标准模板库（STL）是C++标准库中的一个重要组成部分，它提供了一种双向链表的数据结构实现。list是C++ STL中的一个序列容器，它允许在常数时间内进行任意位置的插入和删除操作。与vector不同，list是一个双向链表，其元素不是连续存储的，而是存储在互不相关的独立节点中，每个节点都包含数据部分和两个指针（分别指向前一个节点和后一个节点）。

list关键特性：

  1. 双向链表：list的底层实现是双向链表，支持高效的插入和删除操作，尤其是在链表的头部和尾部。
  2. 不支持随机访问：与vector和deque（双向队列）等容器不同，list不支持通过索引直接访问元素，访问特定位置的元素需要从已知位置（如头部或尾部）开始迭代。
  3. 迭代器：list提供了双向迭代器，允许从前往后或从后往前遍历链表。
  4. 内存分配：由于list的元素不是连续存储的，因此它不需要在插入或删除元素时重新分配大块内存，这减少了内存碎片和重新分配的开销。

list_10">二.list的使用

  学习list时查看文档是非常重要的（list的文档介绍），list在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

list__13">1.list 构造函数

(construct)构造函数声明接口说明
list()（重点）无参构造
list（size_type n, const value_type& val =value_type()）构造并初始化n个val，无val默认为T()，例如整形为0
list (const list& x)（重点）拷贝构造
list (InputIterator first, InputIterator last)使用迭代器区间进行初始化构造

注意：list使用模板，template < class T > ，其中将T重定义为value_type。

int main()
{list<int> l1; //无参构造list<int> l2(10, 1); //10个1有参构造list<int> l3(l2.begin(), l2.end()); //迭代器区间构造list<int> l4(l2); //拷贝构造//list<int> l3(l2.begin() + 3, l2.end() - 2); errorlist<int> l5(++l2.begin(), --l2.end()); //注意：list迭代器区间构造不支持+，-操作，但是支持++，--//1.迭代器循环遍历list<int>::iterator it = l4.begin();while (it != l4.end()){cout << *it << " ";++it;}cout << endl;//2.auto+范围for变量for (auto e : l4){cout << e << " ";}cout << endl;return 0;
}

list__55">2.list 空间大小

函数声明接口说明
size返回list中有效节点的个数
empty检测list是否为空，是返回true，否则返回false
int main()
{list<int> l1;cout << l1.size() << endl;  //0cout << l1.empty() << endl; //1return 0;
}

list__71">3.list 增删查改

函数声明接口声明
front返回list的第一个节点中值的引用
back返回list的最后一个节点中值的引用
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
assign赋值：支持个数赋值、迭代器赋值（不常用）
insert在list position 位置中插入值为val的元素（只支持迭代器）
erase删除list position位置的元素（只支持迭代器）
swap交换两个list中的元素
resize改变list的有效元素的个数
clear清空list中的有效元素
emplace_front在某些情况下比push_front效率高
emplace_back在某些情况下比push_back效率高
int main()
{list<int> l1(10, 1); //初始化为10个1l1.front() = 100; //返回引用——>修改头为100l1.back() = 100;  //返回引用——>修改尾为100l1.push_front(10); //头插l1.pop_front();    //头删l1.push_back(10);  //尾插l1.pop_back();     //尾删list<int> l2;l2.assign(5, 1); //赋值为5个1l2.assign(l1.begin(), l1.end()); //迭代器赋值list<int> l3;l3.push_back(1);l3.push_back(2);l3.push_back(3);l3.push_back(4);//要求在第3个位置插入10：实际是第四个位置变成10//错误写法：l3.insert(l3.begin() + 3, 10); //双向迭代器：支持++/--、不支持随机访问+/-//正确写法如下：auto it = l3.begin();int k = 3;while (k--){++it;}l3.insert(it, 10); //插入一个10for (auto e : l3){cout << e << " "; //1 2 3 10 4}cout << endl;l3.insert(it, 5, 1); //插入5个1for (auto e : l3){cout << e << " "; //1 2 3 10 4}cout << endl;l3.insert(it, l1.begin(), l1.end()); //插入5个1for (auto e : l3){cout << e << " "; //1 2 3 10 4}cout << endl;int x = 0;cin >> x;it = find(l3.begin(), l3.end(), x); //先找x所在的迭代器if (it != l3.end()) //找不到x的表面：it == l3.end(){l3.erase(it); //按照迭代器删除x}l3.swap(l1); //l3与l1交换l3.clear();  //清空l3中的有效数据l3.resize(10, 1); //修改有效数据的个数：10个数据全为1l3.resize(20);    //前10个数据全为1，后10个数据默认为0return 0;
}

struct A
{
public:A(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){cout << "A(int a1 = 1, int a2 = 1)" << endl;}A(const A& a){cout << "A(const A& a)" << endl;}int _a1;int _a2;
};
int main()
{//对于内置类型无区别list<int> l1;l1.push_back(1);l1.emplace_back(2);list<A> l2;A aa1(1, 1);l2.push_back(aa1);     //尾插有名对象l2.push_back(A(2, 2)); //尾插匿名对象//l2.push_back(3, 3);  //不支持A aa2(1, 1); //有参构造l2.emplace_back(aa2); //拷贝构造l2.emplace_back(A(2, 2)); //有参构造+拷贝构造//emplace_back()支持直接传构造A对象的参数，而push_back()不支持l2.emplace_back(3, 3); //直接有参构造更高效return 0;
}

在这里插入图片描述

list__206">4.list 迭代器的使用

函数声明接口说明
begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator/const_reverse_iterator，获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator

迭代器划分为两类：

按照功能：

  1. 正向迭代器：iterator
  2. 反向迭代器：reverse_iterator
  3. const修饰正向迭代器：const_iterator
  4. const修饰反向迭代器：const_reverse_iterator

按照性质：

  1. 单向：forward_list/unordered_map… 支持：++
  2. 双向：list/map/set… 支持：++/–
  3. 随机：vector/string/deque… 支持：++/–/+/-

+：正向、支持随机访问（例如：支持begin()++、begin() + 3）
-：反向、支持随机访问（例如：支持begin()- -、begin() - 3）
++：正向、不支持随机访问（例如：支持begin()++、不支持begin() + 3）
–：反向、不支持随机访问（例如：支持begin()- -、不支持begin() - 3）

双向包含单向，同理随机包含双向。

在这里插入图片描述

int main()
{list<int> l1(10, 1);//list不支持算法库中的sort，要求随机迭代器//sort(l1.begin(), l1.end());//vector、string支持sortstring s1("156874239");sort(s1.begin(), s1.end());cout << s1 << endl; //123456789return 0;
}

1.正向迭代器

在这里插入图片描述

int main()
{//普通正向迭代器list<int> l1(10, 1);list<int>::iterator it = l1.begin();while (it != l1.end()){//(*it)++; 可以修改cout << *it << " ";++it;}cout << endl;//const修饰正向迭代器const list<int> l2(10, 1);list<int>::const_iterator cit = l2.begin();while (cit != l2.end()){//(*cit)++; 不可以修改cout << *cit << " ";++cit;}cout << endl;return 0;
}

2.反向迭代器

在这里插入图片描述

int main()
{//普通反向迭代器list<int> l1(10, 1);list<int>::reverse_iterator rit = l1.rbegin();while (rit != l1.rend()){//(*rit)++; 可以修改cout << *rit << " ";++rit;}cout << endl;//const修饰反向迭代器const list<int> l2(10, 1);list<int>::const_reverse_iterator crit = l2.rbegin();while (crit != l2.rend()){//(*crit)++; 不可以修改cout << *crit << " ";++crit;}cout << endl;return 0;
}

list__321">5.list 其他成员函数

函数声明接口声明
reverse逆置设计的些许冗余，可以使用算法库中的reverse
sort排序：默认得到升序的list，降序需要使用仿函数
merge合并两个有序的list，默认传入升序的list，得到升序的list，降序需要使用仿函数
unique将有序的list去除重复的数据
remove移除给定值的数据
splice剪切+粘贴（具体看如下代码）
int main()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);//list的成员函数reverse设计的有些冗余l1.reverse();//算法库的reversereverse(l1.begin(), l1.end());l1.sort(); //排序：默认升序，低层是归并//算法库的函数sort要支持随机访问，无法被list使用，低层是快排//降序——>仿函数less<int> ls;    //小于号：升序greater<int> gt; //大于号：降序l1.sort(ls);l1.sort(greater<int>()); //匿名对象list<int> first;first.push_back(1);first.push_back(3);first.push_back(5);list<int> second;second.push_back(2);second.push_back(4);second.push_back(6);//合并两个升序list，得到升序的list，此时second为空//也支持合并两个降序list，得到降序的list——>与sort一样使用仿函数first.merge(second); cout << first.size() << endl;  //6cout << second.size() << endl; //0list<int> l2;l2.push_back(1);l2.push_back(3);l2.push_back(2);l2.push_back(2);l2.push_back(5);l2.push_back(5);l2.sort();    //先排序再去重l2.unique();  //有序list去重l2.remove(3); //移除3return 0;
}

int main()
{list<int> mylist1, mylist2;for (int i = 1; i <= 4; ++i){ mylist1.push_back(i);      //mylist1: 1 2 3 4}for (int i = 1; i <= 3; ++i){mylist2.push_back(i * 10); //mylist2: 10 20 30}list<int>::iterator it;it = mylist1.begin();++it;//一个链表的节点转移给另一个链表mylist1.splice(it, mylist2); //mylist1：1 10 20 30 2 3 4//mylist2：emptylist<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);l1.push_back(6);int x;cin >> x;it = find(l1.begin(), l1.end(), x);if (it != l1.end()){//l1.splice(l1.begin(), l1, it); //将it位置的数据剪切粘贴到l1的头部//将迭代器区间it~l1.end()剪切粘贴到l1的头部l1.splice(l1.begin(), l1, it, l1.end()); }return 0;
}

listsort_432">三.vector与list关于sort性能的比较

注意：凡是测试性能Debug下不具有参考价值，要在release下测试性能。

int main()
{srand(time(0));const int N = 1000000;list<int> l1;vector<int> v1;for (int i = 0; i < N; ++i){auto e = rand() + i; //减少重复的数值l1.push_back(e);v1.push_back(e);}int begin1 = clock();sort(v1.begin(), v1.end()); //算法库：sort（快排）排序vectorint end1 = clock();int begin2 = clock();l1.sort(); //无法使用算法库的sort，使用类成员函数sort（归并）排序int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);return 0;
}

在这里插入图片描述

思考：可以发现算法库中的sotr性能更高，list中成员函数sort性能不太高，因此如果将list中的数据拷贝到vector中进行sort，再将vector赋值到list时性能还会更高？代码如下：

int main()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector<int> v(lt2.begin(), lt2.end());//排序sort(v.begin(), v.end());//拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

在这里插入图片描述

事实证明：拷贝数据不会花太多时间，以及list排序性能不太行，甚至不如拷贝到vector中进行排序。


http://www.ppmy.cn/server/95836.html

相关文章

Mac电脑玩Steam游戏 黑神话悟空可以在steam上玩吗 黑神话悟空成为Steam全球周销量第一

Mac电脑玩Steam游戏 黑神话悟空可以在steam上玩吗 黑神话悟空成为Steam全球周销量第一

《黑神话&#xff1a;悟空》游戏基于《西游记》原著的世界观背景设计了主线、支线剧情&#xff0c;努力还原西游原著背景的同时&#xff0c;也在产品开发与设计过程中加入了众多中国传统文化元素。游戏提供数字标准版和数字豪华版两种版本&#xff0c;售价分别为268元和328元&a…
阅读更多...
嵌入式初学-C语言-练习三

嵌入式初学-C语言-练习三

#部分题目可能在之前的博客中有&#xff0c;请谅解&#xff0c;保证常见题型均被发出# 1.计算n以内所有正奇数的和 ? n值通过键盘输入 代码&#xff1a; 1 /*2 需求&#xff1a;计算n以内所有正奇数的和 ? n值通过键盘输入3 */4 #include <stdio.h>5 6 int main()7 …
阅读更多...
[qt] 线程等待与唤醒

[qt] 线程等待与唤醒

对于生产者与消费者的数据处理的另一种好的解决方法是使用QWaitCondition类,允许线程在一定的条件下唤醒其他多个线程来共同处理。 一 定义公共变量 DataSize: 生产者生产数据的大小BufferSize: 也就是这个缓冲区的大小,每个单元是一个int&#xff0c;也有可能是一个链表,结构…
阅读更多...
React（四）：DOCX文件在线预览

React（四）：DOCX文件在线预览

效果 注意 ⚠️注意&#xff1a;部分文件预览存在问题 依赖 $ yarn add docx-preview $ yarn add jszip源码 import ./index.scss; import {useRef} from react; import type {UploadRequestOption} from rc-upload/lib/interface; import {Upload, Button, message} from an…
阅读更多...
写一个MyBatis的plugins，记录完整SQL日志

写一个MyBatis的plugins，记录完整SQL日志

目录 概览MyBatis PluginsInvocationMappedStatementConfigurationBoundSqlMetaObject 完整示例参考资料 概览 MyBatis的SQL输出日志语句和参数是分开打印的&#xff0c;我们调试时需要将语句和参数再次拼接才能进行测试执行。当遇到长SQL和参数较多时&#xff0c;还原一个SQL往…
阅读更多...
C语言基础题：硬币问题（C语言版）

C语言基础题：硬币问题（C语言版）

1.题目描述 今有面值为 1、5、11 元的硬币各无限枚。 想要凑出 九 元&#xff0c;问需要的最少硬币数量。 2.输入格式 仅一行&#xff0c;一个正整数 n。 3.输出格式 仅一行&#xff0c;一个正整数&#xff0c;表示需要的硬币个数。 4.输入输出样例 1.输入1&#xff1a; 15 2…
阅读更多...
Spring Boot集成RabbitMQ的使用

Spring Boot集成RabbitMQ的使用

&#x1f341; 作者&#xff1a;知识浅谈&#xff0c;CSDN签约讲师&#xff0c;CSDN博客专家&#xff0c;华为云云享专家&#xff0c;阿里云专家博主 &#x1f4cc; 擅长领域&#xff1a;全栈工程师、爬虫、ACM算法 &#x1f525; 微信&#xff1a;zsqtcyw 联系我领取学习资料 …
阅读更多...
HTTP/2：让网络飞起来

HTTP/2：让网络飞起来

文章目录 一、HTTP/2 的基本概念和背景二、HTTP/2 的主要特性和优势2.1 二进制帧2.2 多路复用2.3 头部压缩2.4 服务器推送 三、HTTP/2 的实现和部署四、HTTP/2 与现有技术的比较五、HTTP/2 与 Web 性能优化六、结束语&#xff1a;让 HTTP/2 助力你的 Web 开发 今天我们来聊聊一…
阅读更多...
最新文章

Copyright @ 2022~2023