🌟🌟所屬專欄：C++、STL

目錄

前言

list簡(jiǎn)介

一、list的默認(rèn)成員函數(shù)

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

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

賦值重載

二、list的迭代器接口

迭代器的功能分類

三、list的容量接口

empty

size

四、list的元素訪問(wèn)接口

front和back

五、list的增刪查改

push_front

pop_front

push_back

pop_back

insert和erase

swap

resize

clear

find

六、list的其他操作接口

splice

remove

remove_if

unique

merge

sort

reverse

總結(jié)

前言

? ? ? ? 之前我們已經(jīng)學(xué)習(xí)了string、vector兩個(gè)容器的使用方法及模擬實(shí)現(xiàn)，今天跟大家介紹list的使用方法。

? ? ? ? 到了這個(gè)階段，我們應(yīng)該認(rèn)識(shí)到：在STL中，盡管容器各異，但同名接口的功能往往是相似的。因此，在我們掌握了少數(shù)幾個(gè)容器的使用方法后，對(duì)于未曾接觸過(guò)的其他容器，只要了解其底層數(shù)據(jù)結(jié)構(gòu)，就基本能夠上手使用它們。

list簡(jiǎn)介

????????list是STL中的一種容器，用于表示鏈表結(jié)構(gòu)，底層實(shí)現(xiàn)是一個(gè)雙向帶頭循環(huán)鏈表。如果你對(duì)雙向帶頭循環(huán)鏈表不太了解，可以參閱這篇文章：

【數(shù)據(jù)結(jié)構(gòu)】雙向帶頭循環(huán)鏈表（c語(yǔ)言）（附源碼）_c語(yǔ)言雙向環(huán)鏈表初始化-CSDN博客

list在插入和刪除操作方面非常高效，但在遍歷和隨機(jī)訪問(wèn)方面可能不如數(shù)組或者vector高效。因此，在選擇容器時(shí)，需要根據(jù)具體的應(yīng)用場(chǎng)景和需求進(jìn)行權(quán)衡。

我們?cè)谑褂胠ist時(shí)，需要引頭文件<list>，并且該容器定義在命名空間std當(dāng)中。

list相關(guān)接口查閱：

list - C++ Reference

一、list的默認(rèn)成員函數(shù)

????????list顯示實(shí)現(xiàn)的默認(rèn)成員函數(shù)有三個(gè)：分別是構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值重載。?

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

c++11下，list共有六個(gè)構(gòu)造函數(shù)，其中較為常用的有如下五種：

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;//無(wú)參構(gòu)造list<int> l2(5, 3);//n個(gè)val值構(gòu)造list<int> l3(l2);//拷貝構(gòu)造list<int> l4(l2.begin(), l2.end());//迭代器區(qū)間構(gòu)造list<int> l5({ 1,2,3,4,5 });//初始化器構(gòu)造cout << "l1: ";print(l1);cout << "l2: ";print(l2);cout << "l3: ";print(l3);cout << "l4: ";print(l4);cout << "l5: ";print(l5);return 0;
}

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

釋放動(dòng)態(tài)分配的內(nèi)存空間，在對(duì)象聲明周期結(jié)束時(shí)自動(dòng)調(diào)用。

賦值重載

將新內(nèi)容分配給已經(jīng)存在的容器，替換其當(dāng)前內(nèi)容，并相應(yīng)地修改其大小。較為常用的賦值重載有兩個(gè)：

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });l1 = l2;//將l2賦值給l1print(l1);l1 = { 5,4,3,2,1 };//初始化器賦值print(l1);return 0;
}

二、list的迭代器接口

迭代器接口在string和vector中的使用方法大致相同，這里就不多介紹。

由于list元素的內(nèi)存地址是不連續(xù)的，因此在迭代器的實(shí)現(xiàn)上，它與vector和string存在較大差異。我們將在list模擬實(shí)現(xiàn)的部分中對(duì)此進(jìn)行深入探討。

我們?cè)谶@里重點(diǎn)講一下迭代器的功能分類：

迭代器的功能分類

根據(jù)功能強(qiáng)弱，迭代器可以分為以下三種：

1. 單向迭代器：它僅支持在容器中進(jìn)行從頭到尾的遍歷操作，重載了“++”運(yùn)算符。

2. 雙向迭代器：它支持從頭到尾的遍歷和從尾到頭的遍歷，重載了“++”和“--”運(yùn)算符。

3. 隨機(jī)迭代器：顧名思義，它不僅支持雙向的遍歷，還支持隨機(jī)位置的訪問(wèn)，重載了“++”“--”“+”“-”等運(yùn)算符。

