單向鏈表和C++ std::forward_list詳解

2023-08-05 10:18 作者:艱默 0人讀過 | 我要投稿

1. 單向鏈表和std::forward_list

上一章我們介紹了雙向鏈表和C++容器庫中提供的std::list容器，與之對(duì)應(yīng)的就是單向鏈表，顧名思義，單向鏈表只記錄下一個(gè)元素的位置，只能朝一個(gè)方向遍歷元素。C++11從開始提供了std::forward_list（前向列表）來實(shí)現(xiàn)單向鏈表。std::forward_list在插入、刪除和移動(dòng)操作（例如排序）中比其他容器更有用，并且允許時(shí)間常數(shù)內(nèi)插入和刪除元素。

std::forward_list與std::list不同的是：std::forward_list僅跟蹤下一個(gè)元素的位置，而std::list同時(shí)跟蹤下一個(gè)和上一個(gè)元素，從而增加了存儲(chǔ)每個(gè)元素所需的存儲(chǔ)空間。std::forward_list的缺點(diǎn)是它不能向后迭代，也不能直接訪問其各個(gè)元素。

2. forward_list的用法

2.1 forward_list的定義和聲明

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

template<
? ?class T,
? ?class Allocator = std::allocator<T>
> class forward_list; //C++11 起

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

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

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

Allocator為用于獲取/釋放內(nèi)存及構(gòu)造/析構(gòu)內(nèi)存中元素的分配器。

2.2 成員函數(shù)

2.2.1 基本函數(shù)

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

功能描述

創(chuàng)建forward_list容器。

函數(shù)原型
//默認(rèn)構(gòu)造函數(shù)。構(gòu)造擁有默認(rèn)構(gòu)造的分配器的空容器。
forward_list();

//構(gòu)造擁有給定分配器 alloc 的空容器。
explicit forward_list( const Allocator& alloc );

//構(gòu)造擁有 count 個(gè)有值 value 的元素的容器。
forward_list( size_type count,
? ? ? ? ? ? ?const T& value,
? ? ? ? ? ? ?const Allocator& alloc = Allocator()); //C++11 起

//構(gòu)造擁有 count 個(gè) 默認(rèn)插入的 T 實(shí)例的容器。不進(jìn)行復(fù)制。
explicit forward_list( size_type count ); //C++11 起, C++14 前
explicit forward_list( size_type count, const Allocator& alloc = Allocator() ); //C++14 起

//構(gòu)造擁有范圍 [first, last) 內(nèi)容的容器。
template< class InputIt >
forward_list( InputIt first, InputIt last,
? ? ? ? ? ? ?const Allocator& alloc = Allocator() ); //C++11 起

//復(fù)制構(gòu)造函數(shù)。構(gòu)造擁有 other 內(nèi)容的容器。
forward_list( const forward_list& other ); //C++11 起

//構(gòu)造擁有 other 內(nèi)容的容器，以 alloc 為分配器。
forward_list( const forward_list& other, const Allocator& alloc ); //C++11 起

//移動(dòng)構(gòu)造函數(shù)。用移動(dòng)語義構(gòu)造擁有 other 內(nèi)容的容器。分配器通過屬于 other 的分配器移動(dòng)構(gòu)造獲得。
forward_list( forward_list&& other ); //C++11 起

//有分配器擴(kuò)展的移動(dòng)構(gòu)造函數(shù)。以 alloc 為新容器的分配器，從 other 移動(dòng)內(nèi)容；如果 alloc != other.get_allocator() ，那么它會(huì)導(dǎo)致逐元素移動(dòng)。
forward_list( forward_list&& other, const Allocator& alloc ); //C++11 起

//構(gòu)造擁有初始化器列表 init 內(nèi)容的容器。
forward_list( std::initializer_list<T> init,
? ? ? ? ? ? ?const Allocator& alloc = Allocator() ); //C++11 起

//構(gòu)造擁有范圍 rg 內(nèi)容的容器。
template< container-compatible-range<T> R >
forward_list( std::from_range_t, R&& rg,
? ? ? ? ? ? ?const Allocator& alloc = Allocator() ); //C++23 起
示例
// C++11 初始化器列表語法：
std::forward_list<std::string> words1 {"the", "frogurt", "is", "also", "cursed"};
std::cout << "words1: " << words1 << '\n';

