文章首發(fā)公眾號：iDoitnow如果喜歡話，可以關注一下

1. 鏈表和std::list

鏈表是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實現(xiàn)，其由若干節(jié)點所組成。std::list是C++中支持常數(shù)時間從容器任何位置插入和移除元素的容器，但其不支持快速的隨機訪問，其通常實現(xiàn)為雙向鏈表。

由于鏈表的存儲方式并不是連續(xù)的內存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器。在std::list中添加、移動和移除元素不會使迭代器或引用失效，迭代器只有在對應元素被刪除時才會失效。

2. list的用法

2.1 list的定義和聲明

std::list在頭文件<list>中定義，其聲明如下：

emplate<
????class?T,
????class?Allocator?=?std::allocator<T>
>?class?list;

namespace?pmr?{
????template<?class?T?>
????using?list?=?std::list<T,?std::pmr::polymorphic_allocator<T>>;?//C++17?起
}


其中，參數(shù)T為容器要存儲的元素類型，對于T需要滿足：

• 可復制賦值和可復制構造（C++11前）。

• 要求元素類型是完整類型并滿足可擦除，即元素類型的對象能以給定的分配器（Allocator）銷毀（C++11 起，C++17 前）。

• 要求元素類型是完整類型并滿足可擦除，但許多成員函數(shù)附帶了更嚴格的要求。（C++17 起）。

Allocator為用于獲取/釋放內存及構造/析構內存中元素的分配器。

2.2 成員函數(shù)

2.2.1 基本函數(shù)

構造函數(shù)

功能描述

• 創(chuàng)建list容器。

函數(shù)原型

//1.默認構造函數(shù)。構造擁有默認構造的分配器的空容器。
list();

//2.構造擁有給定分配器?alloc?的空容器。
explicit?list(?const?Allocator&?alloc?);

//3.構造擁有?count?個有值?value?的元素的容器。
explicit?list(?size_type?count,
???????????????const?T&?value?=?T(),
???????????????const?Allocator&?alloc?=?Allocator());?//C++11?前
list(?size_type?count,
???????????????const?T&?value,
???????????????const?Allocator&?alloc?=?Allocator());?//C++11?起

//4.構造擁有?count?個?默認插入的?T?實例的容器。不進行復制。
explicit?list(?size_type?count?);?//C++11?起,?C++14?前
explicit?list(?size_type?count,?const?Allocator&?alloc?=?Allocator()?);?//C++14?起

//5.構造擁有范圍?[first,?last)?內容的容器。
template<?class?InputIt?>
list(?InputIt?first,?InputIt?last,
??????const?Allocator&?alloc?=?Allocator()?);

//6.復制構造函數(shù)。構造擁有?other?內容的容器。
list(?const?list&?other?);

//7.構造擁有?other?內容的容器，以?alloc?為分配器。
list(?const?list&?other,?const?Allocator&?alloc?);?//C++11?起

//8.移動構造函數(shù)。用移動語義構造擁有?other?內容的容器。分配器通過屬于?other?的分配器移動構造獲得。
list(?list&&?other?);?//C++11?起

//9.有分配器擴展的移動構造函數(shù)。以?alloc?為新容器的分配器，從?other?移動內容。
list(?list&&?other,?const?Allocator&?alloc?);?//C++11?起

//10.構造擁有?initializer_list?init?內容的容器。
list(?std::initializer_list<T>?init,
??????const?Allocator&?alloc?=?Allocator()?);?//C++11?起


示例

//?C++11?初始化器列表語法：
std::list<std::string>?words1?{"the",?"frogurt",?"is",?"also",?"cursed"};
//words1?=?{"the",?"frogurt",?"is",?"also",?"cursed"}

//?words2?==?words1
std::list<std::string>?words2(words1.begin(),?words1.end());
//words2?=?{"the",?"frogurt",?"is",?"also",?"cursed"}

//?words3?==?words1
std::list<std::string>?words3(words1);
//words3?=?{"the",?"frogurt",?"is",?"also",?"cursed"}

//?words4?是?{"Mo",?"Mo",?"Mo",?"Mo",?"Mo"}
std::list<std::string>?words4(5,?"Mo");
//words4?=?{Mo,?Mo,?Mo,?Mo,?Mo}


operator=

功能描述

• 用于賦值給容器。

