list 容器实现了双向链表的数据结构，数据元素是通过链表指针串连成逻辑意义上的线性表，这样，对链表的任一位置的元素进行插入、删除和查找都是极快速的。由于list对象的节点并不要求在一段连续的内存中，所以对于迭代器，只能通过++或--的操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点是与vector等不同的地方。
特点：
- 线性容器
- 常数时间增删改
- 常数时间查（已知迭代器条件下）
- 支持双向操作
缺点：
- 只能对迭代器进行 '++'、 ' -- '操作 不能进行 '+ n '、'- n' 操作 (因为不是连续存储)
头文件
#include <list>
using namespace std;
声明与定义
1、声明：
list<T> lst; // T 为节点类型
2、构造函数
list([结点个数]) // 构造具有 [结点个数] 个的列表 // 需要结点类型提供构造函数
list([结点个数], [结点对象]) // 构建的列表中包含 [结点个数] 个 [结点对象]
list([列表的起始位置], [列表的结束位置]) // 选取其他列表的一部分建立新的列表，[起始位置，结束位置)
例子
list<T> lst1(9);// 包含 9 个结点，每个结点按照 T 给的构造函数构建
list<T> lst2(5,T(1));// 建一个含5个元素的链表，每个节点都是一个 T(1) 构造的对象 //直接传入对象的话 list会自行拷贝多份
list<T> lst3(lst1.begin(),--lst1.end()); // 从别的列表中提取一部分作为当前列表，此例子中包含 8 个结点
3、初始化
可以使用 assign 方法对列表进行初始化。使用方法与构造函数基本相同，不赘述。
clear 方法清空列表。
lst.clear();
属性读取
size() // 获取列表的元素个数
empty() // 判断列表是否为空
int n = lst.size();
bool isEmpty = lst.empty();
栈操作
push_front([结点对象]); // 在列表头入栈
front();//获取列表头元素
pop_front();//列表头出栈
push_back([结点对象]);// 在列表尾入栈
back();
pop_back();
lst.push_front(t);
T t = lst.front();
lst.pop_front();
lst.push_back(t);
T t = lst.back();
lst.pop_back();
添加元素
insert 方法与构造函数相比多了一个插入位置而已。
insert ([插入位置], [结点对象]); // 就在插入位置这个相对位置插入元素，插入位置与之前元素的对应关系不会变，具体可以见下面的例子
insert ([插入位置], [结点个数], [结点对象]);
insert ([插入位置], [列表的起始位置], [列表的结束位置]);
//假设 lst2: 1 1 1 1 1 。此时迭代器 i 指向 第二个 1。t1 对应值为 3
j = lst2.insert(i, t1); // lst2: 1 3 1 1 1 1 // 在 i 位置的前面插入对象 t1，
// 此时迭代器 i 指向 第二个 1 ，迭代器 j 指向 第一个 3
j = lst2.insert(i, 3, t1);
j =lst2.insert(i, lst.begin(), lst.end());
查找元素
list 自身没有提供查找用的函数。需要使用STL的通用函数 find。
[迭代器] find([起始位置], [结束位置], [查找对象]); //
i = find(lst.begin(), lst.end(), t); // 注意：对于自己定义的类型，需要重载 '==' 运算符
删除元素
remove([迭代器指向的对象]);
erase([删除位置]); // 删除该位置的结点，返回该结点之后的迭代器
erase([起始位置], [结束位置]);// 删除 [起始位置，结束位置) 内的元素 ，返回结束位置的迭代器
lst.remove(*i);
i = lst.erase(i);
i = lst.erase(lst2.begin(), lst2.end());
比较
没有现成的比较函数。想要比较的话直接取出 结点对象 进行比较。
排序
sort() // 升序排列
sort([比较函数]) // a，b两个元素比较，如果 [比较函数] 返回真，则a 排在前面
lst.sort(); // 升序排列 // 需要自定义类型重载 '<' 运算符
lst.sort(cmp); // 此处为降序
unique操作
unique 操作可以把列表中的相同元素剔除掉，至于怎么样算是相同元素可以自行定义。
使用前必须先确保列表处于有序状态。因为 unique 操作元素的比较仅限于相邻元素。
unique();
unique([判别相等的函数]);
lst.unique();
lst.unique(equal);// equal 是个函数，能返回比较结果 // 在Xcode 6 上实测，仅支持基本类型或者STL类型的对象
lst.unique(Equal());// Equal 是个类，重载 '()' 操作符
merge 操作
两个列表在合并前应当处于有序状态，并且前后使用相同的比较逻辑，这样合并后的列表也是有序的，否则合并后的列表是无序列表。
merge([列表对象])
merge([列表对象], [比较函数])
lst.merge(lst2);
lst.merge(lst2,cmp);
遍历
由于列表是一个双向链表，不能通过迭代器间的大小比较判断链表是否到达末尾，需要使用 '!=' 。
for (list<T>::iterator i = lst.begin(); i != lst.end(); ++i){
cout << (*i).a;
}
示例代码
#include<list>
#include<iostream>
using namespace std;
#define Out(T) cout << T << endl;
struct T{
int a;
T(int a){
this->a = a;
}
T(){
a = 0;
}
// find 操作时用
friend bool operator ==(const T &a,const T &b){ // friend 不能缺
return a.a == b.a;
}
friend bool operator < (const T &a,const T &b){ // friend 不能缺
return a.a < b.a;
}
// unique 操作时用
bool operator() (const T &a, const T &b)
{
// return (a.a - b.a) < 5;
return a.a == b.a;
}
};
// sort 用
bool cmp(const T &a, const T &b){
return a.a > b.a;
}
// unique 用
bool equal(const T &a, const T &b){
return a.a == b.a;
}
bool myequal(const double a, const double b){
return a == b;
}
int main(){
////////////////////////////////////////////////
// 声明与定义
list<T> lst;
list<T> lst1(9);// 包含 9 个结点，每个结点按照 T 给的构造函数构建
list<T> lst2(5,T(1));// 建一个含5个元素的链表，每个节点都是一个 T(1) 构造的对象
list<T> lst3(lst1.begin(),--lst1.end()); // 从别的列表中提取一部分作为当前列表，此例子中包含 8 个结点
////////////////////////////////////////////////
// 属性读取
Out(lst1.empty()); // 输出 0
Out(lst3.size()); // 输出 8
////////////////////////////////////////////////
// 栈操作
T t(2);
lst.push_front(t); // lst: 2
T t1(3);
lst.push_front(t1); // lst: 3 2
lst.push_back(t1); // lst: 3 2 3
Out(lst.front().a); // 输出 3
if(!lst.empty()) lst.pop_back(); // lst: 3 2
if(!lst.empty()) lst.pop_front(); // lst: 2
////////////////////////////////////////////////
// 添加元素 （入栈与出栈）
T t2(4);
list<T>::iterator i = lst2.begin(); // 迭代器指向 第一个 1
lst2.insert(++i, t1); // lst2: 1 3 1 1 1 1 // 迭代器指向第二个 1 并在它的前面插入 t1
i = lst2.insert(++i, 3, t2); // lst2: 1 3 1 4 4 4 1 1 1 // 迭代器指向第三个 1 // 返回指向第一个 4 的迭代器
++i; // 迭代器指向第二个 4
lst2.insert(i,lst.begin(), lst.end()); // lst2: 1 3 1 4 2 4 4 1 1 1
// 查找元素
i = find(lst.begin(), lst.end(), T(1)); // 注意：对于自己定义的类型，需要重载 '==' 运算符
////////////////////////////////////////////////
// 删除元素
if (i != lst.end()) {
lst.remove(*i);
// i = lst.erase(i);
// i = lst.erase(lst2.begin(), lst2.end());
}
////////////////////////////////////////////////
// 排序
lst2.sort(); // 升序排列 // 需要自定义类型重载 '<' 运算符
lst2.sort(cmp); // 此处为降序
////////////////////////////////////////////////
// unique 操作
lst.unique();
// lst.unique(equal);// equal 是个函数，能返回比较结果 // 不支持自定义类型
lst2.unique(T());// Equal 是个类，重载 '()' 操作符
list<double> a(5,4);
a.unique(myequal); // 支持基本类型
// merge
lst3.assign(3, T(3));
lst2.sort();
lst3.sort();
lst2.merge(lst3);
lst2.merge(lst3,cmp);
////////////////////////////////////////////////
// 遍历元素
for (list<T>::iterator i = lst2.begin(); i != lst2.end(); ++i){
cout << (*i).a << ' ';
}
Out("");
}