// words2 == words1
std::forward_list<std::string> words2(words1.begin(), words1.end());
std::cout << "words2: " << words2 << '\n';

// words3 == words1
std::forward_list<std::string> words3(words1);
std::cout << "words3: " << words3 << '\n';

// words4 是 {"Mo", "Mo", "Mo", "Mo", "Mo"}
std::forward_list<std::string> words4(5, "Mo");
std::cout << "words4: " << words4 << '\n';

/**************打印結(jié)果******************
words1: [the, frogurt, is, also, cursed]
words2: [the, frogurt, is, also, cursed]
words3: [the, frogurt, is, also, cursed]
words4: [Mo, Mo, Mo, Mo, Mo]
***************************************/

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

功能描述

銷毀 forward_list 。調(diào)用元素的析構(gòu)函數(shù)，然后解分配所用的存儲(chǔ)。注意，若元素是指針，則不銷毀所指向的對(duì)象。

函數(shù)原型
~forward_list(); //C++11 起

operator=

功能描述

用于賦值給容器。

函數(shù)原型
//復(fù)制賦值運(yùn)算符。以 other 的副本替換內(nèi)容。
forward_list& operator=( const forward_list& other ); //C++11 起

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

//以 initializer_list ilist 所標(biāo)識(shí)者替換內(nèi)容。
forward_list& operator=( std::initializer_list<T> ilist ); //C++11 起
示例
std::forward_list<int> nums1 {3, 1, 4, 6, 5, 9};
std::forward_list<int> nums2;
std::forward_list<int> nums3;

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

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

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

assign

功能描述

將值賦給容器，替換容器的內(nèi)容。

函數(shù)原型
//以 count 份 value 的副本替換內(nèi)容。
void assign( size_type count, const T& value ); ////C++11 起

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

//以來自 initializer_list ilist 的元素替換內(nèi)容。
void assign( std::initializer_list<T> ilist ); //C++11 起
示例
std::forward_list<char> c;

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

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

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

get_allocator

功能描述

返回相關(guān)的分配器。

函數(shù)原型

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

2.2.2 元素訪問

front

功能描述

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

函數(shù)原型
reference front(); //C++11 起
const_reference front() const; //C++11 起
注：在空容器上對(duì) front 的調(diào)用是未定義的。

2.2.3 迭代器

begin、end和cbegin、cend

功能描述

begin和cbegin返回指向forward_list首元素的迭代器，
end和cend返回指向forward_list末元素后一元素的迭代器。

函數(shù)原型
iterator begin() noexcept; //C++11 起
const_iterator begin() const noexcept; //C++11 起
const_iterator cbegin() const noexcept; //C++11 起

iterator end() noexcept; //C++11 起
const_iterator end() const noexcept; //C++11 起
const_iterator cend() const noexcept; //C++11 起
如果forward_list為空，則返回的迭代器將等于end或cend。end和cend指向forward_list末元素后一元素的迭代器，該元素的表現(xiàn)為占位符，試圖訪問它將導(dǎo)致未定義行為。

before_begin, cbefore_begin

功能描述

返回指向第一個(gè)元素之前迭代器。此元素表現(xiàn)為占位符，試圖訪問它會(huì)導(dǎo)致未定義行為。

函數(shù)原型
iterator before_begin() noexcept; //C++11 起
const_iterator before_begin() const noexcept; //C++11 起
const_iterator cbefore_begin() const noexcept; //C++11 起

2.2.4 容量

empty

功能描述

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

函數(shù)原型
bool empty() const noexcept; //C++11 起, C++20 前
[[nodiscard]] bool empty() const noexcept; //C++20 起
其底層實(shí)現(xiàn)就是檢查容器是否無元素，即判斷是否begin() == end()。

max_size

功能描述

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

函數(shù)原型
size_type max_size() const noexcept; //C++11 起
注：此值通常反映容器大小上的理論極限，至多為 std::numeric_limits<difference_type>::max() 。運(yùn)行時(shí)，可用 RAM 總量可能會(huì)限制容器大小到小于 max_size() 的值。

