欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++之list容器介紹及使用方式

 更新時間:2023年02月05日 15:57:12   作者:安河橋畔  
這篇文章主要介紹了C++之list容器介紹及使用方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教

一、list底層結(jié)構(gòu)

list底層是帶頭節(jié)點的雙向循環(huán)鏈表

  • 雙向:可以從前往后,也可以從后往前遍歷
  • 循環(huán):找尾節(jié)點的時間復(fù)雜度為O( 1 )
  • 帶頭節(jié)點:代碼實現(xiàn)簡單,不用考慮鏈表為空等特殊情況,可令end()迭代器指向頭節(jié)點的位置

二、構(gòu)造方法

構(gòu)造函數(shù)

list<int> l1;
list<int> l2(5, 3);
//迭代器
vector<int> v{ 1,2,3,4,5 };
list<int> l3(v.begin(), v.end());
//C++11
list<int> l4{ 1,2,3,4,5 };

拷貝構(gòu)造函數(shù)

利用l1拷貝構(gòu)造l2

list<int> l1{ 1,2,3,4,5 };
list<int> l2(l1);

三、元素訪問和迭代器

back&front

list<int> l1{ 1,2,3,4,5 };
cout << l1.front() << endl;
cout << l1.back() << endl;

三種遍歷方式

list<int> l1{ 1,2,3,4,5 };

采用下面三種方式對下面這個list<int>類型的對象進(jìn)行遍歷打?。?/p>

1.迭代器

list<int>::iterator it = l1.begin();
for (it; it != l1.end(); it++)
{
	cout << *it << " ";
}
cout << endl;

打印結(jié)果:

2.范圍for

注意這里e是int類型,不用再進(jìn)行解引用

//范圍for
for (auto e : l1)
{
	cout << e << " ";
}
cout << endl;

打印結(jié)果:

3.反向迭代器

list<int>::reverse_iterator rit = l1.rbegin();
for (rit; rit != l1.rend(); rit++)
{
	cout << *rit << " ";
}
cout << endl;

打印結(jié)果:

四、元素修改

尾插、頭插、尾刪、頭刪

insert、erase

list支持任意位置的插入,注意list對象的迭代器不支持加減數(shù)字,因為其底層空間不連續(xù),如圖:

如果要往一個位置進(jìn)行插入,可以通過find函數(shù)返回位置進(jìn)行,find是一個通用的函數(shù)模板,返回值是傳入?yún)?shù)的迭代器類型,

list<int> l1{ 1,2,3,4,5 };
l1.insert(find(l1.begin(), l1.end(), 3), 10);//任意位置插入
l1.erase(find(l1.begin(), l1.end(), 10), l1.end());//任意位置的刪除

swap

list內(nèi)置的交換函數(shù)

list<int> l1{ 1,2,3,4,5 };
list<int> l2{ 5,6,7,8,9 };
l1.swap(l2);

resize

resize改變有效元素的個數(shù),多的元素用第resize二個參數(shù)填充,如果沒有給第二個參數(shù),則默認(rèn)用T()。

list<int> l1{ 0,1,2 };
l1.resize(5, 3);

五、特殊操作

remove

刪除值為value的元素

list<int> l1{ 3,0,1,3,2,3 };
l1.remove(3);

remove_if

remove_if的參數(shù)是一個判斷條件,可以是函數(shù)指針或者函數(shù)對象

//判斷5的倍數(shù)
bool MultipleFive(int n)
{
	return 0 == n % 5;
}

void Test10()
{
	//此處傳遞函數(shù)指針
	list<int> l1{ 10,0,1,3,5,7,20 };
	l1.remove_if(MultipleFive);
}

unique、sort

unique,去重,刪除所有重復(fù)元素,使用unique之前要先調(diào)用sort進(jìn)行排序,這里的sort是list內(nèi)置的sort,不是標(biāo)準(zhǔn)庫中的sort

void Test()
{
	list<int> l1{ 1,3,3,5,4,0,2,5,4 };
	l1.sort();//默認(rèn)升序
	l1.unique();//刪除重復(fù)元素
}

結(jié)果:

對于sort的使用,還可以自定義函數(shù),并將函數(shù)指針作為參數(shù)傳遞給sort函數(shù)進(jìn)行排序:

reverse

對鏈表進(jìn)行逆置

void Test()
{ 
	list<int> l1{ 1,3,5,7,9 };
	l1.reverse();
}

結(jié)果:

六、list迭代器失效問題

list底層結(jié)構(gòu)為帶頭結(jié)點的雙向循環(huán)鏈表,因此在list中進(jìn)行插入時是不會導(dǎo)致list的迭代器失效的,只有在刪除時才會失效,并且失效的只是指向被刪除節(jié)點的迭代器,其他迭代器不會受到影響。 

erase導(dǎo)致的迭代器失效

如圖所示,it迭代器所指向的位置被刪除后,迭代器失效:

改正方法:

while (it != l1.end())
{
	//it=l1.erase(it);
	l1.erase(it++);
}

這里 l1.erase(it++)語句也能達(dá)到效果,因為后置++會將自增后的結(jié)果保存在臨時變量中,而前置則不可以。 

resize導(dǎo)致的迭代器失效

resize減少有效元素個數(shù)也會導(dǎo)致迭代器失效:

list<int> l1{ 1,3,5,7,9 };
auto it = l1.end();
l1.resize(3);

上面這個程序中,reseze減少有效元素個數(shù)后,it指向的位置元素已經(jīng)被刪除,迭代器失效,如果再使用該迭代器,則會出錯。

七、vector與list對比

vector(動態(tài)順序表)

list(帶頭結(jié)點的雙向循環(huán)鏈表)

對比vectorlist
底層結(jié)構(gòu)動態(tài)順序表,連續(xù)空間帶頭結(jié)點的雙向循環(huán)鏈表
訪問支持隨機(jī)訪問,首地址+下標(biāo)不能隨機(jī)訪問,可通過find查找,訪問隨即元素時間復(fù)雜度O(N)
插入刪除任意位置插入和刪除效率低,需要搬移元素,時間復(fù)雜度為O(N),插入時有可能需要增容,增容:開辟新空間,拷貝元素,釋放舊空間,導(dǎo)致效率更低任意位置插入和刪除效率高,不需要搬移元素,時間復(fù)雜度為O(1)
空間利用率底層為連續(xù)空間,不容易造成內(nèi)存碎片,空間利用率較高,緩存利用率高。可以一次將一個數(shù)據(jù)附近的空間都加載到緩存,不用頻繁地從內(nèi)存讀取數(shù)據(jù)底層節(jié)點動態(tài)開辟,容易造成內(nèi)存碎片,空間利用率低,緩存利用率低
迭代器原生態(tài)指針對指針進(jìn)行了封裝
迭代器失效容量相關(guān)的操作都有可能導(dǎo)致迭代器失效,如插入引起的擴(kuò)容,刪除元素等插入元素不會導(dǎo)致迭代器失效,刪除節(jié)點會導(dǎo)致,且只影響當(dāng)前迭代器,其他迭代器不受影響
使用場景不關(guān)心插入和刪除效率,支持隨機(jī)訪問大量插入和刪除操作,不關(guān)心隨機(jī)訪問的場景

總結(jié)

以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。 

相關(guān)文章

最新評論