STL用環狀雙向鏈表來實現list，方法和leveldb的緩存環狀鏈表一樣，鏈表持有一個傀儡節點，不存儲數據，只為這個鏈表的入口。迭代鏈表時，首先通過鏈表獲得這個這個傀儡節點，然後通過next迭代所有數據。

STL將鏈表的傀儡節點作為鏈表的end節點，傀儡節點的next為begin節點，這樣以來，就可以用[begin,end)這種左閉右開的形式來表示迭代器範圍，和其他容器保持一致。

list節點結構

因為是雙向鏈表，所以有兩個指針，分別指向前向指針和後向指針。

迭代器類型

因為list數據不是存儲在連續的內存內，所以不能通過指針的加１減一來實現迭代器。list數據是通過指針鏈表結合在一起的，所以為了迭代所有數據，必須通過上個節點找到下個節點的地址，進而訪問下個節點。list迭代器就是用這個原理，實現如下:

以上就是list的迭代器實現，只實現了迭代器的++,--，取值，成員調用四個基本操作，並沒有像vector迭代器那樣的+n操作，主要是因為地址不連續。

list實現

接下來看下list實現，list只有一個成員變量，就是那個傀儡節點，也是end節點。

先來看構造函數:

這個構造函數為默認構造函數，就是創建一個節點，然後前後指向自己而已。說到配置器，由於list用的是自己定義節點結構體，所以也定義了相應類型的配置器。

list還定義幾種構造函數，用n個值來初始化list，將另一個list的一部分數據來初始化list和複製構造函數。

這幾個函數調用了fill_initialize和range_initialize，來看下這兩個函數。

這兩個函數最後分別調用了insert函數的不同版本。一起來看下這兩個insert函數。

這兩個函數通過循環調用 iterator insert(iterator position, const T& x) 這個insert版本，將數據一個一個插入到position之前，初始時就是插入到傀儡節點後面，形成初始鏈表，源碼如下:

最後看下析構函數

這兩個函數，clear是清空鏈表所有數據，然後put_node是將傀儡節點回收了。

一些小函數

最後一個交換兩個鏈表，只需要通過標準函數庫的swap函數，交換兩個傀儡節點即可，因為傀儡節點是每個鏈表的入口。

一些常用函數

往鏈表前插一個元素，通過調用insert完成。

往鏈表尾巴插一個元素，也是通過insert函數完成。

移除一個元素

這個函數也很簡單，只需要將被移除節點的前後節點跳過當前節點即可。

前後刪除一個節點，用erase函數實現:

transfer函數

這個函數是很多list接口調用的函數。這個函數有點難看懂，我把《STL源碼剖析》上的圖截下來，容易理解:

;

源碼如下:

按著序號來讀那個示意圖，應該能看懂，本質上就那幾個關鍵節點的前後關係。

有了這個函數之後，就出現了一些很有用的函數:

remove函數

將數值為value的所有元素移除:

merge函數

合併兩個鏈表，前提是兩個鏈表必須有序，合併之後的鏈表也是有序的。merge之後，x鏈表被清空了。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

template <class>

void list::merge(list

iterator first1 = begin();

iterator last1 = end();

iterator first2 = x.begin();

iterator last2 = x.end();

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函數

這個函數是用於將鏈表數據反序:

這裡要注意的是，在鏈表begin前插入元素，都將改變鏈表的begin。

sort函數

list不能使用STL的sort算法，因為STL的sort算法必須接受RamdonAccessIterator，而sort的迭代器為Bidirectional iterators，所以list自己實現了這個sort算法:

這個排序算法，本人看的也不是很懂，看了魚思故淵的博客，略懂程序執行流程。大家可以看他的博客。

當然list還提供了帶自定義比較的上述函數

list大概就這些就這些了。

看STL源碼真心可以學到東西，首先把基本數據結構複習了一遍，而且SGI裡的數據結構比平時寫的數據結構優秀多了。其次好好掌握了STL模板庫用法。最後就是學到一些細節的東西，比如int(),double()表示這種類型的默認值。