2.2.5 修改器

clear

功能描述

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

函數(shù)原型
void clear() noexcept; //C++11 起

insert_after

功能描述

在某個(gè)元素后插入新元素，在容器中的指定位置后插入元素。

函數(shù)原型
//在 pos 所指向的元素后插入 value
//返回值：指向被插入元素的迭代器。
iterator insert_after( const_iterator pos, const T& value ); //C++11 起
iterator insert_after( const_iterator pos, T&& value ); //C++11 起

//在 pos 所指向的元素后插入 value 的 count 個(gè)副本
//返回值：指向最后被插入元素的迭代器，或若 count==0 則為 pos 。
iterator insert_after( const_iterator pos, size_type count, const T& value ); //C++11 起

//在 pos 所指向的元素后插入來自范圍 [first, last) 的元素。若 first 與 last 是指向 *this 中的迭代器則行為未定義。
//返回值：指向最后被插入元素的迭代器，或若 first==last 則為 pos 。
template< class InputIt >
iterator insert_after( const_iterator pos, InputIt first, InputIt last ); //C++11 起

//插入來自 initializer_list ilist 的元素。
//返回值：指向最后被插入元素的迭代器，或若 ilist 為空則為 pos 。
iterator insert_after( const_iterator pos, std::initializer_list<T> ilist ); //C++11 起
示例
std::forward_list<std::string> words{"the", "frogurt", "is", "also", "cursed"};
// words: [the, frogurt, is, also, cursed]

auto beginIt = words.begin();
words.insert_after(beginIt, "strawberry");
// words: [the, strawberry, frogurt, is, also, cursed]

auto anotherIt = beginIt;
++anotherIt;
anotherIt = words.insert_after(anotherIt, 2, "strawberry1");
// words: [the, strawberry, strawberry1, strawberry1, frogurt, is, also, cursed]

std::vector<std::string>
?V = {"apple", "banana", "cherry"};
anotherIt = words.insert_after(anotherIt, V.begin(), V.end());
// words: [the, strawberry, strawberry1, strawberry1, apple, banana, cherry, frogurt, is, also, cursed]

words.insert_after(anotherIt, {"jackfruit", "kiwifruit", "lime", "mango"});
// words: [the, strawberry, strawberry, strawberry, apple, banana, cherry, jackfruit, kiwifruit, lime, mango, frogurt, is, also, cursed]

emplace_after

功能描述

在元素后原位構(gòu)造元素。在容器中的指定位置后插入新元素。原位構(gòu)造元素，即不進(jìn)行復(fù)制或移動(dòng)操作。準(zhǔn)確地以與提供給函數(shù)者相同的參數(shù)調(diào)用元素的構(gòu)造函數(shù)。沒有引用和迭代器會(huì)失效。

函數(shù)原型
/*----------------------------------
?pos：新元素將構(gòu)造于其后的迭代器
?args：轉(zhuǎn)發(fā)給元素構(gòu)造函數(shù)的參數(shù)
?返回值iterator：指向新元素的迭代器
------------------------------------*/
template< class... Args >
iterator emplace_after( const_iterator pos, Args&&... args ); //C++11 起

earse_after

功能描述

擦除元素后的元素.

函數(shù)原型
//移除 pos 后的元素
//返回值：指向后隨被擦除元素的迭代器，或若不存在這種元素則為 end()
iterator erase_after( const_iterator pos ); //C++11 起

//移除 first 后 last 前的元素
//返回值：last
iterator erase_after( const_iterator first, const_iterator last ); //C++11 起
示例
std::forward_list<int> l = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

//l.erase( l.begin() ); // 錯(cuò)誤：沒有名為erase的成員函數(shù)

l.erase_after( l.before_begin() ); // 移除首元素

for( auto n : l ) std::cout << n << " ";
std::cout << '\n';
//2 3 4 5 6 7 8 9

auto fi= std::next( l.begin() );
auto la= std::next( fi, 3 );

l.erase_after( fi, la );