函數(shù)原型

//復制賦值運算符。以?other?的副本替換內容。
list&?operator=(?const?list&?other?);

//移動賦值運算符。用移動語義以?other?的內容替換內容（即從?other?移動?other?中的數(shù)據(jù)到此容器中）。之后other在合法但未指定的狀態(tài)。
list&?operator=(?list&&?other?);?//C++11?起,?C++17?前
list&?operator=(?list&&?other?)?noexcept();?//C++17?起

//以?initializer_list?ilist?所標識者替換內容。
list&?operator=(?std::initializer_list<T>?ilist?);?//C++11?起


示例

std::list<int>?nums1?{3,?1,?4,?6,?5,?9};
std::list<int>?nums2;
std::list<int>?nums3;

//?從?nums1?復制賦值數(shù)據(jù)到?nums2
nums2?=?nums1;
//此時nums2?=?{3,?1,?4,?6,?5,?9}

//?從?nums1?移動賦值數(shù)據(jù)到?nums3,
//?修改?nums1?和?nums3
nums3?=?std::move(nums1);
//此時?nums1?=?{},?nums3?=?{3,?1,?4,?6,?5,?9}


//?initializer_list?的復制賦值復制數(shù)據(jù)給?nums3
nums3?=?{1,?2,?3};
//此時nums3?=?{1,?2,?3}


assign

功能描述

• 將值賦給容器，替換容器的內容。

函數(shù)原型

//以?count?份?value?的副本替換內容。
void?assign(?size_type?count,?const?T&?value?);

//以范圍?[first,?last)?中元素的副本替換內容。其中有任何一個迭代器是指向?*this?中的迭代器時行為未定義。
template<?class?InputIt?>
void?assign(?InputIt?first,?InputIt?last?);

//以來自?initializer_list?ilist?的元素替換內容。
void?assign(?std::initializer_list<T>?ilist?);?//C++11?起


示例

std::list<char>?c;

c.assign(5,?'a');//此時c?=?{'a',?'a',?'a',?'a',?'a'}

const?std::string?str(6,?'b');
c.assign(str.begin(),?str.end());//此時c?=?{'b',?'b',?'b',?'b',?'b',?'b'}

c.assign({'C',?'+',?'+',?'1',?'1'});//此時c?=?{'C',?'+',?'+',?'1',?'1'}


get_allocator

功能描述

• 返回相關的分配器。

函數(shù)原型

//返回值：與容器關聯(lián)的分配器。
allocator_type?get_allocator()?const;?//C++11?前
allocator_type?get_allocator()?const?noexcept;?//C++11?起


2.2.2 元素訪問

front

功能描述

• 訪問容器的第一個元素，其返回值為容器首元素的引用。

函數(shù)原型

reference?front();
const_reference?front()?const;


注：在空容器上對 front 的調用是未定義的。

back

功能描述

• 訪問容器最后一個元素，其返回值為容器最后一個元素的引用。

函數(shù)原型

reference?back();
const_reference?back()?const;


注：在空容器上對 back 的調用是未定義的。

2.2.3 迭代器

begin、end和cbegin、cend

功能描述

• begin和cbegin返回指向list首元素的迭代器，

• end和cend返回指向list末元素后一元素的迭代器。

函數(shù)原型

iterator?begin();?//C++11?前
iterator?begin()?noexcept;?//C++11?起
const_iterator?begin()?const;?//C++11?前
const_iterator?begin()?const?noexcept;?//C++11?起
const_iterator?cbegin()?const?noexcept;?//C++11?起

iterator?end();?//C++11?前
iterator?end()?noexcept;?//C++11?起
const_iterator?end()?const;?//C++11?前
const_iterator?end()?const?noexcept;?//C++11?起
const_iterator?cend()?const?noexcept;?//C++11?起


如果list為空，則返回的迭代器將等于end或cend。end和cend指向list末元素后一元素的迭代器，該元素的表現(xiàn)為占位符，試圖訪問它將導致未定義行為。

rbegin、rend和crbegin、crend

功能描述

• rbegin和crbegin返回指向list首元素的逆向迭代器。它對應非逆向list的末元素，若list為空，則返回的迭代器等于rend或crend。

