其实在日常中，链表的题目做的比较多，但是使用STL自带链表的还是比较少，所以里面的一些API不大熟悉。这边也简要介绍一些。
基本的一些API
先列举的这些和上面几篇用法几乎一样，所以不再累述。
赋值相关
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换
插入、删除相关
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。
list提供了可以从头部或尾部直接加入元素，也可以在头部或尾部直接删除元素。
把remove函数拿出来讲一下，如何删除自定义数据。如果我们的数据是内置类型，那很好删除，找到该elem，用 == 比较，为真就表示找到了，进行删除。而自定义数据用 == 是不能直接比较的，我们应该先重载==，再进行删除。我们重载的时候，要注意，传入的参数都必须是const类型，否则编译不会通过，因为编译器发觉我们会有改变数据的风险，导致比较结果出错！
大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
这边的size函数有个特殊点：
- GCC下时间复杂度为O(n).
- VC下时间复杂度为O(1).
在GCC下，size函数的复杂度为O(n),它是通过调用标准库的distance(begin(),end())算法来计算长度的。而在VC类的编译器下，维护了一个成员变量_Mysize，保存长度。就可以直接查出来，时间复杂度为O(1).
这其实是一种取舍，要先讲一下list::splice函数，这是让两个不同的链表进行拼接的函数。GCC为了维护这个函数，使拼接后长度更容易计算，因此没有给一个成员变量来保存大小，如果给了，那拼接后的长度是两个size相加吗？不一定，因为splice拼接方法有多种。所以没有给出。
存取操作
front();//返回第一个元素。
back();//返回最后一个元素。
注意是直接返回元素。
STL中list是一个双向循环链表
我们用一段代码来证明它是一个双向循环链表：从头结点遍历2倍的长度单位，看是否会循环再打印一次。
先说一下几个类型：
//链表结点类型
list<int>::_Nodeptr node;
而结点类有三个成员：下一节点指针，上一节点指针，数据：
node->_Next;
node->_Prev;
node->_Myval;
再看例子：
int main(){
list<int> myList;
for (int i = 0; i < 10; i ++){
myList.push_back(i);
}
list<int>::_Nodeptr node = myList._Myhead->_Next;
for (int i = 0; i < myList._Mysize * 2;i++){
cout << "Node:" << node->_Myval << endl;
node = node->_Next;
if (node == myList._Myhead){
node = node->_Next;
}
}
return 0;
}
首先我们用一个for循环，将数据存进去。
然后我们用一个节点指向头结点的的下一节点。list的头结点_Myhead是不存任何东西的，只是为了插入方便而已，所以这么整。所以我们要指向第一个有数据的节点。
当我们遍历一次链表长度时，到达尾节点时，若是循环链表，则会再回到头部，看一下执行结果：
可以清楚的看到，我循环了2倍长度，它遍历了两次。所以，list是一个循环链表。
list的反转和排序函数
reverse和sort函数
reverse函数就是反转函数，较为简单，没什么特殊的。sort函数排序也是一样，默认从小到大排序。
而我们可以是指定排序顺序的。有两种方法，一种是回调函数的方法，另一种是仿函数的方法。
现在假设我们有一个链表：
list<int> myList;
for (int i = 0; i < 5; i++){
myList.push_back(i);
}
list.sort();
我们执行完sort的结果，会是从小到大排序的链表。也就是说，当sort的参数为空时，会执行默认的排序，那现在我们就给它传递一个参数，改变排序规则。
现在就来介绍上述的两种方法。
回调函数方法
先写出这个回调函数：
bool mycmp(int a, int b)
{
return a > b;
}
- 返回值：bool(因为这里需要比较)。
- 参数：int型(取决于你的链表存放的数据类型)。
- 排序规则：从大到小，所以return a > b;
我们针对整型进行大到小的排序，所以，我们要返回a > b即可。
随后，我们再程序中执行：
mylist.sort(mycmp);
这样就行了，就可以从大到小排序了。
仿函数方法
记住仿函数不是一个函数，是一个类。它通过重载()来生效。因为底层中使用了大量的cmp(a,b)这种形式来比较a和b的大小。来看一下：
class MyCmp
{
public:
bool operator()(int a, int b)
{
return a > b;
}
};
同样的，仿函数里面重载()：
- 返回值：bool(因为这里需要比较)。
- 参数：int型(取决于你的链表存放的数据类型)。
- 排序规则：从大到小，所以return a > b;
可以看到，和回调函数的规则几乎一样。
调用形式为：
mylist.sort(MyCmp());
为什么多了一对小括号呢？我们需要传入的是一个对象，而回调函数传进去就直接是一个函数对象，仿函数是一个类，我们加一对括号生成一个匿名对象，从而传递正确的参数。
下面看一个reverse和sort的使用例子：
int main()
{
list<int> myList;
for (int i = 0; i < 5; i++){
myList.push_back(i);
}
//反转
myList.reverse();
list<int>::_Nodeptr node = myList._Myhead->_Next;
cout << "反转之后：" << endl;
for (size_t i = 0; i < myList._Mysize; ++i)
{
cout << node->_Myval << " ";
node = node->_Next;
}
//再排序(从小到大)
myList.sort();
node = myList._Myhead->_Next;
cout << endl << "默认排序：" << endl;
for (size_t i = 0; i < myList._Mysize; ++i)
{
cout << node->_Myval << " ";
node = node->_Next;
}
//再排序(从大到小)
//myList.sort(mycmp); //使用回调函数方法，传入一个函数对象
myList.sort(MyCmp()); //使用仿函数方法，传入一个匿名对象
node = myList._Myhead->_Next;
cout << endl << "从大到小排序：" << endl;
for (size_t i = 0; i < myList._Mysize; ++i)
{
cout << node->_Myval << " ";
node = node->_Next;
}
return 0;
}
执行结果：
为什么不用标准库算法sort呢？
如果用系统提供的sort，那么参数就为迭代器：
sort(mylist.begin(),mylist.end());
但实际上不能完成的。因为系统提供的sort函数对迭代器有要求：必须是可以随机访问的迭代器！ 而list容器不提供随机访问的能力，所以不能使用。但是往往这类东西都会自己实现一个sort，所以不用担心。
一些复杂需求排序
讲完刚刚指定排序规则的排序，现在我们可以有更复杂的排序需求了：
若干学生，优先按照成绩大到小排序，成绩相同按照年龄小到大排序，年龄相同按照姓名升序排序，姓名相同按照班级降序排序。
这就是个不断比较的过程而已，没什么特殊的地方，回调函数如下：
bool ComplicatedCmp(Stu &stu1, Stu &stu2)
{
if (stu1._iScore == stu2._iScore)
{
if (stu1._iAge == stu2._iAge)
{
if (stu1._strName == stu2._strName)
{
return stu1._iClass > stu2._iClass;
}
else
{
return stu1._strName < stu2._strName;
}
}
else
{
return stu1._iAge < stu2._iAge;
}
}
else
{
return stu1._iScore > stu2._iScore;
}
}
主函数：
int main()
{
list<Stu> mylist;
mylist.push_back(Stu("Tom", 4, 90, 13));
mylist.push_back(Stu("Jerry", 5, 84, 11));
mylist.push_back(Stu("Giao", 1, 99, 10));
mylist.push_back(Stu("Fuck", 6, 35, 15));
mylist.push_back(Stu("Bill", 2, 96, 17));
mylist.push_back(Stu("Null", 2, 96, 16));
mylist.push_back(Stu("Null", 0, 96, 17));
mylist.sort(ComplicatedCmp);
for (auto it = mylist.begin(); it != mylist.end(); ++it)
{
cout << "Score:" << it->_iScore << " Age:" << it->_iAge << " Name:" << it->_strName << " Class:" << it->_iClass << endl;
}
return 0;
}
可以看到结果为：
已经按照我们想要的排序进行排序了。