C++之list容器介紹及使用方式
一、list底層結構
list底層是帶頭節(jié)點的雙向循環(huán)鏈表
- 雙向：可以從前往后，也可以從后往前遍歷
- 循環(huán)：找尾節(jié)點的時間復雜度為O( 1 )
- 帶頭節(jié)點：代碼實現簡單，不用考慮鏈表為空等特殊情況，可令end()迭代器指向頭節(jié)點的位置
二、構造方法
構造函數
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>類型的對象進行遍歷打?。?/p>
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對象的迭代器不支持加減數字，因為其底層空間不連續(xù)，如圖：
如果要往一個位置進行插入，可以通過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底層結構為帶頭結點的雙向循環(huán)鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節(jié)點的迭代器，其他迭代器不會受到影響。
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（動態(tài)順序表）
list（帶頭結點的雙向循環(huán)鏈表）
| 對比 | vector | list |
|---|---|---|
| 底層結構 | 動態(tài)順序表，連續(xù)空間 | 帶頭結點的雙向循環(huán)鏈表 |
| 訪問 | 支持隨機訪問，首地址+下標 | 不能隨機訪問，可通過find查找，訪問隨即元素時間復雜度O(N) |
| 插入刪除 | 任意位置插入和刪除效率低，需要搬移元素，時間復雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導致效率更低 | 任意位置插入和刪除效率高，不需要搬移元素，時間復雜度為O(1) |
| 空間利用率 | 底層為連續(xù)空間，不容易造成內存碎片，空間利用率較高，緩存利用率高。可以一次將一個數據附近的空間都加載到緩存，不用頻繁地從內存讀取數據 | 底層節(jié)點動態(tài)開辟，容易造成內存碎片，空間利用率低，緩存利用率低 |
| 迭代器 | 原生態(tài)指針 | 對指針進行了封裝 |
| 迭代器失效 | 容量相關的操作都有可能導致迭代器失效，如插入引起的擴容，刪除元素等 | 插入元素不會導致迭代器失效，刪除節(jié)點會導致，且只影響當前迭代器，其他迭代器不受影響 |
| 使用場景 | 不關心插入和刪除效率，支持隨機訪問 | 大量插入和刪除操作，不關心隨機訪問的場景 |
總結
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
多繼承容易讓代碼邏輯復雜、思路混亂，本文主要介紹了C++多繼承(多重繼承)的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
本文主要介紹了如何使用OpenCV C++對視頻中的人流量進行統(tǒng)計。文中的示例代碼講解詳細，對我們學習OpenCV有一定的幫助，需要的可以了解一下2022-01-01
下面小編就為大家?guī)硪黄猚語言實現詞頻統(tǒng)計的簡單實例。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-09-09
這篇文章主要介紹了C語言數據結構之順序數組的實現的相關資料,這里提供實現實例，希望通過本文能幫助到大家，需要的朋友可以參考下2017-08-08
JSON是一種對源自Javascript的對象數據進行編碼的格式,但現在被廣泛用作互聯(lián)網上的數據交換格式,本文主要介紹了Qt使用Json的項目實踐,詳細的介紹了主要使用的類以及Json實戰(zhàn),感興趣的可以了解一下2023-09-09
這篇文章主要介紹了C語言函數調用約定和返回值詳情，函數調用約定不同，會影響函數生成的符號名，函數入參順序，形參內存的清理者，更多相關需要的小伙伴可以參考下文詳情介紹2022-07-07
這篇文章主要介紹了C++設計模式之適配器模式,本文詳細講解了C++中的適配器模式,并給出了實現代碼,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細介紹了C語言數字圖像處理之直方圖均衡化，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
C++11標準提供了許多有用的新特性。這篇文章特別針對使C++11和C++98相比看上去像一門新語言的特性2017-03-03
頭文件保護機制是一種防止頭文件被重復包含的技術,它主要借助 #ifndef、#define 和 #endif 這些預處理指令來達成,本文就來詳細的介紹一下,感興趣的可以了解一下2025-04-04