《白话C++》第10章 Page126 常用容器 10.6.4 std::list

2024-03-28 04:20

本文主要是介绍《白话C++》第10章 Page126 常用容器 10.6.4 std::list,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 基本概念与本质特性

std::list实现双向列表(也称链表),每一个节点,都有一个指针,指向后一节点和前一节点(都可为空,比如首节点的“上一节点”)。

因为,采用额外的指针维护前后关系,所以列表节点的内存完全不需要连续,这就让节点的插入,删除,甚至链表的合并操作,变得简单。要合并两个vector,需要在第一个vector开辟一大块连续内存,而合并两个列表,只需要让前一列表最后一个节点的“下一节点指针”,指向第二个列表的首指针,再让后者的“前一节点指针”,指向前者即可。

 上图演示了两个vector合并最悲惨的一种情况:合并目标vector1后续可用的连续内存空间不足,只好另开新界,然后复制待合并的两份数据。list合并就永远不会有这种情况发生,如下图所示:

改变两个指针的指向,list2就全部归顺list1了。

【课堂作业】:图解list操作

请读者画出list插入一个节点与删除一个节点的操作过程。

在节点增删操作的性能上,list完胜vector和deque,但在定位节点的速度上list不支持随机访问。如果要修改列表中第9个节点的内容,需要从前面爬起,连爬8次到达,或者考虑从后面倒着爬,如果总节点数没超过17个的话。

在内存占用上,list和vector各有千秋,表面上list的每个节点都要至少多占用2个指针,但由于vector提出的是占用“连续内存”这样苛刻的要求,相比之下,list的要求更好满足。

更重要的是,list不需要“预分配”内存机制,所以不会占用多余内存。

另外一点,list胜出的是:vector和deque由于内存是连续的,当变化之后,容易造成所有数据移位,结果原来代码中使用的迭代器,指针,引用等,很多情况下会失效,需要重新指向。list插入或删除某一节点,除了被删除的节点之外,其他迭代器起,指针,引用等还有效。

某些算法在不支持随机访问的数据结构上执行,会慢许多,但某些算法如果针对list的结构做特点优化,又会快不少。

2.常规的队列接口

尽管deque是相对整齐的队列,而list往往是歪来歪去的长蛇阵,但好歹是都是队列,还都双向,因此list的一些操作接口,和deque是类似的:

//取第一个元素,不判断是否为空
T const& front();
//取最后一个元素,不判断是否为空
T const& back();//在前端或后端加入新元素
void push_front(t);
void push_back(t);//弹出前端或后端的1个元素,并不返回
void pop_front();
void pop_back();

其他标准容器所需要的:

//正向迭代器始末
begin(); //返回正向迭代器
end(); //返回正向迭代器结束位置//逆向迭代器始末
rbegin();
rend();/*C++ 11提供,返回常量迭代器(const_iterator)*/
cbegin();
cend();//是否为空,高效,判断begin() == endl()
bool empty();
//返回个数,需遍历,效率一般
size_t size();
//将元素个数变成num个,如有新增元素,采用默认构造
void resize(num);
//将元素变成num个,如有新增元素,复制elem
void resize(num, elem);

【课堂作业】:证明容器删除元素时,对象被析构

写一个list <S> 调用resize的例子,其中S是用户自定义class/struct类型,证明当resize(num)所传入的num比当前元素个数少时,被扔出容器的元素对象将析构。

3.高效的插入与删除

(1)插入操作

std::list提供三个insert的重载版本:

//在迭代器pos指定位置上,插入一个新元素elem
//返回插入后,同一位置上的有效迭代器
iterator & insert(pos, elem);//在迭代器pos指定位置上,插入n个新元素elem
//无返回值,原pos迭代器通常已经失效
void insert(pos, n, elem);//在迭代器pos指定位置上,插入外来的[beg, end)区间的元素
//无返回值,原pos迭代器通常已经失效
void insert(pos, beg, end);

演示例子:

#include <list>
...list <int> li;li.insert(li.begin(), 11);
li.insert(li.begin(), 2, 22);list <int> li2;
/* 把[++li.begin(), li.end()) 区间的元素
,插入li2的begin()位置*/
li2.insert(li2.begin(), ++li.begin(), li.end());

 

