C++ 頭文件系列(list)

簡介

list實現的實際上是雙向鏈表，所以叫它doubly-linked list也許更好。 因為實現的是雙向鏈表，所以它有兩個非常重要的性質：

• 雙向
• 鏈表

雙向

雙向意味著----給定一個元素，我們能夠知道後一個元素和前一個元素。而這在單項鏈表裡是不可能實現的，因為單向鏈表只維護了單個方向的元素信息。

這種具體實現決定了，list的迭代器是雙向迭代器（Bidirectional Iterator）。

鏈表

優點

鏈表， 即 鏈▪表。 它暗示了鏈接的實質，也就是說，鏈表中的元素存儲單元不一定是順序的，只是通過繩子串連起來（-_-）。 這個事實導致了鏈表的特殊之處----插入和刪除操作是常數時間的。 因為執行這兩個操作的時候，我們只要修改單個元素兩邊的信息就可以了，不必動其他數據。 不像很多用數組作為內部結構的容器，這兩個操作往往需要移動一部分元素來維持元素位置的正確性。

缺點

當然了，禍福相依，鏈表的這種機制也導致了它某些方面的欠缺----元素的訪問不是常數時間的。 因為鏈表的順序是通過額外的數據來維護的（一般是指針），獲取元素往往在給定一個迭代器的基礎上通過遍歷來實現，因此在距離上是線性時間復雜度。

特殊函數

基於鏈表的特殊性質（常數時間的插入和刪除操作），list類模版提供了一些特殊的函數：

• splice：將一個list中的元素 拼接 到另一個list中。 標准文檔上給出的解釋是“destructively move elements from one list to another”，也就是說兩個list對象都會被影響。
• merge：合並兩個list，效果上像是splice的特例。
• remove、remove_if：移除相等的元素、移除滿足給定條件的元素。
• unique：移除重復的元素，也即使元素唯一。
• sort：對list進行排序。
• reverse：逆轉鏈表，這個對於雙向鏈表來說非常方便，只要交換一下頭尾指針的值就可以了。