• rend和crend返回指向逆向list末元素后一元素的逆向迭代器，它對應非逆向list首元素的前一元素，此元素表現(xiàn)為占位符，試圖訪問它導致未定義行為。

函數(shù)原型

reverse_iterator?rbegin();?//C++11?前
reverse_iterator?rbegin()?noexcept;?//C++11?起
const_reverse_iterator?rbegin()?const;?//C++11?前
const_reverse_iterator?rbegin()?const?noexcept;?//C++11?起
const_reverse_iterator?crbegin()?const?noexcept;?//C++11?起

reverse_iterator?rend();?//C++11?前
reverse_iterator?rend()?noexcept;?//C++11?起
const_reverse_iterator?rend()?const;?//C++11?前
const_reverse_iterator?rend()?const?noexcept;?//C++11?起
const_reverse_iterator?crend()?const?noexcept;?//C++11?起


2.2.4 容量

empty

功能描述

• 檢查容器是否為空，若為空則返回true，否則為false。

函數(shù)原型

bool?empty()?const;?//C++11?前
bool?empty()?const?noexcept;?//C++11?起，C++20?前
[[nodiscard]]?bool?empty()?const?noexcept;?//C++20?起


其底層實現(xiàn)就是檢查容器是否無元素，即判斷是否begin() == end()。

size

功能描述

• 返回容器中元素數(shù)量，即std::distance(begin(), end()) 。

函數(shù)原型

size_type?size()?const;?//C++11?前
size_type?size()?const?noexcept;?//C++11?起


max_size

功能描述

• max_size函數(shù)返回根據(jù)系統(tǒng)或庫實現(xiàn)限制的容器可保有的元素最大數(shù)量，即對于最大容器的 std::distance(begin(), end())。

函數(shù)原型

size_type?max_size()?const;?//C++11?前
size_type?max_size()?const?noexcept;?//C++11?起


注：此值通常反映容器大小上的理論極限，至多為 std::numeric_limits<difference_type>::max() 。運行時，可用 RAM 總量可能會限制容器大小到小于 max_size() 的值。

2.2.5 修改器

clear

功能描述

• 擦除所有元素，使用clear()后，再次調用size()，size函數(shù)返回0。

函數(shù)原型

void?clear();?//C++11?前
void?clear()?noexcept;?//C++11?起


insert

功能描述

• 插入元素到容器的指定位置。

函數(shù)原型

//在?pos?前插入?value。
//返回值：指向被插入?value?的迭代器。
iterator?insert(?const_iterator?pos,?const?T&?value?);
iterator?insert(?const_iterator?pos,?T&&?value?);?//C++11?起

//在?pos?前插入?value?的?count?個副本。
//返回值：指向首個被插入元素的迭代器，或者在?count?==?0?時返回?pos。
iterator?insert(?const_iterator?pos,?size_type?count,?const?T&?value?);

//在?pos?前插入來自范圍?[first,?last)?的元素。
//返回值：指向首個被插入元素的迭代器，或者在?first?==?last?時返回?pos。
template<?class?InputIt?>
iterator?insert(?const_iterator?pos,?InputIt?first,?InputIt?last?);

//在?pos?前插入來自?initializer_list?ilist?的元素。
//返回值：指向首個被插入元素的迭代器，或者在?ilist?為空時返回?pos。
iterator?insert(?const_iterator?pos,?std::initializer_list<T>?ilist?);?//C++11?起


示例

std::list<int>?c1(3,?100);?//初始化c1，此時c1?=?{100,?100,?100}

auto?it?=?c1.begin();
it?=?c1.insert(it,?200);?//在it前插入元素200
//c1?=?{200，100,?100,?100}

c1.insert(it,?2,?300);?//在it前插入兩個元素值都為300
//c1?=?{300，300，200，100,?100,?100}

//?將?it?重新指向開頭
it?=?c1.begin();

std::list<int>?c2(2,?400);?//c2?=?{400,?400}
c1.insert(std::next(it,?2),?c2.begin(),?c2.end());?//在it后兩個元素（即200）的前面插入c2
//c1?=?{300，300，400，400，200，100,?100,?100}

int?arr[]?=?{501,?502,?503};
c1.insert(c1.begin(),?arr,?arr?+?std::size(arr));
//c1?=?{501，502，503，300，300，400，400，200，100,?100,?100}

