詳解C++ STL模擬實現(xiàn)forward_list
forward_list 概述
forward_list 是 C++ 11 新增的容器，它的實現(xiàn)為單鏈表。
forward_list 是支持從容器中的任何位置快速插入和移除元素的容器，不支持快速隨機訪問。forward_list 和 list 的主要區(qū)別在于，前者的迭代器屬于單向的 Forward Iterator，后者的迭代器屬于雙向的 Bidirectional Iterator。
下面實現(xiàn)的單鏈表為單向帶頭循環(huán)鏈表，實現(xiàn)為循環(huán)鏈表只是因為這樣實現(xiàn)比較簡單，更容易處理 end 的指向。
文章完整代碼：ForwardList · 秦1230/STL study
接口總覽
namespace qgw {
/// @brief forward_list 中每個節(jié)點
/// @tparam T 節(jié)點存儲的數(shù)據(jù)類型
template <class T>
struct _forward_list_node {
_forward_list_node(const T& data = T()); // 節(jié)點類的構(gòu)造函數(shù)
_forward_list_node<T>* _next; // 指向后一節(jié)點
T _data; // 存儲節(jié)點數(shù)據(jù)
};
/// @brief forward_list 的迭代器
/// @tparam T forward_list 數(shù)據(jù)的類型
/// @tparam Ref 數(shù)據(jù)的引用類型
/// @tparam Ptr 數(shù)據(jù)的指針類型
template <class T, class Ref, class Ptr>
struct _forward_list_iterator {
typedef _forward_list_iterator<T, T&, T*> iterator;
typedef _forward_list_iterator<T, Ref, Ptr> self;
typedef Ptr pointer;
typedef Ref reference;
typedef _forward_list_node<T> forward_list_node;
// 構(gòu)造函數(shù)
_forward_list_iterator(forward_list_node* node = nullptr);
// 各種運算符重載
bool operator==(const self& x) const;
bool operator!=(const self& x) const;
reference operator*() const;
pointer operator->() const;
self& operator++();
self operator++(int);
forward_list_node* _node; // 指向?qū)?yīng)的 forward_list 節(jié)點
};
template <class T>
class forward_list {
public:
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef _forward_list_node<T> forward_list_node;
typedef _forward_list_iterator<T, T&, T*> iterator;
typedef _forward_list_iterator<T, const T&, const T*> const_iterator;
public:
// 默認(rèn)成員函數(shù)
forward_list();
forward_list(const forward_list<T>& other);
forward_list<T>& operator=(const forward_list<T>& other);
~forward_list();
// 元素訪問
reference front();
const_reference front() const;
// 迭代器
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// 容量
bool empty() const;
// 修改器
void clear();
iterator insert_after(iterator pos, const_reference val);
void push_front(const_reference val);
iterator erase_after(iterator pos);
void pop_front();
void swap(forward_list& other);
private:
forward_list_node* _node;
};
}
forward_list 的節(jié)點
forward_list 節(jié)點的設(shè)計與 list 的節(jié)點類似，只需兩個成員變量：一個節(jié)點指針和數(shù)據(jù)。
構(gòu)造函數(shù)將數(shù)據(jù)初始化為給定數(shù)據(jù)，再將 _next 指針初始化為空。
/// @brief 節(jié)點類的構(gòu)造函數(shù)
/// @param data 用來構(gòu)造節(jié)點的初值
_forward_list_node(const T& data = T())
: _data(data) {
_next = nullptr;
}
默認(rèn)成員函數(shù)
默認(rèn)構(gòu)造函數(shù)
因為實現(xiàn)的是的單向帶頭循環(huán)鏈表，所以要在構(gòu)造函數(shù)創(chuàng)建一個頭節(jié)點，并將 _next 指針指向自己。
/// @brief 構(gòu)造一個空鏈表
forward_list() {
_node = new forward_list_node; // 創(chuàng)建一個頭節(jié)點
_node->_next = _node; // 后面指向自己
}
析構(gòu)函數(shù)
forward_list 的析構(gòu)函數(shù)，先調(diào)用 clear 釋放數(shù)據(jù)資源，再 delete 掉頭節(jié)點即可。
/// @brief 釋放資源
~forward_list () {
clear();
delete _node;
_node = nullptr;
}
forward_list 的迭代器
forward_list 的節(jié)點在內(nèi)存中不是連續(xù)存儲的，因此不能使用原生指針作為 forward_list 的迭代器。
由于 forward_list 是一個單向鏈表，迭代器必須具備后移的能力，所以 forward_list 提供的是 Forward Iterator。
構(gòu)造函數(shù)
forward_list 的迭代器中成員變量只有一個節(jié)點指針，將其初始化為給定的節(jié)點指針。
/// @brief 迭代器的構(gòu)造函數(shù)
/// @param node 用來構(gòu)造的節(jié)點
_forward_list_iterator(forward_list_node* node = nullptr) {
_node = node;
}
operator==
兩個 forward_list 迭代器的比較，實際上比較的是迭代器所指向的節(jié)點，指向同一節(jié)點即為兩迭代器相同。
/// @brief 判斷兩迭代器指向的節(jié)點是否相同
/// @param x 用來比較的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const {
return _node == x._node;
}
operator!=
operator!= 的實現(xiàn)可以借助 operator==，直接調(diào)用判斷是否相等的函數(shù)，然后返回相反的結(jié)果。
/// @brief 判斷兩迭代器指向的節(jié)點是否不同
/// @param x 用來比較的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const {
return !operator==(x);
}
operator*
當(dāng)我們對一個指針進行解引用時會發(fā)生什么，我們會得到指針指向的數(shù)據(jù)。同理，我們對迭代器進行解引用，得到的是迭代器中節(jié)點指針?biāo)赶蜃兞康闹怠?/p>
/// @brief 獲取指向節(jié)點中的數(shù)據(jù)值
/// @return 返回指向節(jié)點數(shù)據(jù)的引用
reference operator*() const {
return (*_node)._data;
}
operator->
假如我們有如下數(shù)據(jù)類：
// 有一個 Person 類，里面有身高和體重兩個成員
struct Person {
double height;
double weight;
};
此時，我們的數(shù)據(jù)不再是單一的變量了，而是一個結(jié)構(gòu)體變量。我們想讀取其中的數(shù)據(jù)，該怎么操作呢？
Person p1 = { 165, 105 };
Person* p = &p1;
cout << (*p).height << endl; // 獲取身高數(shù)據(jù)
cout << p->weight << endl; // 獲取體重數(shù)據(jù)
我們可以先對直接解引用得到一個 Person 對象，再用 . 操作符訪問其中的變量。
當(dāng)然我們也可以選擇對 Person* 使用 -> 操作符訪問結(jié)構(gòu)體內(nèi)的變量。
于是乎，operator-> 的功能也就很清晰了。當(dāng)我們對迭代器使用 -> 時我們可以直接訪問節(jié)點中的變量。也就是說，我們有一迭代器 iter，其中迭代器中存儲的數(shù)據(jù)類型為 Person，當(dāng)我們使用 iter->height 時，可以直接獲取到身高。
/// @brief 獲取節(jié)點中數(shù)據(jù)的地址
/// @return 返回節(jié)點指向的數(shù)據(jù)的地址
pointer operator->() const {
return &(operator*());
}
看了實現(xiàn)你可能會疑惑 iter-> 獲得的明明是結(jié)構(gòu)體的指針，后面應(yīng)該再跟一個 -> 箭頭才對。是的沒錯，確實應(yīng)該是這樣，不過 iter->->height 的可讀性比較差，所以編譯器會在編譯時自動為我們添加一個箭頭。
operator++
operator++ 運算符的作用是讓迭代器指向 forward_list 中下一節(jié)點。因為 forward_list 是單鏈表不能向前移動，所以不用實現(xiàn) operator--。
前置實現(xiàn)的思路是：通過迭代器中的節(jié)點指針找到下一節(jié)點，然后賦值給迭代器中的節(jié)點指針。
后置實現(xiàn)的思路是：先拷貝一份當(dāng)前位置的迭代器，然后調(diào)用前置 ++，最后返回臨時變量。
需要注意的是：前置 ++ 返回的是前進后迭代器的引用，后置 ++ 返回的是一個臨時變量。
/// @brief 前置 ++
/// @return 返回前進一步后的迭代器
self& operator++() {
_node = _node->_next;
return *this;
}
/// @brief 后置 ++
/// @param 無作用，只是為了與前置 ++ 進行區(qū)分，形成重載
/// @return 返回當(dāng)前的迭代器
self operator++(int) {
self tmp = *this;
++(*this);
return tmp;
}
元素訪問
front
front 獲取容器首元素的引用，調(diào)用 begin 得到首元素的迭代器，再解引用即可。
因為 forward_list 的迭代器只能單向移動，故不能快速獲得鏈表中最后一個節(jié)點。
/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() {
return *begin();
}
// 與上面唯一不同就是用于 const 容器
const_reference front() const {
return *begin();
}
迭代器
begin
begin 獲取的是首元素的迭代器，根據(jù)上圖，直接返回頭節(jié)點的下一位置即可。
/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
// 根據(jù)節(jié)點指針構(gòu)造迭代器
return iterator(_node->_next);
}
// const 版本供 const 容器使用
const_iterator begin() const {
return const_iterator(_node->_next);
}
end
end 獲取的是最后一個元素下一個位置的迭代器，根據(jù)上圖就是 _node 所指向的節(jié)點。
/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() {
// 調(diào)用 iterator 構(gòu)造函數(shù)
return iterator(_node);
}
const_iterator end() const {
return const_iterator(_node);
}
容量
empty
begin 和 end 指向相同，說明鏈表此時只有一個頭節(jié)點，鏈表為空。
/// @brief 檢查容器是否無元素
/// @return 若容器為空則為 true，否則為 false
bool empty() const {
return begin() == end();
}
修改器
insert_after
根據(jù) STL 的習(xí)慣，插入操作會將新元素插入于指定位置之前，而非之后。然而 forward_list 是一個單向鏈表，它沒有任何方便的方法可以定位出前一個位置，它必須從頭找。因此，forward_list 中提供的插入操作，是插入在指定位置之后。
下圖為：只有 0、1 兩個元素的單鏈表，在 0 之后插入元素值為 2 的節(jié)點的示意圖。
插入的過程非常簡單：
1.創(chuàng)建一個要插入的節(jié)點
2.插入節(jié)點的 _next 指向 pos 后一位置的節(jié)點
3.pos 的 _next 指向要插入的節(jié)點
/// @brief 在容器中的指定位置后插入元素
/// @param pos 內(nèi)容將插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val) {
forward_list_node* tmp = new forward_list_node(val); // 創(chuàng)建要插入的節(jié)點
tmp->_next = pos._node->_next; // (1)
pos._node->_next = tmp; // (2)
return tmp;
}
push_front
push_front 的作用是在容器起始處插入元素。
直接調(diào)用 insert_after 插入就行，需要注意的是，insert_after 是在給定位置之后插入，所以應(yīng)傳入頭節(jié)點對應(yīng)的迭代器位置。
/// @brief 頭插給定元素 val 到容器起始
/// @param val 要頭插的元素值
void push_front(const_reference val) {
// end() 返回頭節(jié)點位置的迭代器，在這之后插入是頭插
insert_after(end(), val);
}
erase_after
下圖為：有三個元素 0、1、2 的鏈表，刪除 pos 指向節(jié)點之后節(jié)點（值為 1）的示意圖。
刪除的過程非常簡單：
1.記錄 pos 的下一節(jié)點 nextNode
2.將 pos 的 _next 指向 nextNode 的下一個節(jié)點
3.delete 釋放掉 nextNode 所指向的節(jié)點
/// @brief 從容器移除 pos 后面一個元素
/// @param pos 指向要被移除元素前一個元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) {
forward_list_node* nextNode = pos._node->_next; // 記錄 pos 指向節(jié)點的下一節(jié)點
pos._node->_next = nextNode->_next; // (1)
delete (nextNode);
return (iterator)(pos._node->_next);
}
pop_front
pop_front 移除容器的首元素，也就是 end 指向的下一節(jié)點。
/// @brief 移除容器首元素
void pop_front() {
erase_after(end());
}
clear
clear 用于清空容器所有數(shù)據(jù)，不清理頭節(jié)點。
要注意 erase_after 刪除給定位置下一個節(jié)點，end 的下一個是第一個元素，這樣以次刪除直到容器為空，即只剩一個頭節(jié)點。
/// @brief 從容器擦除所有元素
void clear() {
while (!empty()) {
erase_after(end());
}
}
swap
swap 用來交換兩個 forward_list容器，不用交換 forward_list 中每個元素的值，直接交換 _node 指針即可。
/// @brief 將內(nèi)容與 other 的交換
/// @param other 要與之交換內(nèi)容的容器
void swap(forward_list& other) {
std::swap(_node, other._node);
}以上就是詳解C++ STL模擬實現(xiàn)forward_list的詳細(xì)內(nèi)容，更多關(guān)于C++ STL forward_list的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++連接mysql數(shù)據(jù)庫并讀取數(shù)據(jù)的具體步驟
在實際開發(fā)中我們經(jīng)常需要對數(shù)據(jù)庫進行訪問,針對不同類型的數(shù)據(jù)庫（如MySQL、sqLite、Access、Excel等）,如果采用不同的方法進行連接，會把我們搞崩潰,下面這篇文章主要給大家介紹了關(guān)于C++連接mysql數(shù)據(jù)庫并讀取數(shù)據(jù)的具體步驟,需要的朋友可以參考下2023-04-04
C/C++中關(guān)鍵字typedef的理解不是多透徹，今天小編抽空給大家分享下C及C++中typedef的簡單使用介紹，需要的朋友可以參考下2016-10-10
這篇文章主要為大家介紹了C語言的指針，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了C++之std命名空間使用,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了顯示內(nèi)存狀態(tài)示例，代碼簡單，下面直接看代碼,需要的朋友可以參考下2014-02-02
這篇文章主要為大家詳細(xì)介紹了opencv實現(xiàn)矩形檢測，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要為大家介紹了C++類與對象，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
排序算法是程序中常用的算法,下面這篇文章主要給大家介紹了關(guān)于十大排序算法的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
這篇文章主要介紹了c++ 發(fā)展的過程，幫助大家更好的了解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08
基于Matlab實現(xiàn)離散系統(tǒng)分岔圖的繪制
這篇文章主要介紹了如何利用Matlab實現(xiàn)離散分岔圖的繪制，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2022-04-04