日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：安河橋畔 ? 更新時間： 2023-04-06 編程語言

一、list底層結構

list底層是帶頭節點的雙向循環鏈表

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

二、構造方法

構造函數

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 };

拷貝構造函數

利用l1拷貝構造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>類型的對象進行遍歷打印：

1.迭代器

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

打印結果：

2.范圍for

注意這里e是int類型，不用再進行解引用

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

打印結果：

3.反向迭代器

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

打印結果：

四、元素修改

尾插、頭插、尾刪、頭刪

insert、erase

list支持任意位置的插入，注意list對象的迭代器不支持加減數字，因為其底層空間不連續，如圖：

如果要往一個位置進行插入，可以通過find函數返回位置進行，find是一個通用的函數模板，返回值是傳入參數的迭代器類型，

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內置的交換函數

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

resize

resize改變有效元素的個數，多的元素用第resize二個參數填充，如果沒有給第二個參數，則默認用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的參數是一個判斷條件，可以是函數指針或者函數對象

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

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

unique、sort

unique，去重，刪除所有重復元素，使用unique之前要先調用sort進行排序，這里的sort是list內置的sort，不是標準庫中的sort

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

結果：

對于sort的使用，還可以自定義函數，并將函數指針作為參數傳遞給sort函數進行排序：

reverse

對鏈表進行逆置

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

結果：

六、list迭代器失效問題

list底層結構為帶頭結點的雙向循環鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。?

erase導致的迭代器失效

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

改正方法：

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

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

resize導致的迭代器失效

resize減少有效元素個數也會導致迭代器失效：

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

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

七、vector與list對比

vector（動態順序表）

list（帶頭結點的雙向循環鏈表）

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

總結

原文鏈接：https://blog.csdn.net/qq_44631587/article/details/126413746

欄目分類
最近更新