??博主CSDN主頁(yè):杭電碼農(nóng)-NEO??
?
?專欄分類:C++從入門到精通?
?
??代碼倉(cāng)庫(kù):NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)C++
? ????

1. 前言

本質(zhì)重點(diǎn):

本章重點(diǎn)講解list的接口函數(shù)的熟悉
并且講解list迭代器失效的特性
最后講解迭代器的功能分類以及
算法庫(kù)函數(shù)中誰(shuí)能用誰(shuí)不能用

STL標(biāo)準(zhǔn)庫(kù)中的list是一個(gè)
帶頭雙向循環(huán)鏈表

和vector不同,list沒(méi)有支持[ ]訪問(wèn)
以及resize和reserve容量相關(guān)的函數(shù)
這是因?yàn)閘ist不能隨機(jī)訪問(wèn)數(shù)據(jù)

并且list的迭代器的底層明顯不是指針了
那它的底層到底是啥?
list會(huì)和vector一樣有迭代器失效問(wèn)題嗎?

帶著這些疑問(wèn),我們來(lái)進(jìn)入今天的學(xué)習(xí)分享

2. list的使用

我們還是在網(wǎng)站:cplusplus中查詢字典

和vector一樣,list也有兩個(gè)模板參數(shù)
但是第二個(gè)模板參數(shù)是和內(nèi)存效率相關(guān)的
所以現(xiàn)在的學(xué)習(xí)暫時(shí)不用管它(它有缺省值)

list的使用分為以下幾個(gè)階段進(jìn)行:

• list的構(gòu)造,析構(gòu),拷貝構(gòu)造函數(shù)
• list迭代器的使用
• list容量相關(guān)的操作
• list的增刪查改

2.1 list的構(gòu)造函數(shù)

list的構(gòu)造函數(shù):

第一個(gè)是無(wú)參構(gòu)造,直接跳過(guò)
第二個(gè)是用n個(gè)val初始化list對(duì)象
第三個(gè)是用一段迭代器區(qū)間構(gòu)造
第四個(gè)是用一個(gè)初始值構(gòu)造

看起來(lái)平平無(wú)奇,來(lái)實(shí)操一下:

list<int> l1;//無(wú)參構(gòu)造
list<int> l2(10,5);//用10個(gè)5初始化鏈表

vector<int> vv{1,2,3,4,5,6};
list<int> l3(vv.begin(),vv.end());//用迭代器區(qū)間初始化

list<char> l4('a');//用一個(gè)字符來(lái)初始化

list的拷貝構(gòu)造和析構(gòu)函數(shù)在使用
list時(shí)不會(huì)顯示調(diào)用,所以將它們忽略掉

2.2 list迭代器的使用

雖然list的迭代器底層不是指針
但是可以把它理解為指針來(lái)使用

這四個(gè)函數(shù)都是老朋友了,不多介紹了

唯一值得注意的是下圖:

begin和rend的指向相同
end和rbegin的指向相同

迭代器遍歷鏈表:

vector<int> vv{1,3,5,7,9,11,13,15};
list<int> l(vv.begin(),vv.end());

auto it = l.begin();
while(it!=l.end())
{
	cout << *it<< " ";
	it++;
}

范圍for遍歷鏈表:

vector<int> vv{1,3,5,7,9,11,13,15};
list<int> l(vv.begin(),vv.end());
for(auto x : l)
{
	cout << x<< " ";
}

注:list不支持隨機(jī)訪問(wèn),不能用[]

一個(gè)小tips:

在寫用迭代器遍歷容器時(shí),我們往往
會(huì)寫it!=l.end(),而不是it<l.end()
這是因?yàn)樵趌ist中,空間并不連續(xù),用小于
符號(hào)很大概率會(huì)出錯(cuò),但是在string
和vector中,空間是連續(xù)的,用<也沒(méi)問(wèn)題

2.3 list容量相關(guān)操作

這里最簡(jiǎn)單,和vector一模一樣

只有這四個(gè)函數(shù)接口比較常用!

2.4 list的增刪查改

首先映入眼簾的頭插/頭刪,尾插/尾刪

這幾個(gè)函數(shù)的意思很明了,直接跳過(guò)

insert插入:

insert函數(shù)要輸入一個(gè)迭代去位置進(jìn)行插入
可以插入一個(gè)數(shù)據(jù)或插入一段迭代器區(qū)間

erase刪除:

erase函數(shù)可以刪除一個(gè)迭代器的數(shù)據(jù)
或者刪除一段迭代器區(qū)間

clear清空有效元素:

