一、list概述
- 底層是使用連結清單實作的，支援雙向順序通路
- 在list中任何位置進行插入和删除的速度都很快
- 不支援随機通路，為了通路一個元素，必須周遊整個容器
- 與其他容器相比，額外記憶體開銷大
- 設計目的：令容器在任何位置進行插入和删除都很快
- 何時使用：
- 容器需要不斷地在中間插入或删除元素
- 無論删除還是增加，list的疊代器、引用、指針都不會失效
- 與其他容器的比較：
| vector | 可變大小數組。支援快速随機通路。在尾部之外的位置插入或删除元素可能很慢 |
| deque | 雙端隊列。支援快速随機通路。在頭尾插入/删除速度很快 |
| list | 雙向連結清單。隻支援雙向順序通路。在list中任何位置進行插入和删除的速度都很快 |
| forward_list | 單向連結清單。隻支援單向順序通路。在連結清單任何位置進行插入和删除操作速度都很快 |
| array | 固定大小數組。支援快速随機通路。不能添加或删除元素 |
| string | 與vector相似的容器，但專門用于儲存字元。随機通路快。在尾部插入或删除速度快 |
二、list的節點（__list_node）
- list的每個節點是一個結構體。以下是list的節點（node）結構：
源碼
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer prev; //類型為void*。其實可設為__list_node<T>*
void_pointer next;
T data;
};
三、list的疊代器
- list不再能夠 vector一樣以原生名額做為疊代器，因為其節點不保證在儲存空間中連續存在
- list疊代器必須有能力指向list的節點，并有能力做正确的遞增、遞減、取值、成員存取等動作。所謂“list疊代器正确的遞增、遞 減、取值、成員取用”動作是指：遞增時指向下一個節點，遞減時指向上一個節點，取值時取的是節點的資料值，成員取用時取用的是節點的成員，如下圖所示：
- 由于list是一個雙向連結清單（double linked-list），疊代器必須具備前移、後移的能力。是以list提供的是Bidirectional Iterators
- list有以下幾個重要性質：
- 插入動作（insert）和接合動作（splice）都不會造成原有的 list 疊代器失效。這在vector是不成立的，因為 vector的插入動作可能造成記憶體重新配置，導緻原有的疊代器全部失效
- 甚至list的元素删除動作（erase），也隻有“指向被删除元素”的那個疊代器失效，其他疊代器不受任何影響
疊代器源碼
template<class T, class Ref, class Ptr>
struct list_iterator {
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; / 疊代器内部當然要有一個原生名額，指向list的節點
// constructor
list_iterator(link_type x) : node(x) {}
list_iterator() {}
list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 以下對疊代器取值（dereference），取的是節點的資料值
reference operator*() const { return (*node).data; }
// 以下是疊代器的成員存取（member access）運算子的标準作法
pointer operator->() const { return &(operator*()); }
//對疊代器累加1，就是前進一個節點
self& operator++()
node = (link_type)((*node).next);
return *this;
}
self operator++(int)
self tmp = *this;
++*this;
return tmp;
}
//對疊代器遞減1，就是後退一個節點
self& operator--()
node = (link_type)((*node).prev);
return *this;
}
self operator--(int)
self tmp = *this;
--*this;
return tmp;
}
};
四、list的資料結構
- list不僅是一個雙向串行，而且還是一個環狀雙向連結清單。是以它隻需要一個指針，便可以完整表現整個連結清單
link_type、node節點
template <class T, class Alloc = alloc> //預設使用alloc為配置器
class list {
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; // 隻要一個指針，便可表示整個環狀雙向連結清單
...
};
begin()、end()等函數
- 如果讓名額node指向刻意置于尾端的一個空白節點，node便能符合STL對于“前閉後開”區間的要求，成為last疊代器，如下圖所示。這麼一來，以幾個函數便都可以輕易完成：
iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
bool empty() const { return node->next == node; }
size_type size() const {
size_type result = 0;
distance(begin(), end(), result); // 全局函式，第 3章。
return result;
}
// 取頭節點的内容（元素值）
reference front() { return *begin(); }
// 取尾節點的内容（元素值）
reference back() { return *(--end()); }
五、list的構造與記憶體管理（constructor、push_back、insert）
list的記憶體管理（list_node_allocator）
- list預設使用alloc做為空間配置器，并據此另外定義了一個list_node_allocator，為的是更友善地以節點大小為配置機關：
template <class T, class Alloc = alloc> //預設使用alloc為配置器
class list {
protected:
typedef __list_node<T> list_node;
// 專屬之空間配置器，每次配置一個節點大小：
typedef simple_alloc<list_node, Alloc> list_node_allocator;
...
};
于是，list_node_allocator(n) 表示配置n個節點空間。以下四個函數，分别用來配置、釋放、建構、摧毀一個節點：
protected:
// 配置一個節點并傳回
link_type get_node() { return list_node_allocator::allocate(); }
// 釋放一個節點
voidput_node(link_typep){list_node_allocator::deallocate(p);}
// 産生（配置并構造）一個節點，帶有元素值
link_type create_node(const T& x) {
link_type p = get_node();
construct(&p->data, x);//全局函數，構造/析構基本工具
return p;
}
// 摧毀（解構并釋放）一個節點
void destroy_node(link_type p) {
destroy(&p->data); //全局函數，構造/析構基本工具
put_node(p);
}
構造函數
- list 提供有許多constructors，其中以個是default constructor，允許我們不指 定任何參數做出一個空的list出來：
public:
list() { empty_initialize(); } //産生一個空連結清單
protected:
void empty_initialize()
node = get_node(); //配置一個節點空間，令node指向它
node->next = node; //令node頭尾都指向自己，不設元素值
node->prev = node;
}
- list為空時， node節點的prev、next指向于自己
push_back、insert
- 當我們以push_back()将新元素插入于list尾端，此函數内部調用insert()：
void push_back(const T& x) { insert(end(), x); }
- insert()是一個重載函數，有多種形式，其中最簡單的以種如下，符合以上所需。首先配置并構造一個節點，然後在尾端進行适當的指針動作，将新節點插入進去：
//函數目的：在疊代器 position 所指位置插入一個節點，内容為x
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x);//産生一個節點（設妥内容為x）
//調整雙向指針，使 tmp插入進去
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
- 于是，如果程式連續插入了五個節點（其值為0、1、2、3、4）之後，list的狀态如下圖所示
- 如果我們希望在list内的某處安插新節點，首先必須确定安插位置， 例如我希望在資料值為3的節點處插入一個資料值為99的節點，可以這麼做：
- ilite = find(il.begin(), il.end(), 3);
- if (ilite!=0)
- il.insert(ilite, 99);
- find()操作稍後再做說明。插入之後的list狀态如下圖所示。注意，插入完成後， 新節點将位于标兵疊代器（标示出插入點）所指之節點的前方——這是STL對于 “插入動作”的标準規範。由于list不像vector 那樣有可能在空間不足時做重新配置、資料移動的操作，是以插入前的所有疊代器在插入動作之後都仍然有效
六、list的元素操作
push_front、push_back
//插入一個節點，做為頭節點
void push_front(const T& x) { insert(begin(), x); }
//插入一個個節點，做為尾節點
void push_back(const T& x) { insert(end(), x); }
erase
//移除疊代器position所指節點
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
- 由于list是一個雙向環狀連結清單，隻要我們把邊際條件處理好，那麼，在頭部或尾部插入元素（push_front 和 push_back），動作幾乎是一樣的，在頭部或尾部移除元素（pop_front和pop_back），動作也幾乎是一樣的。移除（erase） 某個疊代器所指元素，隻是做一些指針搬移動作而已，并不複雜。如果上圖再經以下搜尋并移除的動作，狀況将如下圖所示
ite = find(ilist.begin(), ilist.end(), 1);
if (ite!=0)
cout << *(ilist.erase(ite)) << endl;
pop_front、pop_back
//移除頭節點
void pop_front() { erase(begin()); }
//移除尾節點
void pop_back()
iterator tmp = end();
erase(--tmp);
}
clear
// 清除所有節點（整個連結清單）
template <class T, class Alloc>
void list<T, Alloc>::clear()
{
link_type cur = (link_type) node->next; //begin()
while (cur != node) { //周遊每一個節點
link_type tmp = cur;
cur = (link_type) cur->next;
destroy_node(tmp); // 銷毀（析構并釋放）一個節點
}
//恢複node原始狀态
node->next = node;
node->prev = node;
}
remove
//将數值為value之所有元素移除
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) { //周遊每一個節點
iterator next = first;
++next;
if (*first == value)
erase(first); //找到就移除
first = next;
}
}
unique
//移除數值相同的連續元素。注意，隻有“連續而相同的元素”，才會被移除剩一個
template <class T, class Alloc>
void list<T, Alloc>::unique()
{
iterator first = begin();
iterator last = end();
if (first == last)
return; //空連結清單，什麼都不必做
iterator next = first;
while (++next != last) { //周遊每一個節點
if (*first == *next) //如果在此區段中有相同的元素
erase(next); //移除之
else
first = next; //調整指針
next = first; //修正區段範圍
}
}
transfer
- list内部提供一個所謂的遷移動作（transfer）：将某連續範圍的元素遷移到某個特定位置之前。技術上很簡單，節點間的指針移動而已
- 這個動作為其他的複雜動作如splice, sort, merge等奠定良好的基礎
- 下面是transfer的源碼，transfer不是公開接口：
protected:
//将[first,last)内的所有元素搬移到position之前
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
(*(link_type((*last.node).prev))).next = position.node; // (1)
(*(link_type((*first.node).prev))).next = last.node; // (2)
(*(link_type((*position.node).prev))).next = first.node; // (3)
link_type tmp = link_type((*position.node).prev); // (4)
(*position.node).prev = (*last.node).prev; // (5)
(*last.node).prev = (*first.node).prev; // (6)
(*first.node).prev = tmp; // (7)
}
}
splice
- 上述的transfer并非公開接口。list公開提供的是所謂的接合動作（splice）：将某連續範圍的元素從一個list搬移到另一個（或同一個）list 的某個定點
- 下面是一個示範案例：
int iv[5] = { 5,6,7,8,9 };
list<int> ilist2(iv, iv+5);
//假設ilist的内容為0 2 99 3 4
ite = find(ilist.begin(), ilist.end(), 99);
ilist.splice(ite,ilist2); // 0 2 5 6 7 8 9 99 3 4
ilist.reverse(); // 4 3 99 9 8 7 6 5 2 0
ilist.sort(); // 0 2 3 4 5 6 7 8 9 99
- 很容易便可看出效果。下圖顯示接合動作。技術上很簡單，隻是節點間的指針移動而已，這些動作已完全由transfer()做掉了
- 為了提供各種接口彈性，list::splice有許多版本：
public:
//将x接合于position所指位置之前。x必須不同于*this
void splice(iterator position, list& x) {
if (!x.empty())
transfer(position, x.begin(), x.end());
}
//将i所指元素接合于position所指位置之前。position和i可指向同一個list
void splice(iterator position, list&, iterator i) {
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
//将[first,last) 内的所有元素接合于 position 所指位置之前
//position 和[first,last)可指向同一個list，
//但position不能位于[first,last)之内
void splice(iterator position, list&, iterator first, iterator last) {
if (first != last)
transfer(position, first, last);
}
- 以下是 merge(), reverse(), sort()的源碼。有了transfer()在手，這些動作都不難完成
merge()
// merge()将x合并到*this身上。兩個lists的内容都必須先遞增排序
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
// 注意：前提是，兩個lists都已經經過遞增排序
while (first1 != last1 && first2 != last2)
if (*first2 < *first1) {
iterator next = first2; transfer(first1,
first2, ++next);
first2 = next;
}
else
++first1;
if (first2 != last2)
transfer(last1, first2, last2);
}
reverse()
//reverse()将*this的内容逆向重置
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
//以下判斷，如果是空連結清單，或僅有一個元素，就不做任何動作
//使用 size() == 0 || size() == 1 來判斷，雖然也可以，但是比較慢
if (node->next == node || link_type(node->next)->next == node)
return;
iterator first = begin();
++first;
while (first != end()) {
iterator old = first;
++first;
transfer(begin(), old, first);
}
}
sort()
//list不能使用STL算法sort()，必須使用自己的sort() member function，
//因為STL算法 sort()隻接受RamdonAccessIterator.
//本函數采用 quick sort
template <class T, class Alloc>
void list<T, Alloc>::sort() {
// 以下判斷，如果是空連結清單，或僅有一個元素，就不做任何動作
// 使用 size() == 0 || size() == 1 來判斷，雖然也可以，但是比較慢
if (node->next == node || link_type(node->next)->next == node)
return;
//一些新的lists，做為中介資料存放區
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill)
++fill;
}
for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}
![2017年團體程式設計天梯賽-決賽小結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)