for( auto n : l ) std::cout << n << " ";
std::cout << '\n';
//2 3 6 7 8 9

push_front

功能描述

插入元素到容器起始。前附給定元素 value 到容器起始。沒有引用和迭代器會(huì)失效。

函數(shù)原型
void push_front( const T& value ); //C++11 起
void push_front( T&& value ); //C++11 起

emplace_front

功能描述

在容器頭部原位構(gòu)造元素。插入新元素到容器起始。

函數(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

功能描述

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

函數(shù)原型
void pop_front(); //C++11 起

resize

功能描述

改變?nèi)萜髦锌纱鎯?chǔ)元素的個(gè)數(shù)。

函數(shù)原型
//重設(shè)容器大小以容納 count 個(gè)元素，在 count == size() 時(shí)不做任何事。
//如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個(gè)元素。
//如果當(dāng)前大小小于 count，那么后附額外的默認(rèn)插入的元素
void resize( size_type count );

//重設(shè)容器大小以容納 count 個(gè)元素，在 count == size() 時(shí)不做任何事。
//如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個(gè)元素。
//如果當(dāng)前大小小于 count，那么后附額外的 value 的副本
void resize( size_type count, const value_type& value );

swap

功能描述

交換內(nèi)容。

函數(shù)原型
void swap( forward_list& other ); //C++11 起, C++17 前
void swap( forward_list& other ) noexcept(); //C++17 起
將內(nèi)容與 other 的交換。不在單獨(dú)的元素上調(diào)用任何移動(dòng)、復(fù)制或交換操作。所有迭代器和引用保持有效。在操作后，未指明保有此容器中 end() 值的迭代器指代此容器還是另一容器。

2.2.6 操作

merge

功能描述

合并二個(gè)已排序列表。

函數(shù)原型
//用 operator< 比較元素
void merge( forward_list& other ); //C++11 起
void merge( forward_list&& other ); //C++11 起

//用給定的比較函數(shù) comp
template < class Compare >
void merge( forward_list& other, Compare comp ); //C++11 起
template < class Compare >
void merge( forward_list&& other, Compare comp ); //C++11 起
如果 other 與 *this 指代同一對(duì)象，那么什么也不做。否則，將兩個(gè)已排序鏈表歸并為一個(gè)。鏈表應(yīng)以升序排序。不復(fù)制元素，并且在操作后容器 other 會(huì)變?yōu)榭?。不?huì)無效化任何引用或迭代器，但被移動(dòng)元素的迭代器現(xiàn)在指代到 *this 中，而不是到 other 中。
注：對(duì)于兩個(gè)鏈表中的等價(jià)元素，來自 *this 的元素始終在來自 other 的元素之前，并且 *this 和 other 的等價(jià)元素順序不更改。如果 get_allocator() != other.get_allocator()，那么行為未定義。
示例
std::forward_list<int> list1 = {5, 9, 1, 3, 3};
std::forward_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_after

功能描述

從另一 forward_list 移動(dòng)元素。

函數(shù)原型
/*《參數(shù)說明》
pos ?? ? ? ?- 指向?qū)⒉迦雰?nèi)容到其后的元素的迭代器
other ?? ? ?- 移動(dòng)內(nèi)容來源的另一容器
it ?? ? ? ?- 指向從 other 移動(dòng)到 *this 的元素的迭代器的前趨迭代器
first, last - 從 other 移動(dòng)到 *this 的元素范圍
*/

/*從 other 移動(dòng)所有元素到 *this 。元素被插入到 pos 所指向的元素后。
操作后 other 變?yōu)榭?。?other 與 *this 指代同一對(duì)象則行為未定義。*/
void splice_after( const_iterator pos, forward_list& other ); //C++11 起
void splice_after( const_iterator pos, forward_list&& other ); //C++11 起

/* 從 other 移動(dòng)后隨 it 的迭代器所指向的元素到 *this 。
元素被插入到 pos 所指向的元素后，若 pos == it 或若 pos == ++it 則無效果。*/
void splice_after( const_iterator pos, forward_list& other,
? ? ? ? ? ? ? ? ? const_iterator it ); //C++11 起
void splice_after( const_iterator pos, forward_list&& other,
? ? ? ? ? ? ? ? ? const_iterator it ); //C++11 起

