list 是順序容器的一種厢呵。list 是一個雙向鏈表从诲。使用 list 需要包含頭文件 list果元。雙向鏈表的每個元素中都有一個指針指向后一個元素，也有一個指針指向前一個元素腾降，如圖1所示拣度。
在 list 容器中，在已經(jīng)定位到要增刪元素的位置的情況下螃壤，增刪元素能在常數(shù)時間內(nèi)完成抗果。如圖2所示，在 ai 和 ai+1 之間插入一個元素奸晴，只需要修改 ai 和 ai+1 中的指針即可冤馏。
list 容器不支持根據(jù)下標隨機存取元素。
list 的構(gòu)造函數(shù)和許多成員函數(shù)的用法都與 vector 類似蚁滋，此處不再列舉宿接。除了順序容器都有的成員函數(shù)外，list 容器還獨有如表 1 所示的成員函數(shù)（此表不包含全部成員函數(shù)辕录，且有些函數(shù)的參數(shù)較為復(fù)雜睦霎，表中只列出函數(shù)名）。
表1中列出的成員函數(shù)有些是重載的走诞，如 unique副女、merge、splice 成員函數(shù)都不止一個蚣旱， 這里不再一一列舉并解釋碑幅。后面對于其他容器以及算法的介紹，對于有重載的情況也不再指出塞绿。要詳細了解 STL沟涨，還需要查閱專門的 STL 手冊，或查看編譯器提供的聯(lián)機幫助异吻。
STL 中的算法 sort 可以用來對 vector 和 deque 排序裹赴，它需要隨機訪問迭代器的支持喜庞。因為 list 不支持隨機訪問迭代器，所以不能用算法 sort 對 list 容器排序棋返。因此延都，list 容器引入了 sort 成員函數(shù)以完成排序。
list 的示例程序如下：
#include <list> //使用 list 需要包含此頭文件
#include <iostream>
#include <algorithm> //使用STL中的算法需要包含此頭文件
using namespace std;
class A {
private: int n;
public:
A(int n_) { n = n_; }
friend bool operator < (const A & a1, const A & a2);
friend bool operator == (const A & a1, const A & a2);
friend ostream & operator << (ostream & o, const A & a);
};
bool operator < (const A & a1, const A & a2) {
return a1.n < a2.n;
}
bool operator == (const A & a1, const A & a2) {
return a1.n == a2.n;
}
ostream & operator << (ostream & o, const A & a) {
o << a.n;
return o;
}
template <class T>
void Print(T first, T last)
{
for (; first != last; ++first)
cout << *first << " ";
cout << endl;
}
int main()
{
A a[5] = { 1, 3, 2, 4, 2 };
A b[7] = { 10, 30, 20, 30, 30, 40, 40 };
list<A> lst1(a, a + 5), lst2(b, b + 7);
lst1.sort();
Print(lst1.begin(), lst1.end()); //輸出：1 2 2 3 4
lst1.remove(2); //刪除所有和A(2)相等的元素
Print(lst1.begin(), lst1.end()); //輸出：1 3 4
lst2.pop_front(); //刪除第一個元素
Print(lst2.begin(), lst2.end()); //輸出：30 20 30 30 40 40
lst2.unique(); //刪除所有和前一個元素相等的元素
Print(lst2.begin(), lst2.end()); //輸出：30 20 30 40
lst2.sort();
lst1.merge(lst2); //合并 lst2 到 lst1 并清空 lst2
Print(lst1.begin(), lst1.end()); //輸出：1 3 4 20 30 30 40
Print(lst2.begin(), lst2.end()); //lst2是空的睛竣，輸出：空
lst1.reverse(); //將 lst1 前后顛倒
Print(lst1.begin(), lst1.end()); //輸出 40 30 30 20 4 3 1
lst2.insert(lst2.begin(), a + 1, a + 4); //在 lst2 中插入 3,2,4 三個元素
list <A>::iterator p1, p2, p3;
p1 = find(lst1.begin(), lst1.end(), 30);
p2 = find(lst2.begin(), lst2.end(), 2);
p3 = find(lst2.begin(), lst2.end(), 4);
lst1.splice(p1, lst2, p2, p3); //將[p2, p3)插入p1之前晰房，并從 lst2 中刪除[p2,p3)
Print(lst1.begin(), lst1.end()); //輸出：40 2 30 30 20 4 3 1
Print(lst2.begin(), lst2.end()); //輸出：3 4
return 0;
}
應(yīng)用實例：用 list 解決約瑟夫問題。
約瑟夫問題是：有 n 只猴子射沟，按順時針方向圍成一圈選大王（編號為 1~n）殊者，從第 1 號開始報數(shù)，一直數(shù)到 m躏惋，數(shù)到 m 的猴子退到圈外幽污，剩下的猴子再接著從 1 開始報數(shù)嚷辅。就這樣簿姨，直到圈內(nèi)只剩下一只猴子時，這個猴子就是猴王簸搞。編程求輸入 n扁位、m 后,輸出最后猴王的編號。
輸入數(shù)據(jù)：每行是用空格分開的兩個整數(shù)趁俊，第一個是 n域仇，第二個是 m（0<m, n<=1 000 000）。最后一行是：
0 0
輸出要求：對于每行輸入數(shù)據(jù)（最后一行除外）寺擂，輸出數(shù)據(jù)也是一行暇务，即最后猴王的編號。
輸入樣例：
6 2
12 4
8 3
0 0
輸出樣例：
5
1
7
示例代碼
#include <list>
#include <iostream>
using namespace std;
int main()
{
list<int> monkeys;
int n, m;
while (true) {
cin >> n >> m;
if (n == 0 && m == 0){
break;
}
monkeys.clear(); //清空list容器
for (int i = 1; i <= n; ++i) { //將猴子的編號放入list
monkeys.push_back(i);
}
list<int>::iterator it = monkeys.begin();
while (monkeys.size() > 1) { //只要還有不止一只猴子怔软，就要找一只猴子讓其出列
for (int i = 1; i < m; ++i) { //報數(shù)
++it;
if (it == monkeys.end()){
it = monkeys.begin();
}
}
it = monkeys.erase(it); //刪除元素后垦细，迭代器失效，
//要重新讓迭代器指向被刪元素的后面
if (it == monkeys.end()){
it = monkeys.begin();
}
}
cout << monkeys.front() << endl; //front返回第一個元素的引用
}
return 0;
}
erase 成員函數(shù)返回被刪除元素后面那個元素的迭代器挡逼。如果被刪除的是最后一個元素括改，則返回 end()。
這個程序也可以用 vector 實現(xiàn)家坎，但是執(zhí)行速度要慢很多嘱能。因為 vector 的 erase 操作牽涉元素的移動，不能在常數(shù)時間內(nèi)完成虱疏，所花費的時間和容器中的元素個數(shù)有關(guān)惹骂；而 list 的 erase 操作只是修改幾個指針而已，可以在常數(shù)時間內(nèi)完成做瞪。當 n 很大（數(shù)十萬）時对粪，兩種寫法在速度上會有明顯區(qū)別。