這三種迭代器的功能是向下兼容的，即隨機(jī)迭代器具有雙向迭代器的功能，而雙向迭代器具有單向迭代器的功能。

為什么會(huì)有這樣的分類呢？其實(shí)這是由底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)導(dǎo)致的。

????????有些數(shù)據(jù)結(jié)構(gòu)元素的內(nèi)存地址連續(xù)，還能夠支持雙向遍歷，并且遍歷效率高，那么就可以支持隨機(jī)迭代器（例如string、vector）；有些數(shù)據(jù)結(jié)構(gòu)能夠支持雙向遍歷，但是隨機(jī)訪問(wèn)的效率低下，那就支持雙向迭代器（例如list）；有些數(shù)據(jù)結(jié)構(gòu)只能做到從前向后訪問(wèn)元素，那么就只能支持單向迭代器（例如單鏈表forward_list）。

所以我們?cè)谑褂?strong>string、vector的迭代器時(shí)，可以使用“+”“-”操作符進(jìn)行隨機(jī)訪問(wèn)；而對(duì)于list，就只能通過(guò)“++”“--”來(lái)移動(dòng)迭代器指向的位置。

三、list的容量接口

三個(gè)容量接口當(dāng)中，前兩個(gè)比較常用，我們重點(diǎn)介紹一下：

empty

empty函數(shù)用于判斷該列表容器是否為空（即元素個(gè)數(shù)是否為0）。注意：該函數(shù)不會(huì)以任何方式修改容器。

size

size函數(shù)用于獲取容器內(nèi)元素的個(gè)數(shù)。?

代碼示例：

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });cout << "l1.size(): " << l1.size() << endl;cout << l1.empty() << endl;cout << "l2.size(): " << l2.size() << endl;cout << l2.empty() << endl;return 0;
}

四、list的元素訪問(wèn)接口

front和back

front函數(shù)返回對(duì)列表容器中第一個(gè)元素的引用，在空容器上調(diào)用此函數(shù)會(huì)導(dǎo)致未定義行為。

back函數(shù)返回對(duì)列表容器中最后一個(gè)元素的引用，在空容器上調(diào)用此函數(shù)會(huì)導(dǎo)致未定義行為。

代碼示例：

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l = { 1,2,3,4,5 };cout << l.front() << endl;cout << l.back() << endl;return 0;
}

相比vector的元素訪問(wèn)接口，list缺少了operator[ ]和at。是因?yàn)樗鼈儾荒軐?shí)現(xiàn)嗎？當(dāng)然不是，而是由于鏈表的特殊結(jié)構(gòu)。如果實(shí)現(xiàn)了這兩個(gè)接口，則使用時(shí)都需要遍歷元素，效率的代價(jià)是很大的。

五、list的增刪查改

在涉及增刪查改操作的接口中，鑒于部分接口功能有所重復(fù)，博主僅挑選幾個(gè)進(jìn)行介紹。

push_front

push_front的功能是在容器的開(kāi)頭插入一個(gè)新元素，就在它當(dāng)前的第一個(gè)元素之前。val的內(nèi)容被復(fù)制（或移動(dòng)）到插入的元素中。這有效地將容器大小增加了1。

pop_front

pop_front的功能是刪除列表容器中的第一個(gè)元素，有效地將其大小減小1。這將破壞被刪除的元素。

push_back

push_back的作用是在容器的末尾插入一個(gè)新元素。val的內(nèi)容被復(fù)制（或移動(dòng)）到新元素中。這有效地將容器大小增加了1。

pop_back

pop_back的作用是刪除容器中的最后一個(gè)元素，有效地將容器大小減少一個(gè)。這將破壞被刪除的元素。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,2,3,4,5 };cout << "原鏈表：";print(l1);l1.push_back(0);cout << "尾插：";print(l1);l1.push_front(0);cout << "頭插：";print(l1);l1.pop_back();cout << "尾刪：";print(l1);l1.pop_front();cout << "頭刪：";print(l1);return 0;
}

insert和erase

insert用于指定位置插入元素（需要使用迭代器指定）。該函數(shù)支持單個(gè)元素插入、n個(gè)val值插入、迭代器區(qū)間插入以及初始化器插入。操作結(jié)束后，該函數(shù)會(huì)返回新插入部分首元素的迭代器。

erase的作用是刪除指定位置的元素或區(qū)間（需要使用迭代器指定）。操作結(jié)束后，函數(shù)返回刪除部分的后一個(gè)位置的迭代器（防止迭代器失效）。?

