7.list

本篇博客梳理C++的STL中的list容器

一、list的基本结构与使用

1．list的介绍

list的底层是带头循环双向链表

带头：含哨兵位
循环：尾节点的next指针指向哨兵位
双向：每个节点具有两个指针域，一个指针指向前一个结点

2．list的使用

（1）list的构造函数

构造函数	接口说明
list (size_type n, const value_type& val = value_type()	用n个val值构造list
list()	构造空的list
list(const list& x)	拷贝构造
list(InputIrerator first,InputIrerator last)	用(first,last)区间中的元素来构造list

（2）迭代器

函数声明	接口说明
begin/end	返回第一个元素的迭代器/返回最后一个元素下一个位置的迭代器
rbegin/rend	返回第一个元素的位置（即end处）/返回最后一个元素的下一个位置（即begin）

迭代器的分类：
①　功能上

②　性质上

实际上，迭代器的性质由STL的底层结构决定
单向迭代器：只支持单向遍历
双向迭代器：支持双向遍历，支持++和–，但不支持一下子+或者-多个单位
随机迭代器：支持随机访问，也就是既支持++和–，也支持+n和-n

（3）容量相关函数

函数声明	接口说明
empty	检查list是否为空，是则返回true，不是则返回false
size	返回list中有效元素的个数

（4）头，尾元素的访问

函数声明	接口说明
front	返回list第一个值的引用
back	返回list最后一个值的引用

（5）增删查改

函数声明	接口说明
push_front	在list的第一个元素前面插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list的pos位置处插入值为val的元素
erase	删除list的pos位置处的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

（6）list支持的sort函数（std标准库库里面没支持）

#include <iostream> 
using namespace std;
#include <vector> 
#include <list>
int main()
{vector<int> v = { 6,3,7,8,3,5,8,1,2,9 };list<int> lt(v.begin(), v.end());lt.sort();//默认排成升序for (auto e : lt){cout << e << " ";}cout << endl;greater<int> gt;lt.sort(gt);//排成降序for (auto e : lt){cout << e << " ";}cout << endl;less<int> ls;lt.sort(ls);//排成升序for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

（7）merge函数：合并两个有序链表

#include <iostream> 
using namespace std;
#include <list>int main()
{list<int> lt1;lt1.push_back(3);lt1.push_back(4);lt1.push_back(2);lt1.sort();list<int> lt2;lt2.push_back(8);lt2.push_back(7);lt2.push_back(9);lt2.sort();lt1.merge(lt2);for (auto e : lt1){cout << e << " ";}return 0;
}

注意，此时lt2已经被清空