入参beg和end也可以是指向裸数组的指针,下面演示这种情况,并同时演示使用advance调整插入位置:

list <int>::iterator pos = li2.begin();
advance(pos, 2);int arr[] = {0, 1, 2, 3, 4, 5};
li2.insert(pos, arr, arr + sizeof(arr)/sizeof(arr[0]));

 

(2)删除操作

list提供erase和remove两种删除接口:

//删除指定迭代器位置的元素,返回删除后,同一位置上的有效迭代器
iterator & erase(pos);//删除指定迭代器区间的所有元素[beg, end),没有返回值
void erase(beg, end);//删除与指定值相等的所有元素
void remove(val);//删除符合指定判断条件的所有元素
void remove_if(Pred);

erase还是按迭代器位置删,remove则是删除所有指定值的元素,而remove_if则是删除符合判断式Pred的数据:

//判断v是不是偶数
bool is_even_number(int v)
{return (v % 2) == 0;
}void test_list_remove()
{list <int> li;for(int i = 0; i < 10; ++ i){li.push_back(i/2);}li.remove(3); //删除list中,值等于3的元素cout << li.size() << endl; //8li.remove_if(is_even_number);for(list<int>::const_iterator it = li.begin(); it != li.end(); ++ it){cout << *it << ',';}cout << endl;
}

【课堂作业】:测试list、vector、deque的插入与删除性能

参考之前的例子,将deque加入测试。

4. 其他变动性操作

变动性操作是list的优势项目,所以它提供了许多这类操作,下面是几个较常用的操作:

//将所有元素,倒个序儿存储,
//提醒:别和reserve混了
reverse();//元素大小排序,元素之间需要支持使用 < 作比较
sort();
//采用comp方法比较两个元素,然后排序
sort(Compare comp);//将当前list和传入的list中的元素进行有序合并
//注意:两个list中的元素在合并前必须已经有序,
//合并后仍然有序
merge(list& other);//将当前list和传入的list中的元素根据
//给定的比较方法进行有序合并
//注意:两个list中的元素在合并前必须
//已经是按comp方法排序,合并后仍然有序
merge(list& other, Compare comp);

参数中的“Compare”同样是一种判断式,判断原则是:对给定的两个入参比较大小,如果第一个入参比较小,就返回真,否则返回假。我们以第二个版本sort示例:

 

list还提供unique和splice函数,需自学。

【小提示】:为什么list的接口功能“一枝独秀”?

这里提一个问题:list提供的这么多特定操作(在STL中也称算法),难到别的容器不需要吗?比如说“sort(排序)”,难道vector中,deque中的元素就没有排序的需求?真相是,vector和deque都可直接使用全局版本的sort()等算法,因为它们支持随机访问。

这篇关于《白话C++》第10章 Page126 常用容器 10.6.4 std::list的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/854421

相关文章

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

C/C++和OpenCV实现调用摄像头

《C/C++和OpenCV实现调用摄像头》本文主要介绍了C/C++和OpenCV实现调用摄像头,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录准备工作1. 打开摄像头2. 读取视频帧3. 显示视频帧4. 释放资源5. 获取和设置摄像头属性

c/c++的opencv图像金字塔缩放实现

《c/c++的opencv图像金字塔缩放实现》本文主要介绍了c/c++的opencv图像金字塔缩放实现,通过对原始图像进行连续的下采样或上采样操作,生成一系列不同分辨率的图像,具有一定的参考价值,感兴... 目录图像金字塔简介图像下采样 (cv::pyrDown)图像上采样 (cv::pyrUp)C++ O

c/c++的opencv实现图片膨胀

《c/c++的opencv实现图片膨胀》图像膨胀是形态学操作,通过结构元素扩张亮区填充孔洞、连接断开部分、加粗物体,OpenCV的cv::dilate函数实现该操作,本文就来介绍一下opencv图片... 目录什么是图像膨胀?结构元素 (KerChina编程nel)OpenCV 中的 cv::dilate() 函

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

C++ HTTP框架推荐(特点及优势)

《C++HTTP框架推荐(特点及优势)》:本文主要介绍C++HTTP框架推荐的相关资料,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Crow2. Drogon3. Pistache4. cpp-httplib5. Beast (Boos

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、