代碼舉例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,4,5 };l.insert(++l.begin(), 0);//在第二個(gè)位置插入一個(gè)元素print(l);l.erase(----l.end());//刪除倒數(shù)第二個(gè)元素print(l);return 0;
}

swap

swap的功能是交換兩個(gè)list容器的內(nèi)容。?當(dāng)然，也有一個(gè)非成員函數(shù)的swap支持list的交換：

resize

resize的功能是調(diào)整容器的大小，使其包含n個(gè)元素。

如果n小于當(dāng)前容器的大小，則內(nèi)容將被減少到前n個(gè)元素，并刪除超出的元素（銷(xiāo)毀它們）

如果n大于當(dāng)前容器的大小，則通過(guò)在末尾插入所需的元素來(lái)擴(kuò)展內(nèi)容，以達(dá)到n的大小。如果指定了val，則將新元素初始化為val的副本，否則調(diào)用其構(gòu)造函數(shù)來(lái)初始化元素。

注意：這個(gè)函數(shù)通過(guò)插入或刪除元素來(lái)改變?nèi)萜鞯膶?shí)際內(nèi)容。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2;l1.resize(10);l2.resize(10, 5);print(l1);print(l2);list<int> l3({ 1,2,3,4,5 });print(l3);l3.resize(3);print(l3);return 0;
}

clear

clear的功能是從列表容器中刪除所有元素，并將容器的大小保留為0。

find

與vector相同，list并沒(méi)有用于查找的函數(shù)（find），要使用STL實(shí)現(xiàn)的通用find完成查找。該find函數(shù)定義在算法庫(kù)<algorithm>當(dāng)中，用于容器元素的查找。它接受兩個(gè)迭代器參數(shù)和一個(gè)值參數(shù)，表示需要查找的區(qū)間和值。如果找到了，函數(shù)會(huì)返回指向第一個(gè)查找到的元素的迭代器，否則返回尾迭代器。

六、list的其他操作接口

除了傳統(tǒng)的成員函數(shù)外，list還提供了一些特有的與插入刪除相關(guān)的操作接口供我們使用。通過(guò)學(xué)習(xí)這些接口的使用方法，我們可以初步了解仿函數(shù)的相關(guān)知識(shí)。

splice

splice的功能是剪切。它能夠?qū)?容器x?/?容器x的某個(gè)元素?/?容器的一部分 拷貝到原容器的指定位置，并且刪除x中的相應(yīng)元素。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });l1.splice(l1.end(), l2);//將l2剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;l2 = { 1,2,3,4,5 };l1.splice(l1.end(), l2, l2.begin());//將l2的首元素剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;l2 = { 1,2,3,4,5 };l1.splice(l1.end(), l2, ++l2.begin(), --l2.end());//將l2掐頭去尾的部分剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;
}

remove

remove的功能是刪除指定值的元素。

該函數(shù)從容器中刪除比較結(jié)果為val的所有元素。這將調(diào)用這些對(duì)象的析構(gòu)函數(shù)，并按刪除元素的數(shù)量減少容器大小。

與erase不同，erase根據(jù)元素的位置刪除元素，該函數(shù)根據(jù)元素的值刪除元素。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,2,4,2,2,5 };print(l);l.remove(2);//刪除所有的2print(l);return 0;
}

?

remove_if

remove_if用于刪除list容器中滿足特定條件的所有元素（特定條件由我們?cè)O(shè)定）。

該函數(shù)的參數(shù)是一個(gè)謂詞（Predicate），如果容器中的某元素使得該謂詞返回true，就將該元素刪除。

---

這里簡(jiǎn)單介紹一下謂詞：

? ? ? ? 之前我們?cè)赾語(yǔ)言部分使用qsort函數(shù)時(shí)，需要顯示寫(xiě)一個(gè)比較函數(shù)用于確定排序的規(guī)則，謂詞的功能就相當(dāng)于我們顯示寫(xiě)的比較函數(shù)。

? ? ? ? 謂詞可以是以下幾種形式之一：

????????1. 返回值為bool類型的函數(shù)指針

? ? ? ? 2. 仿函數(shù)（重載了函數(shù)調(diào)用操作符"()"的類，且該重載函數(shù)的返回值是bool類型）

? ? ? ? 3. Lambda表達(dá)式（c++11之后支持）

--------------------