c1.insert(c1.end(),?{601,?602,?603});
//c1?=?{501，502，503，300，300，400，400，200，100,?100,?100，601，602，603}


emplace

功能描述

• 原位構造元素并將其在pos前插入到容器中。

函數(shù)原型

/*----------------------------------
??pos：將構造新元素到其前的迭代器
??args：轉發(fā)給元素構造函數(shù)的參數(shù)
??返回值iterator：指向被安置的元素的迭代器
------------------------------------*/
template<?class...?Args?>
iterator?emplace(?const_iterator?pos,?Args&&...?args?);?//C++11?起


注：通過 std::allocator_traits::construct構造元素，用布置 new 在容器提供的位置原位構造元素。

將參數(shù) args... 作為 std::forward<Args>(args)... 轉發(fā)給構造函數(shù)。 args... 可以直接或間接地指代容器中的值。

earse

功能描述

• 擦除元素，

函數(shù)原型

//移除位于pos的元素
//返回值：最后移除元素之后的迭代器。如果pos指代末元素，則返回end()迭代器
iterator?erase(?iterator?pos?);?//C++11?前
iterator?erase(?const_iterator?pos?);?//C++11?起

//移除范圍[first,?last)中的元素。
/*返回值：最后移除元素之后的迭代器。
?????????如果在移除前l(fā)ast?==?end()，那么最終返回end()迭代器
?????????如果范圍[first,?last)?為空，那么返回?last。*/
iterator?erase(?iterator?first,?iterator?last?);?//C++11?前
iterator?erase(?const_iterator?first,?const_iterator?last?);?//C++11?起


注：指向被擦除元素的迭代器和引用會失效。其他引用和迭代器不受影響。

示例

std::list<int>?c{0,?1,?2,?3,?4,?5,?6,?7,?8,?9};

c.erase(c.begin());
//?c?=?{1,?2,?3,?4,?5,?6,?7,?8,?9}

std::list<int>::iterator?range_begin?=?c.begin();
std::list<int>::iterator?range_end?=?c.begin();
std::advance(range_begin,?2);
std::advance(range_end,?5);

c.erase(range_begin,?range_end);
//?c?=?{1,?2,?6,?7,?8,?9}

//?移除所有偶數(shù)
for?(std::list<int>::iterator?it?=?c.begin();?it?!=?c.end();)
{
??if?(*it?%?2?==?0)
????it?=?c.erase(it);
??else
????++it;
}
//?c?=?{1,?7,?9}


push_back

功能描述

將元素添加到容器末尾。

函數(shù)原型

//后附給定元素?value?到容器尾。初始化新元素為?value?的副本。
void?push_back(?const?T&?value?);

//后附給定元素?value?到容器尾。移動?value?進新元素。
void?push_back(?T&&?value?);?//C++11?起


emplace_back

功能描述

emplace_back函數(shù)與emplace類似，只不過是在容器末尾就地構造元素。

函數(shù)原型

template<?class...?Args?>
void?emplace_back(?Args&&...?args?);?//C++11?起，C++17?前

template<?class...?Args?>
reference?emplace_back(?Args&&...?args?);?//C++17?起


由于emplace_back是原地構造元素，因此其插入效率要高于push_back。

pop_back

功能描述

移除末元素。

函數(shù)原型

void?pop_back();?


如果在空容器上調用pop_back會導致未定義行為。

注：指向被擦除元素的迭代器和引用會失效。

push_front

功能描述

插入元素到容器起始。

函數(shù)原型

void?push_front(?const?T&?value?);
void?push_front(?T&&?value?);?//C++11?起


emplace_front

功能描述

在容器頭部原位構造元素，與push_front功能相同，主要區(qū)別是其它典型地用布置 new 在容器所提供的位置原位構造元素。將參數(shù) args... 作為 std::forward<Args>(args)... 轉發(fā)給構造函數(shù)。

函數(shù)原型

template<?class...?Args?>
void?emplace_front(?Args&&...?args?);?//C++11?起,?C++17?前

template<?class...?Args?>
reference?emplace_front(?Args&&...?args?);?//C++17?起


pop_front

功能描述

移除容器首元素。若容器中無元素，則行為未定義。指向被擦除元素的迭代器和引用會失效。

函數(shù)原型

void?pop_front();


resize

功能描述