/*從 other 移動(dòng)范圍 (first, last) 中的元素到 *this 。
元素被插入到 pos 所指向的元素后。不移動(dòng) first 所指向的元素。若 pos 是范圍 (first,last) 中的元素則行為未定義。*/
void splice_after( const_iterator pos, forward_list& other,
? ? ? ? ? ? ? ? ? const_iterator first, const_iterator last ); //C++11 起
void splice_after( const_iterator pos, forward_list&& other,
? ? ? ? ? ? ? ? ? const_iterator first, const_iterator last ); //C++11 起
不復(fù)制元素。 pos 必須是指向 *this 中的可解引用迭代器或before_begin()迭代器（特別是end() 不是 pos 的合法參數(shù)值）。若 get_allocator() != other.get_allocator()則行為未定義。沒有迭代器或引用被非法化，指向被移動(dòng)的元素的迭代器現(xiàn)在指代到*this 中，而非 other 中。
示例
std::forward_list<int> l1 = {1, 2, 3, 4, 5};
std::forward_list<int> l2 = {10, 11, 12};

l2.splice_after(l2.cbegin(), l1, l1.cbegin(), l1.cend());
// 不等價(jià)于 l2.splice_after(l2.cbegin(), l1);

for (int n : l1)
?std::cout << n << ' ';
std::cout << '\n';
// 1

for (int n : l2)
?std::cout << n << ' ';
std::cout << '\n';
//10 2 3 4 5 11 12

remove、remove_if

功能描述

移除滿足特定標(biāo)準(zhǔn)的元素。

函數(shù)原型
//移除所有等于 value 的元素
void remove( const T& value ); //C++11 起，C++20 前
size_type remove( const T& value ); //C++20 起

//移除所有謂詞 p 對(duì)它返回 true 的元素
template< class UnaryPredicate >
void remove_if( UnaryPredicate p ); //C++11 起，C++20 前
template< class UnaryPredicate >
size_type remove_if( UnaryPredicate p ); //C++20 起
示例
std::forward_list<int> l = { 1,100,2,3,10,1,11,-1,12 };

l.remove(1); // 移除兩個(gè)等于 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

功能描述

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

函數(shù)原型
void reverse() noexcept; //C++11 起
示例
std::forward_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ù)的重復(fù)元素。從容器移除所有相繼的重復(fù)元素。只留下相等元素組中的第一個(gè)元素。若選擇的比較器不建立等價(jià)關(guān)系則行為未定義。

函數(shù)原型
//用 operator== 比較元素。
void unique(); //C++11 起, C++20 前

//用二元謂詞 p 比較元素。
template< class BinaryPredicate >
void unique( BinaryPredicate p ); //C++11 起, C++20 前
template< class BinaryPredicate >
size_type unique( BinaryPredicate p ); //C++20 起
示例
std::forward_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

功能描述

對(duì)元素進(jìn)行排序。以升序排序元素。保持相等元素的順序。

函數(shù)原型
//用 operator< 比較元素
void sort(); ?//C++11 起

//用給定的比較函數(shù) comp, 在第一參數(shù)小于（即先序于）第二參數(shù)時(shí)返回 true。
template< class Compare >
void sort( Compare comp ); ?//C++11 起
示例
std::forward_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};
// 按照元素個(gè)位數(shù)的大小進(jìn)行排序
list.sort([mod = 10](int x, int y)
? ? ? ? ?{ return (x % mod) < (y % mod); }); // 1 2 22 3 14 25

2.3 非成員函數(shù)

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

功能描述

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

函數(shù)聲明
//1. ==
//返回值：在 forward_list 內(nèi)容相等時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator==( const std::forward_list<T, Alloc>& lhs,
? ? ? ? ? ? ? ? const std::forward_list<T, Alloc>& rhs );

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

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

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

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

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

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

