1. list功能
list是雙向循環鏈表，每一個元素都知道前面一個元素和後面一個元素.list對象自身提供了兩個pointer用來指向第一個和最後一個元素.每個元素都有pointer指向前一個和後一個元素.如果想要插入新元素,只需要操縱對應的pointer即可.因此list在幾個方面與array,vector不同:
- list不支持隨機訪問,如果你要訪問第5個元素,就得順著串鏈逐一爬過前4個元素.所以在list中隨機訪問一個元素是很緩慢的,然而你可以從兩端開始航行整個list,所以訪問第一個或最後一個元素速度很快.
- 任何位置上(不只兩端)執行元素的插入或刪除都非常快,因為無需移動任何其他元素.實際上內部只是進行了一些pointer操作而已.
- 插入和刪除動作並不會造成其他元素的各個pointer,reference和iterator失效.
- list對於異常的處理方式是:要麼操作成功,要麼什麼都不發生,絕對不會陷入”只成功一半”這種進退維谷的境地.
list所提供的成員函數反映出它與array,vector不同:
- list提供front(),push_front()和pop_front(),back(),push_back()和pop_back()等操作函數.
- 由於不支持隨機訪問,list既不提供下表操作符,也不提供at().
- list並未提供容量,空間重新分配等操作函數,因為完全無必要.每個元素都有自己的內存,在這個元素刪除前一直有效.
2.list操作
在使用list前必須包括頭文件#include
本文例子中到的兩個list對象c1,c2分別為c1(10,20,30) c2(40,50,60)。還有一個迭代器it = list::iterator用來指向c1或c2元素。
1)、list的構造函數和析構函數
listc; // 構造函數,產生一個空list,沒有任何元素
listc(c2); // copy 構造函數,建立c2的同類型list,並成為c2的一份拷貝
listc = c2; // copy 構造函數,建立一個新的list作為c2的拷貝
listc(rv); // move 構造函數,建立一個新的list,取rvalue rv的內容(始自C++11)
listc = c2; // move 構造函數,建立一個新的list,取rvalue rv的內容(始自C++11)
listc(initlist); // 建立一個list,以初值列initlist的元素為初值(始自C++11)
listc = initlist; // 建立一個list,以初值列initlist的元素為初值(始自C++11)
listc(n); // 利用元素的default構造函數生成一個大小為n的list
listc(n,elem); // 建一個含n個元素的list，值都是elem
listc(c1.begin(),c1.end()); // c含c1一個區域的元素[First, _Last)。
c.~list(); // 銷毀所有元素,釋放內存
2)、list的非易型操作
c.empty() // 返回容器是否為空(相當於size()==0但也許較快)
c.size() // 返回目前的元素個數
c.max_size() // 返回元素個數之最大可能量
c1 == c2 // 返回c1是否等於c2(對每個元素調用==)
c1 != c2 // 返回c1是否不等於c2(相當於!(c1 == c2))
c1 > c2 // 返回c1是否大於c2
c1 >= c2 // 返回c1是否大於等於c2
c1 < c2 // 返回c1是否小與c2
c1 <= c2 // 返回c1是否小與等於c2
3)、assign() 給list賦值：
c.assign(n,elem); // 復制n個elem,賦值給c
c.assign(beg,end); // 將區間[beg,end)內的元素賦值給c
c.assign(initlist); // 將初值列initlist所有元素賦值給c
4)、swap() 交換兩個list
c1.swap(c2); // 置換c1和c2的數據
swap(c1,c2); // 置換c1和c2的數據
5)、list元素直接訪問
front() 返回第一個元素 (不檢查是否存在第一個元素)
int i=c1.front(); // i=10
back() 返回最後一個元素 (不檢查是否存在最後一個元素)
int i=c1.back(); // i=30
6)、迭代器相關函數
begin() 返回一個迭代器,指向第一個元素
it=c1.begin(); // *it=10
end() 返回一個迭代器,指向最後一個元素的下一位置
it=c1.end(); //*(--it)=30;
rbegin() 返回一個反向迭代器, 指向反向迭代器第一個元素
list::reverse_iterator riter=c1.rbegin(); // *riter=30
rend() 返回一個反向迭代器, 指向反向迭代器最後一個元素的下一個位置
list::reverse_iterator riter=c1.rend(); // *(--riter)=10
cbegin() 返回一個const迭代器, 指向第一個元素 (始自C++11)
list::const_iterator citer=c1.cbegin(); // *citer=10且為const
cend() 返回一個const迭代器, 指向最後一個元素的下一個位置 (始自C++11)
list::const_iterator citer=c1.cend(); // *(--citer)=30且為const
crbegin() 返回一個const反向迭代器, 指向反向迭代器第一個元素 (始自C++11)
list::const_reverse_iterator criter=c1.crbegin(); // *criter=30且為const
crend() 返回一個const反向迭代器, 指向反向迭代器最後一個元素的下一個位置 (始自C++11)
list::const_reverse_iterator criter=c1.crend(); // *(--criter)=10且為const
7)、clear() 刪除所有元素
c1.clear(); //c1為空 c1.size為0；
8)、erase() 刪除一個元素 , 注意事項參照下面”注意事項1”
c1.erase(pos); // 移除pos位置上的元素,返回下一個元素的位置
c1.erase(beg,end); // 移除區間[beg,end)內所有元素,返回下一個元素的位置
9)、remove() 從list刪除元素
c.remove(val); // 移除所有其值為val的元素
10)、remove_if() 按指定條件刪除元素
c1.remove_if(op); // 移除所有"造成op(elem)結果為true"的元素
11)、resize() 改變list的大小
c1.resize(num) // 將元素數量改為num(如果size()變大,多出來的新元素都需以default構造函數完成初始化)
c1.resize(num,elem) // 將元素數量改為num(如果size()變大,多出來的新元素都是elem的拷貝)
12)、insert() 插入一個元素到list中
c.insert(pos,elem); // 在iterator位置pos之前插入一個elem拷貝,並返回新元素的位置
c1.insert(pos,n,elem); // 在iterator位置pos之前插入n個elem拷貝,並返回第一個新元素的位置(或返回pos--如果沒有新元素的話)
c1.insert(pos,beg,end); // 在iterator位置pos之前插入區間[beg,end)內所有元素的一份拷貝,並返回第一個新元素的位置(或返回pos--如果沒有新元素的話)
c1.insert(pos,initlist);// 在iterator位置pos之前插入初值列initlist內所有元素的一份拷貝,並返回第一個新元素的位置(或返回pos--如果沒有新元素的話;始自C++11)
例如:
c1.insert(++c1.begin(),100); // c1(10,100,20,30)
c1.insert(c1.begin(),2,200); // c1(200,200,20,30);
c1.insert(++c1.begin(),c2.begin(),--c2.end()); // c1(10,40,50,20,30);
c1.insert(++c1.begin(),{100,200}); // c1(10,100,200,20,30)
13)、emplace() 插入以args為初值的元素
c.emplace(pos,args...) // 在iterator位置pos之前插入一個以args為初值的元素,並返回新元素位置(始自C++11)
c.emplace_back(args...) // 在末尾插入一個以args為初值的元素,不返回任何東西(始自C++11)
c.emplace_front(args...) // 在起點插入一個以args為初值的元素,不返回任何東西(始自C++11)
14)、pop_back() 刪除最後一個元素 ,但是不返回它
c1.pop_back(); // c1(10,20);
15)、pop_front() 刪除第一個元素 ,但是不返回
c1.pop_front(); // c1(20,30)
16)、push_back() 在list的末尾添加一個元素
c1.push_back(100); // c1(10,20,30,100)
17)、push_front() 在list的頭部添加一個元素
c1.push_front(100); // c1(100,10,20,30)
18)、merge() 合並兩個list 並使之默認升序(也可改)
c.merge(c2) // 假設c和c2容器都包含op()准則下的已排序元素,將c2中的全部元素轉移到c,並保證合並後的list仍已排序
c.merge(c2,op) // 假設c和c2容器都包含已排序元素,將c2中的全部元素轉移到c,並保證合並後的list在op()准則下已排序
例如:
c2.merge(c1); //c1現為空;c2現為c2(10,20,30,40,50,60)
c2.merge(c1,greater()); //同上，但c2現為降序
19)、reverse() 把list的元素倒轉
c1.reverse(); // c1(30,20,10)
20)、sort() 給list排序, 默認升序(可自定義)
c.sort() // 以operator<為准則對所有元素排序
c.sort(op) // 以op()為准則對所有元素排序
例如:
c1.sort(); // c1(10,20,30)
c2.sort(greater()); //同上，但c1現為降序
21)、splice() 合並兩個list
c.splice(pos,c2) // 將c2內的所有元素轉移到c之內,迭代器pos之前
c.splice(pos,c2,c2pos) // 將c2內的c2pos所指元素轉移到c內pos之前
c.splice(pos,c2,c2beg,c2end) // 將c2內的[c2beg,c2end)區間內所有元素轉移到c內pos之前
例如:
c1.splice(++c1.begin(),c2); //c1(10,40,50,60,20,30) c2為空 全合並
c1.splice(++c1.begin(),c2,++c2.begin()); //c1(10,50,20,30) ; c2(40,60) 指定元素合並
c1.splice(++c1.begin(),c2,++c2.begin(),c2.end()); //c1(10,50,60,20,30); c2(40) 指定范圍合並
22)、unique() 刪除list中重復的元素
c.unique() // 如果存在若干相鄰而數值相同的元素,就移除重復元素,只留一個
c.unique(op) // 如果存在若干相鄰元素都使op()的結果為true,則移除重復元素,只留一個
例如:
c1.unique(); // 假設c1開始為(-10,10,10,20,20,-10),則之後為c1(-10,10,20,-10)
以上就是list的基本用法,實際使用中還需要注意一下幾點,後續遇到再加補充.
注意事項:erase使用注意 參考:http://blog.sina.com.cn/s/blog_66f74d9f0100om0f.html
常用的刪除容器中元素的方法是如下（方法1）：
list< int> List;
list< int>::iterator iter;
for( iter = List.begin(); iter != List.end(); )
{
if(1)
{
iter = List.erase( iter );
}
else
{
iter++;
}
}
也可以這樣寫（方法2）：
list< int> List;
list< int>::iterator iter;
for( iter = List.begin(); iter != List.end(); )
{
if(1)
{
List.erase( iter++ );
}
else
{
iter++;
}
}
有一種錯誤的寫法（注意同方法2比較）
list< int> List;
list< int>::iterator iter;
for( iter = List.begin(); iter != List.end(); )
{
if(1)
{
List.erase( iter );
}
iter++;
}
我們看一下erase()函數的源代碼（僅列出release下的代碼）。
iterator erase(iterator _Where)
{ // erase element at _Where
_Nodeptr _Pnode = (_Where++)._Mynode();
if (_Pnode != _Myhead)
{ // not list head, safe to erase
_Nextnode(_Prevnode(_Pnode)) = _Nextnode(_Pnode);
_Prevnode(_Nextnode(_Pnode)) = _Prevnode(_Pnode);
this->_Alnod.destroy(_Pnode);
this->_Alnod.deallocate(_Pnode, 1);
--_Mysize;
}
return (_Where);
}
函數在返回的時候，是返回當前迭代器的下一個節點。所以當 iter = List.erase( iter ); 執行以後，迭代器自動指向了下一個元素。而對於入參中的iter，所指的地址已經被銷毀，所以寫的時候，應該注意加上前面的iter =
那另外的一種寫法，List.erase( iter++ ); 為什麼也是對的呢？
研究了一下，這裡需要講一下++運算符的操作.
_Myt_iter& operator++()
{ // preincrement
++((_Mybase_iter )this);
return (*this);
}
_Myt_iter operator++(int)
{ // postincrement
_Myt_iter _Tmp = *this;
++*this;
return (_Tmp);
}
++實際上可以看做是一個函數。
對於++在後的情況（例如i++），函數在運行的時候，將運算的數據i已經改變，但是函數的返回值是操作之前的數據，所以在我們看來，i++好像是先進行了i的讀取，才+1。
回到迭代器，List.erase( iter++ );就沒有問題了。
對於那種錯誤的方法，List.erase( iter );在執行以後，iter所指的對象已經被銷毀，所以再對iter進行操作是非法的，程序會出錯。