改變容器中可存儲元素的個數(shù)，通過該函數(shù)可以重新設置容器大小。

函數(shù)原型

/*
該函數(shù)重設容器的大小為count，在count==size()時不做任何操作。
如果當前大小大于?count，那么減小容器到它的開頭?count?個元素。
如果當前大小小于?count，那么后附額外的默認插入的元素。
*/
void?resize(?size_type?count?);

/*
該函數(shù)重設容器的大小為count，在count==size()時不做任何操作。
如果當前大小大于?count，那么減小容器到它的開頭?count?個元素。
如果當前大小小于?count，那么后附額外的?value?的副本
*/
void?resize(?size_type?count,?const?value_type&?value?);


示例

std::list<int>?c?=?{1,?2,?3};

c.resize(5);?//將其size增加大小到5
//c?=?{1,?2,?3,?0,?0}

c.resize(2);?//將其size減少大小到2
//c?=?{1,?2}

c.resize(6,?4);?//將其size增加大小到6，填充值為4";
//c?=?{1,?2,?4,?4,?4，4}


swap

功能描述

交換兩個list容器的內容，不在單獨的元素上調用任何移動、復制或交換操作。所有迭代器和引用保持有效。在操作后，未指明保有此容器中 end()值的迭代器指代此容器還是另一容器。

函數(shù)原型

void?swap(?list&?other?);?//C++17?前
void?swap(?list&?other?)?noexcept();?//C++17?起


示例

std::list<int>?a1{1,?2,?3},?a2{4,?5};

auto?it1?=?std::next(a1.begin());?//*it1?=?2?
auto?it2?=?std::next(a2.begin());?//*it2?=?5?

int&?ref1?=?a1.front();?//ref1?=?1
int&?ref2?=?a2.front();?//ref1?=?4

std::cout?<<*it1?<<?'?'?<<?*it2?<<?'?'?<<?ref1?<<?'?'?<<?ref2?<<?'\n';
//打印結果為2?5?1?4

a1.swap(a2);

//此時a1?=?{4,?5}，a2?=?{1,?2,?3}
std::cout?<<*it1?<<?'?'?<<?*it2?<<?'?'?<<?ref1?<<?'?'?<<?ref2?<<?'\n';
//打印結果仍為2?5?1?4

/*注：
????交換后迭代器與引用保持與原來的元素關聯(lián)，
????例如盡管?'a1'?中值為?2?的元素被移動到?'a2'?中，
????原來指向它的?it1?仍指向同一元素。*/


2.2.6 操作

merge

功能描述

合并二個已排序列表。

函數(shù)原型

//用?operator<?比較元素
void?merge(?list&?other?);
void?merge(?list&&?other?);?//C++11?起

//用給定的比較函數(shù)?comp?比較元素。
template?<?class?Compare?>
void?merge(?list&?other,?Compare?comp?);
template?<?class?Compare?>
void?merge(?list&&?other,?Compare?comp?);?//C++11?起


如果 other 與*this指代同一對象，那么什么也不做。否則將兩個已經(jīng)排序列表歸并為一個。鏈表應以升序排序。不復制元素，并且在操作后容器other會變空。不會無效化任何引用或者迭代器，但被移動元素的迭代器現(xiàn)在指代到*this中，而不是到other中。

注：對于兩個鏈表中的等價元素，來自 *this 的元素始終在來自 other 的元素之前，并且 *this 和 other 的等價元素順序不更改。如果 get_allocator() != other.get_allocator()，那么行為未定義。

示例

std::list<int>?list1?=?{5,?9,?1,?3,?3};
std::list<int>?list2?=?{8,?7,?2,?3,?4,?4};

list1.sort();?//?1?3?3?5?9
list2.sort();?//?2?3?4?4?7?8

list1.merge(list2);?//1?2?3?3?3?4?4?5?7?8?9


splice

功能描述

從一個 list 轉移元素給另一個。

函數(shù)原型

/*《參數(shù)說明》
pos?????????-?將插入內容到它之前的元素
other???????-?要從它轉移內容的另一容器
it?????????-?要從?other?轉移到?*this?的元素
first,?last?-?要從?other?轉移到?*this?的元素范圍
*/