1,2中會(huì)檢查 lhs 與 rhs 的內(nèi)容是否相等，即它們是否擁有相同數(shù)量的元素且 lhs 中每個(gè)元素與 rhs 的同位置元素比較相等。
3-6中按照字典比較lhs和rhs的內(nèi)容，其內(nèi)部等價(jià)于調(diào)用std::lexicographical_compare函數(shù)進(jìn)行比較。
7中也是按字典序比較lhs和rhs的內(nèi)容。其內(nèi)部等價(jià)于調(diào)用std::lexicographical_compare_three_way進(jìn)行比較。返回類型同合成三路比較的結(jié)果類型。其邏輯大致如下：
lhs < rhs ? std::weak_ordering::less :
rhs < lhs ? std::weak_ordering::greater :
? ? ? ? ? ?std::weak_ordering::equivalent
//注：通常情況下less對(duì)應(yīng)的是-1，greater對(duì)應(yīng)1，equivalent對(duì)應(yīng)0
lhs與rhs中的首對(duì)不等價(jià)元素的相對(duì)順序，如果有這種元素；否則是lhs.size() <=> rhs.size()。

示例
std::forward_list<int> alice{1, 2, 3};
std::forward_list<int> bob{7, 8, 9, 10};
std::forward_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';
輸出結(jié)果：
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::forward_list)

功能描述

為 std::forward_list特化 std::swap算法。

函數(shù)原型
template< class T, class Alloc >
void swap( std::forward_list<T, Alloc>& lhs,
? ? ? ? ? std::forward_list<T, Alloc>& rhs ); //C++11 起, C++17 前

template< class T, class Alloc >
void swap( std::forward_list<T, Alloc>& lhs,
? ? ? ? ? std::forward_list<T, Alloc>& rhs ) noexcept(); //C++17 起
交換 lhs 與 rhs 的內(nèi)容。調(diào)用lhs.swap(rhs)。
示例
std::forward_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';
// 打印結(jié)果為2 5 1 4

std::swap(a1, a2);

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

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

std::erase, std::erase_if (std::forward_list)

功能描述

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

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

//從容器中擦除所有滿足pred的元素，pred為應(yīng)該擦除元素則返回true的一元謂詞。
//等價(jià)于 return c.remove_if(pred);
template< class T, class Alloc, class Pred >
?typename std::forward_list<T, Alloc>::size_type
? ?erase_if(std::forward_list<T, Alloc>& c, Pred pred); //C++20 起
返回值為被擦除的元素?cái)?shù)。
示例
std::forward_list<int> c{1, 2, 3, 4, 6};
// 擦除c中的值等于3的元素
auto erased1 = std::erase(c, 3); // erased1 = 1
// 此時(shí)c = {1, 2, 4, 6}

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

3. 總結(jié)

forward_list容器的優(yōu)勢(shì)和劣勢(shì)：

優(yōu)勢(shì)

采用動(dòng)態(tài)內(nèi)存分配，不會(huì)造成內(nèi)存浪費(fèi)和溢出。且使用的內(nèi)存比list小。
重組操作不需要移動(dòng)/復(fù)制元素（適用于存儲(chǔ)具有高復(fù)制/大分配成本的對(duì)象）。

劣勢(shì)

僅在線性時(shí)間內(nèi)隨機(jī)訪問。
只能單向遍歷。
有時(shí)候可能會(huì)由于內(nèi)存局部性錯(cuò)誤而導(dǎo)致遍歷緩慢。

forward_list容器與list的區(qū)別

forward_listlist使用單向鏈表實(shí)現(xiàn)使用雙向鏈表實(shí)現(xiàn)消耗相對(duì)較少的內(nèi)存消耗相對(duì)更多的內(nèi)存由于每個(gè)節(jié)點(diǎn)的指針較少，因此插入和移除元素的開銷更少，因此性能更好。由于每個(gè)節(jié)點(diǎn)的指針更多，插入和刪除元素的開銷更大，因此性能較差。正向順序訪問正向和反向順序訪問比list更有效。效率低于forward_list表。通常用于需要單向順序訪問的情況，例如實(shí)現(xiàn)二叉樹、哈希表、堆棧等。通常用于需要雙向順序訪問的情況，例如在散列中實(shí)現(xiàn)鏈接、圖的鄰接列表表示等。

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

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

標(biāo)簽：

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频