????????由于我們已經(jīng)使用過(guò)函數(shù)指針，在接下來(lái)的代碼示例當(dāng)中，我們就嘗試寫(xiě)一個(gè)仿函數(shù)來(lái)表示謂詞。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}//仿函數(shù)
class f
{
public:bool operator()(int value){return value < 10;//將小于10的元素確定為true}
};int main()
{list<int> l = { 20,1,5,9,15,17 };l.remove_if(f());//刪除所有小于10的元素print(l);return 0;
}

?

unique

unique函數(shù)的功能是刪除所有與它的前一個(gè)元素滿足某特定關(guān)系（特定關(guān)系可由我們?cè)O(shè)定）的元素。當(dāng)然，該特定關(guān)系也是使用謂詞表示。當(dāng)我們沒(méi)有顯示設(shè)置特定關(guān)系，那么該特定關(guān)系就是兩元素相等，也就是說(shuō)我們沒(méi)有傳參時(shí)，函數(shù)的功能是刪除所有相鄰的重復(fù)元素（保留一個(gè)重復(fù)的元素，不會(huì)全部刪除）。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,1,2,3,3,4,4,4,5,5,6,7,8,8 };//有序序列l(wèi)1.unique();print(l1);list<int> l2 = { 2,2,1,2,2 };//無(wú)序序列，無(wú)法直接刪除所有重復(fù)元素l2.unique();print(l2);return 0;
}

對(duì)于一個(gè)無(wú)序list序列，如果想要?jiǎng)h除所有的重復(fù)元素，那么就需要先對(duì)list進(jìn)行排序，然后再調(diào)用unique函數(shù)。

merge

merge的作用是合并兩個(gè)有序鏈表，注意兩個(gè)容器都應(yīng)是有序狀態(tài)。

這實(shí)際上刪除了x中的所有元素，但不是銷(xiāo)毀其中元素，而是將節(jié)點(diǎn)的指針互相連接，最后全部并入到原容器中。

該函數(shù)可以接受一個(gè)特定的謂詞（comp）來(lái)執(zhí)行元素之間的比較操作。

函數(shù)執(zhí)行后，等價(jià)元素的相對(duì)位置不變（即原容器的在前，x的在后）。

如果x就是原容器，那么函數(shù)什么也不做。

代碼示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,3,5,7,9 };list<int> l2 = { 2,4,6,8,10 };l1.merge(l2);//合并cout << "l1:";print(l1);cout << "l2:";print(l2);return 0;
}

sort

sort用于排序list容器。當(dāng)然，我們也可以傳入一個(gè)謂詞來(lái)確定排序規(guī)則，否則默認(rèn)升序。

它的底層是一個(gè)優(yōu)化的歸并排序，意味著等價(jià)元素相對(duì)位置不變。

說(shuō)起sort，博主在這里補(bǔ)充一點(diǎn)：與通用find函數(shù)相同，STL實(shí)現(xiàn)了一個(gè)通用的排序函數(shù)sort，參數(shù)是隨機(jī)迭代器構(gòu)成的迭代器區(qū)間，用于容器排序。

為什么要實(shí)現(xiàn)一個(gè)成員函數(shù)版的sort呢？直接使用算法庫(kù)中的通用sort不行嗎？剛才博主已經(jīng)提到，list支持的是雙向迭代器，并不具備隨機(jī)迭代器的功能，所以list無(wú)法使用通用的sort函數(shù)完成排序，會(huì)發(fā)生報(bào)錯(cuò)。所以說(shuō)list的成員函數(shù)當(dāng)中，實(shí)現(xiàn)了一個(gè)排序函數(shù)sort。

接下來(lái)我們嘗試使用該函數(shù)：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 5,1,7,2,4,8,0,3 };l.sort();//排序print(l);return 0;
}

由于list底層是一個(gè)鏈表，所以對(duì)于排序這種需要重復(fù)調(diào)整元素順序的算法，它的效率不是很高。如果要對(duì)list排序，建議將list的內(nèi)容拷貝給vector，然后進(jìn)行排序，最后拷貝回list。

reverse

reverse的功能是反轉(zhuǎn)鏈表。

代碼示例：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,4,5 };l.reverse();//反轉(zhuǎn)print(l);return 0;
}

總結(jié)

? ? ? ? 今天我們學(xué)習(xí)了STL容器--list的使用方法。當(dāng)我們需要頻繁進(jìn)行插入和刪除操作時(shí)，可以考慮使用該容器。之后博主會(huì)和大家一起模擬實(shí)現(xiàn)list，并且借此來(lái)深入學(xué)習(xí)迭代器的底層實(shí)現(xiàn)。如果你覺(jué)得博主講的還不錯(cuò)，就請(qǐng)留下一個(gè)小小的贊在走哦，感謝大家的支持???