/*從?other?轉移所有元素到?*this?中。元素被插入到?pos?指向的元素之前。
操作后容器?other?變?yōu)榭铡ther?與?*this?指代同一對象時行為未定義。*/
void?splice(?const_iterator?pos,?list&?other?);
void?splice(?const_iterator?pos,?list&&?other?);?//C++11?起

/*從?other?轉移?it?指向的元素到?*this。元素被插入到?pos?指向的元素之前。*/
void?splice(?const_iterator?pos,?list&?other,?const_iterator?it?);
void?splice(?const_iterator?pos,?list&&?other,?const_iterator?it?);?//C++11?起

/*從?other?轉移范圍?[first,?last)?中的元素到?*this。
元素被插入到?pos?指向的元素之前。pos?是范圍?[first,last)?中的迭代器時行為未定義。*/
void?splice(?const_iterator?pos,?list&?other,
?????????????const_iterator?first,?const_iterator?last);
void?splice(?const_iterator?pos,?list&&?other,
?????????????const_iterator?first,?const_iterator?last?);?//C++11?起


不復制或移動元素，僅重指向鏈表結點的內部指針。get_allocator() != other.get_allocator() 時行為未定義。沒有迭代器或引用會失效，指向被移動元素的迭代器保持有效，但現(xiàn)在指代到 *this 中，而非到 other 中。

示例

std::list<int>?list1?=?{1,?2,?3,?4,?5};
std::list<int>?list2?=?{10,?20,?30,?40,?50};

auto?it?=?list1.begin();

list1.splice(it,?list2);
//list1?=?{10,?20,?30,?40,?50,?1,?2,?3,?4,?5};
//list2?=?{};

list2.splice(list2.begin(),?list1,?it,?list1.end());
//list1?=?{10,?20,?30,?40,?50};
//list2?=?{1,?2,?3,?4,?5};


remove、remove_if

功能描述

移除滿足特定標準的元素。

函數(shù)原型

//移除所有等于?value?的元素
void?remove(?const?T&?value?);?//C++20?前
size_type?remove(?const?T&?value?);?//C++20?起

//移除所有謂詞?p?對它返回?true?的元素
template<?class?UnaryPredicate?>
void?remove_if(?UnaryPredicate?p?);?//C++20?前
template<?class?UnaryPredicate?>
size_type?remove_if(?UnaryPredicate?p?);?//C++20?起


示例

std::list<int>?l?=?{?1,100,2,3,10,1,11,-1,12?};

l.remove(1);?//?移除兩個等于?1?的元素
l.remove_if([](int?n){?return?n?>?10;?});?//?移除全部大于?10?的元素

for?(int?n?:?l)?{
??std::cout?<<?n?<<?'?';?
}
std::cout?<<?'\n';

//輸出結果：2?3?10?-1


reverse

功能描述

將該鏈表的所有元素的順序反轉。逆轉容器中的元素順序。不非法化任何引用或迭代器。

函數(shù)原型

void?reverse();?//C++11?前)
void?reverse()?noexcept;?//C++11?起


示例

std::list<int>?list?=?{?8,7,5,9,0,1,3,2,6,4?};
list.reverse();?//4?6?2?3?1?0?9?5?7?8


unique

功能描述

刪除連續(xù)的重復元素。從容器移除所有相繼的重復元素。只留下相等元素組中的第一個元素。若選擇的比較器不建立等價關系則行為未定義。

函數(shù)原型

//用?operator==?比較元素。
void?unique();?//C++20?前
size_type?unique();?//C++20?起

//用二元謂詞?p?比較元素。
template<?class?BinaryPredicate?>
void?unique(?BinaryPredicate?p?);?//C++20?前
template<?class?BinaryPredicate?>
size_type?unique(?BinaryPredicate?p?);?//C++20?起


示例

std::list<int>?c?=?{1,?2,?2,?3,?3,?2,?1,?1,?2};
c.unique();//?1?2?3?2?1?2

c?=?{1,?2,?12,?23,?3,?2,?51,?1,?2};
c.unique([mod=10](int?x,?int?y)?{?return?(x?%?mod)?==?(y?%?mod);?});
//1?2?23?2?51?2


sort

功能描述

對元素進行排序。以升序排序元素。保持相等元素的順序。

函數(shù)原型

//用?operator<?比較元素
void?sort();
?
//用給定的比較函數(shù)?comp,?在第一參數(shù)小于（即先序于）第二參數(shù)時返回?true。
template<?class?Compare?>
void?sort(?Compare?comp?);


