本篇我们将学习STL中list的使用

list的初始和官方文档

list的官方文档

list的构造与析构

构造函数

析构函数

=运算符重载

迭代器

正向迭代器

反向迭代器

const正向迭代器

const反向迭代器

容量

empty

size

max_size

访问

访问第一个元素编辑

访问最后一个元素

修饰符函数

头插

尾插

构造并头插

构造并尾插

assign

头删

尾删

emplace

insert

erase

resize

swap

clear

操作

sort

reverse

归并编辑

unique

remove

remove_if

splice(拼接)

获取分配器（后续深入学习）

非成员函数重载

关系运算符重载

swap编辑

list的初始和官方文档

list在底层上类似于双向循环链表

在使用list之前需要包含头文件<list>并且有

using namespace std;

list的官方文档

list - C++ 参考

std：：list - cppreference.com

list的构造与析构

构造函数

void list_test1()
{list<int>lt1;//默认构造函数，创建一个空的listlist<int>lt2(10,1);//使用10个1初始化list//构造类似于vector的用法vector<int>v1={1,2,3,4,5};//迭代器区间构造list<int>lt3(v1.begin(),v1.end());//使用vector初始化list//传递数组的指针int a[] = {1,2,3,4,5};list<int>lt4(a,a+4);
}

指针是一种特殊的迭代器（指针是指向数组的指针）。

迭代器行为本质上就是模拟指向数组的指针

容器的迭代器按功能分为三种：

通用功能：++，*，！=

单向：只支持++（单链表/哈希表）

双向：除了支持++，还支持--（红黑树/双向链表list）

随机：除了支持++，还支持--、+、-（string/vector/deque）

迭代器类型可以从这个位置看到

一个算法不是所有的容器都适用的，算法对迭代器有一定的要求。

下图所示的情况下，sort没办法对list类型进行排序，没有对应的功能去支持

双向迭代器是特殊的单向迭代器，随机迭代器是特殊的双向迭代器。

所以要求传双向迭代器的时候可以传双向迭代器也可以传随机迭代器

析构函数

=运算符重载

迭代器

正向迭代器

反向迭代器

const正向迭代器

const反向迭代器

容量

empty

size

max_size

理论值，实际意义不大

访问

访问第一个元素

访问最后一个元素

修饰符函数

头插

尾插

测试：

void list_test2()
{list<int>lt1(5,1);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.push_back(2);//在list尾部添加元素lt1.push_front(3);//在list头部添加元素for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果：

构造并头插

构造并尾插

assign

头删

尾删

emplace

insert

erase

resize

测试：

void list_test3()
{list<int>lt1(5, 1);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.resize(20, 5);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.resize(2,0);for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果为：

swap

clear

操作

sort

算法库的sort是随机迭代器，不适合list

但是sort的效率比算法库的sort要低，为什么呢？

在内存上，分配内存的时候除了CPU还有三级缓存。

CPU访问修改内存数据的时候，会看它在不在缓存，如果在就是命中，不在就是不命中。如果不在就先加载到缓存在命中。

CPU高速，缓存命中率高

数组类型的命中率比较高。而链表的命中率比较低，而且有缓存污染的问题。

sort在数据量小的时候可以使用。在实际应用中最好是用vector的 sort，如果一定要使用建议拷贝到vector然后sort返回list。

reverse

测试：

void list_test7()
{list<int>lt1;for (int i = 1;i <= 10;i++){lt1.push_back(i);}for (auto e : lt1){cout << e << " ";}cout << endl;lt1.reverse();for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果为：

归并

归并之前必须要对链表中的元素进行排序，否则会出问题

void list_test4()
{list<int>lt1,lt2;lt1.push_back(1);lt1.push_back(2);lt1.push_back(4);lt1.push_back(5);lt1.push_back(1);lt1.push_back(3);lt2.push_back(5);lt2.push_back(1);lt2.push_back(3);lt2.push_back(8);lt2.push_back(21);//归并之前必须要对数据进行排序lt1.sort();lt2.sort();//合并两个listlt1.merge(lt2);for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果：

unique

作用是去重。将重复的元素去除。但是要求必须要先排序才能使用

void list_test5()
{list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(4);lt1.push_back(5);lt1.push_back(1);lt1.push_back(3);lt1.push_back(5);lt1.push_back(8);lt1.push_back(21);lt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;lt1.unique();for (auto e : lt1){cout << e << " ";}cout << endl;	
}

结果为：

remove

void list_test6()
{list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(4);lt1.push_back(5);lt1.push_back(1);lt1.push_back(3);lt1.push_back(5);lt1.push_back(8);lt1.push_back(21);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.remove(1);for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果：

remove_if

splice(拼接)

void list_test7()
{list<int>lt1,lt2;for (int i = 1;i <= 10;i++){lt1.push_back(i);}for (auto e : lt1){cout << e << " ";}cout << endl;for (int i = 1;i <= 5;i++){lt2.push_back(i*3);}for (auto e : lt2){cout << e << " ";}cout << endl;list<int>::iterator lt = lt1.begin();lt++;lt1.splice(lt, lt2);for (auto e : lt1){cout << e << " ";}cout << endl;
}

结果为：