list不像vector一樣有size和capacity
list的clear函數(shù)是將鏈表清空
(除頭節(jié)點(diǎn)外)

增刪查改實(shí)操:

vector<int> vv{1,5,10,15,20,100,120};
list<int> ll(vv.begin(),vv.end());
auto pos = find(ll.begin(),ll.end(),20);
ll.insert(pos,250);
ll.erase(ll.begin()+2);
ll.clear();

3. list迭代器失效問(wèn)題探討

由于list的底層是雙向帶頭循環(huán)鏈表
所以插入操作時(shí),pos指向的節(jié)點(diǎn)的
位置始終都是一個(gè)位置,它們只改變
鏈接關(guān)系,并不連續(xù),所以插入操作
并不會(huì)導(dǎo)致list迭代器失效

list迭代器失效只在erase刪除時(shí)才會(huì)發(fā)生
erase刪除的位置在空間上是唯一的
這個(gè)位置的數(shù)據(jù)被刪除后,只是改變了
數(shù)據(jù)的鏈接關(guān)系,然而此位置已經(jīng)不在
原先的鏈表中了,再次使用會(huì)出錯(cuò)!

STL庫(kù)的erase提供了返回值來(lái)解決問(wèn)題:

會(huì)返回被刪除位置的下一個(gè)位置的迭代器
以后可以這樣寫代碼來(lái)避免錯(cuò)誤:

list<int> ll{1,2,3,4,5,6,7,8};
auto it=ll.begin();
while(it!=ll.end())
{
	if((*it)%2==0)
	{
		it=erase(it);
	}
	else
	{
		it++;
	}
}

4. 算法庫(kù)函數(shù)和list的關(guān)系

首先,迭代器從功能角度可以分類為:

1. 正向迭代器: forward_iterator
2. 雙向迭代器: bidirectional_iterator
3. 隨機(jī)迭代器: random_iterator

它們分別支持且僅支持:

1. 只支持++
2. 支持++和- -
3. 支持++,- -,+和-

常見(jiàn)的容器以及它們的迭代器類型:

4.1 算法庫(kù)函數(shù)的迭代器類型

現(xiàn)在再來(lái)看算法庫(kù)的sort函數(shù):

它的函數(shù)模板支持的是隨機(jī)迭代器

再來(lái)看看算法庫(kù)的reverse函數(shù):

它的函數(shù)模板支持的是雙向迭代器

我先給出以下的結(jié)論:

1. 若函數(shù)模板給的隨機(jī)迭代器
   則只能傳有隨機(jī)迭代器的容器

2. 若函數(shù)模板給的雙向迭代器
   則可以傳有隨機(jī)或者雙向迭代器的容器

3. 若函數(shù)模板給的單向迭代器
   則三種迭代器都可以傳進(jìn)來(lái)!

可以看出它支持向上兼容!

4.2 list不能使用的算法庫(kù)函數(shù)

可見(jiàn),list是雙向迭代器,而sort函數(shù)的
函數(shù)模板是隨機(jī)迭代器
所以庫(kù)函數(shù)中的sort無(wú)法排序鏈表

但是仔細(xì)查閱字典可以發(fā)現(xiàn):
list類自己實(shí)現(xiàn)了一個(gè)不同于算法庫(kù)的排序

此排序?qū)ｉT用于排序list中的數(shù)據(jù)!

雖然list有自己的sort函數(shù)來(lái)排序
但是當(dāng)數(shù)據(jù)很多時(shí),list自我實(shí)現(xiàn)的
sort的效率低的驚人!甚至還不如
將list的數(shù)據(jù)導(dǎo)入vector容器
再在vector容器中使用算法庫(kù)的排序
排完序再導(dǎo)入到list中,這一步驟快!

5. 總結(jié)以及拓展

總的來(lái)說(shuō)list的使用和vector大同小異
當(dāng)然,要掌握l(shuí)ist,list的模擬實(shí)現(xiàn)是不可少的
list的模擬實(shí)現(xiàn)將在下一節(jié)分享給大家

本章筆記:

1. 請(qǐng)自行熟悉list接口函數(shù)

2. list的insert不會(huì)導(dǎo)致迭代器失效
   而erase會(huì)致使迭代器失效

3. 迭代器從功能上可以劃分為三種
   它們向上兼容彼此

4. list不能使用算法庫(kù)中的sort
   但list類中實(shí)現(xiàn)了專門排序鏈表的函數(shù)

拓展閱讀:

迭代器相關(guān)拓展知識(shí)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-697355.html

到了這里，關(guān)于【C++進(jìn)階(四)】STL大法--list深度剖析&list迭代器問(wèn)題探討的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！