示例

std::list<int>?list?=?{?8,7,5,9,0,1,3,2,6,4?};

list.sort();//0?1?2?3?4?5?6?7?8?9
list.sort(std::greater<int>());//9?8?7?6?5?4?3?2?1?0

list?=?{1,?2,?14,?25,?3,?22};
//按照元素個位數(shù)的大小進行排序
list.sort([mod?=?10](int?x,?int?y)
?????????{?return?(x?%?mod)?<?(y?%?mod);?});//1?2?22?3?14?25


2.3 非成員函數(shù)

operator==,!=,<,<=,>,>=,<=>(std::list)

功能描述

按照字典順序比較 list 中的值。

函數(shù)聲明

//1.?==
//返回值：在?list?內容相等時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator==(?const?std::list<T,?Alloc>&?lhs,
?????????????????const?std::list<T,?Alloc>&?rhs?);

//2.?!=
//返回值：在?list?內容不相等時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator!=(?const?std::list<T,?Alloc>&?lhs,
?????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?前

//3.?<
//返回值：在?lhs?的內容按字典序小于?rhs?的內容時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator<(?const?std::list<T,?Alloc>&?lhs,
????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?前

//4.?<=
//返回值：在?lhs?的內容按字典序小于或等于?rhs?的內容時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator<=(?const?std::list<T,?Alloc>&?lhs,
?????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?前

//5.?>
//返回值：在?lhs?的內容按字典序大于?rhs?的內容時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator>(?const?std::list<T,?Alloc>&?lhs,
????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?前

