目录
◉list的底层逻辑
◉关于list的新增功能
▲splice功能
▲remove函数
▲unique函数
▲merge函数
▲sort函数
▣迭代器类型
▲reverse函数
作为数据容器之一的list和其他容器的使用上有很多相似的地方,比如都有大致相同的构造函数,大致相同的头插尾插,头删尾删函数。因此对于重复的内容我们就不在赘述,直接介绍关于list和其他数据结构容器不相同的使用方法。
list的底层逻辑
我们的list底层是使用带头双向循环链表实现的。所以list具有链表的特征——在插入数据的时候不需要进行数据的移动,效率很高。同时由于是带头双向循环链表。所以我们还可以通过只想尾节点的指针快速的找到最后一个节点的指针大大的提高了效率。
由于我们的list是链表的结构。链表并不支持随机读取,如果使用随机读取的话,程序的运行效率会大大降低,所以设计者为了避免大家犯这种错误,没有提供[ ]运算符重载的接口。所以我们在想要遍历链表的时候只能使用迭代器。
但是在使用迭代器的时候,还有很多需要注意的事项:由于我们的链表每一个元素所存储的位置并不连续所以我们的list同样没有支持+/-等函数接口。如果想要使用迭代器进行list对象的查找,我们只能通过对迭代器进行++操作进行。或者直接使用范围for(实际上也是迭代器)
同时还需要我们注意一点:由于我们的链表不是顺序存储,所以我们的循环判断条件不能是tmp<l1.end() 而应该是不等于!!!
关于list的新增功能
splice功能
splice函数的作用是将另外链表上的节点截取下来链接到该链表的指定位置上面。同样的我们也可以使用该函数取下本链表上的节点,重新链接到指定的位置达到我们的预期效果。使用方式如下:
remove函数
该功能仅仅是删除链表当中等于某一个值的节点,我们直接使用即可。
unique函数
该函数的作用是去除链表当中重复的数据,但是在使用的时候我们需要注意:该函数只能对有序的链表执行去重操作,因此我们必须先对链表进行排序操作。
我们会发现第一遍去重操作并没有成功,因此我们需要注意在去重之前一定要保证链表当中的元素有序。
merge函数
该函数的作用是将两个链表进行归并产生一个新的有序的链表。同样的我们在使用该函数之前需要保证我们的链表当中的数据是有序的。
函数的第二个参数是一个比较器,我们可以手动编写一个比较函数规定归并的方式。
sort函数
该函数的作用是对链表当中的数据进行排序。相信大家看到这个函数的时候都会想到另外一个sort函数。没错,就是我们algorithm库当中提供的sort函数。那么这两个排序函数有什么区别呢?
我们来进行比较:
仔细观察我们会发现,库函数当中的sort参数是一个一个的迭代器。并且类型都是自定义出来的Random迭代器。那么这个有没有什么讲究呢?我们的list能不能通过迭代器进行排序呢?
我们会发现在尝试使用迭代器进行sort排序的时候出现了系统报错。这是因为我们的迭代器的类型不匹配。
查找文档我们可以发现list的迭代器类型是bidirectional。该迭代器是一个双向的迭代器。
迭代器类型
这个时候就要向大家介绍我们数据结构当中所使用到的迭代器的类型了。在我们的数据结构当中一共存在三种迭代器种类。一种是单向迭代器,一种是双向迭代器,一种是随机迭代器。
其中单项迭代器主要由单链表等数据结构进行使用,双向迭代器主要由list和deque等数据结构进行使用,随机迭代器主要由vector和string等数据结构进行使用,对于不同的迭代器使用的场景以及功能也是不同的。
对于单向迭代器我们只允许进行++操作,对于双向迭代器我们允许进行++/--操作,对于随机迭代器我们允许++/--/+/-操作。
vector的迭代器类型:random iterator
list的迭代器类型:bidirectional iterator
forward_list的迭代器类型:forward iterator
这就是我们的list不能使用系统库当中的sort的原因。
但是我们不能过分依赖于list当中的sort函数。list当中的sort函数仅仅是为了给我们提供方便而已。对于小规模数据的处理还可以,但是对于大规模的数据,由于容器的特性的原因效率很低。所以我们还是推荐使用vector进行数据的排序操作。
reverse函数
该函数的作用就是将链表当中的数据进行逆置操作。同样的,我们的系统std库当中也拥有相同功能的reverse函数。
我们会发现该函数的迭代器类型是一个双向迭代器,因此可以正常使用。