//6.?>=
//返回值：在?lhs?的內容按字典序大于或等于?rhs?的內容時返回?true，否則返回?false
template<?class?T,?class?Alloc?>
bool?operator>=(?const?std::list<T,?Alloc>&?lhs,
?????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?前

//7.?<=>
//返回值：lhs?與?rhs?中的首對不等價元素的相對順序，如果有這種元素；否則是?lhs.size()?<=>?rhs.size()。
template<?class?T,?class?Alloc?>
operator<=>(?const?std::list<T,?Alloc>&?lhs,
?????????????????????????????const?std::list<T,?Alloc>&?rhs?);?//C++20?起


• 1,2中會檢查 lhs 與 rhs 的內容是否相等，即它們是否擁有相同數(shù)量的元素且 lhs 中每個元素與 rhs 的同位置元素比較相等。

• 3-6中按照字典比較lhs和rhs的內容，其內部等價于調用std::lexicographical_compare函數(shù)進行比較。

• 7中也是按字典序比較lhs和rhs的內容。其內部等價于調用std::lexicographical_compare_three_way 進行比較。返回類型同合成三路比較的結果類型。其邏輯大致如下：

  lhs?<?rhs???std::weak_ordering::less?:
rhs?<?lhs???std::weak_ordering::greater?:
????????????std::weak_ordering::equivalent
//注：通常情況下less對應的是-1，greater對應1，equivalent對應0


  lhs與rhs中的首對不等價元素的相對順序，如果有這種元素；否則是 lhs.size() <=> rhs.size()。

示例

std::list<int>?alice{1,?2,?3};
std::list<int>?bob{7,?8,?9,?10};
std::list<int>?eve{1,?2,?3};

std::cout?<<?std::boolalpha;

//?比較不相等的容器
std::cout?<<?"alice?==?bob?returns?"?<<?(alice?==?bob)?<<?'\n';
std::cout?<<?"alice?!=?bob?returns?"?<<?(alice?!=?bob)?<<?'\n';
std::cout?<<?"alice?<??bob?returns?"?<<?(alice?<?bob)?<<?'\n';
std::cout?<<?"alice?<=?bob?returns?"?<<?(alice?<=?bob)?<<?'\n';
std::cout?<<?"alice?>??bob?returns?"?<<?(alice?>?bob)?<<?'\n';
std::cout?<<?"alice?>=?bob?returns?"?<<?(alice?>=?bob)?<<?'\n';

std::cout?<<?'\n';

//?比較相等的容器
std::cout?<<?"alice?==?eve?returns?"?<<?(alice?==?eve)?<<?'\n';
std::cout?<<?"alice?!=?eve?returns?"?<<?(alice?!=?eve)?<<?'\n';
std::cout?<<?"alice?<??eve?returns?"?<<?(alice?<?eve)?<<?'\n';
std::cout?<<?"alice?<=?eve?returns?"?<<?(alice?<=?eve)?<<?'\n';
std::cout?<<?"alice?>??eve?returns?"?<<?(alice?>?eve)?<<?'\n';
std::cout?<<?"alice?>=?eve?returns?"?<<?(alice?>=?eve)?<<?'\n';


輸出結果為

alice?==?bob?returns?false
alice?!=?bob?returns?true
alice?<??bob?returns?true
alice?<=?bob?returns?true
alice?>??bob?returns?false
alice?>=?bob?returns?false
?
alice?==?eve?returns?true
alice?!=?eve?returns?false
alice?<??eve?returns?false
alice?<=?eve?returns?true
alice?>??eve?returns?false
alice?>=?eve?returns?true


std::swap(std::list)

功能描述

std::list特化 std::swap算法。

函數(shù)原型

template<?class?T,?class?Alloc?>
void?swap(?std::list<T,?Alloc>&?lhs,
???????????std::list<T,?Alloc>&?rhs?);?//C++17?前
template<?class?T,?class?Alloc?>
void?swap(?std::list<T,?Alloc>&?lhs,
???????????std::list<T,?Alloc>&?rhs?)?noexcept();?//C++17?起


交換 lhs 與 rhs 的內容。調用lhs.swap(rhs)。

示例

std::list<int>?a1{1,?2,?3},?a2{4,?5};

auto?it1?=?std::next(a1.begin());?//*it1?=?2
auto?it2?=?std::next(a2.begin());?//*it2?=?5

int?&ref1?=?a1.front();?//?ref1?=?1
int?&ref2?=?a2.front();?//?ref1?=?4

std::cout?<<?*it1?<<?'?'?<<?*it2?<<?'?'?<<?ref1?<<?'?'?<<?ref2?<<?'\n';
//?打印結果為2?5?1?4

std::swap(a1,?a2);

//?此時a1?=?{4,?5}，a2?=?{1,?2,?3}
std::cout?<<?*it1?<<?'?'?<<?*it2?<<?'?'?<<?ref1?<<?'?'?<<?ref2?<<?'\n';
//?打印結果仍為2?5?1?4

/*注：
??????交換后迭代器與引用保持與原來的元素關聯(lián)，
??????例如盡管?'a1'?中值為?2?的元素被移動到?'a2'?中，
??????原來指向它的?it1?仍指向同一元素。*/


std::erase, std::erase_if (std::list)

功能描述

函數(shù)主要用來擦除所有滿足特定判別標準的元素。

函數(shù)原型

//從容器中擦除所有比較等于value的元素，
//等價于?return?c.remove_if([&](auto&?elem)?{?return?elem?==?value;?});
template<?class?T,?class?Alloc,?class?U?>
typename?std::list<T,?Alloc>::size_type
????erase(std::list<T,?Alloc>&?c,?const?U&?value);?//C++20?起

//從容器中擦除所有滿足pred的元素，pred為應該擦除元素則返回true的一元謂詞。
//等價于?return?c.remove_if(pred);
template<?class?T,?class?Alloc,?class?Pred?>
typename?std::list<T,?Alloc>::size_type
????erase_if(std::list<T,?Alloc>&?c,?Pred?pred);?//C++20?起


返回值為被擦除的元素數(shù)。

示例

std::list<int>?c{1,?2,?3,?4,?6};
//?擦除c中的值等于3的元素
auto?erased1?=?std::erase(c,?3);?//?erased1?=?1
//?此時c?=?{1,?2,?4,?6}

//?擦除c中的偶數(shù)
auto?erased2?=?std::erase_if(c,?[](int?n)
?????????????????????????????{?return?n?%?2?==?0;?});?//?erased2?=?3
//?此時c?=?{1}


3. 總結

list容器的優(yōu)勢和劣勢：

優(yōu)勢

• 采用動態(tài)內存分配，不會造成內存浪費和溢出。

• 執(zhí)行插入和刪除操作十分方便、高效。修改指針即可，不需要移動大量元素。

劣勢

• 空間（指針域）和時間（遍歷）額外耗費比較大。