詳解C++ STL模擬實(shí)現(xiàn)forward_list

更新時間：2023年01月13日 14:07:15 作者：叫我小秦就好了

forward_list是C++ 11新增的容器，它支持從容器中的任何位置快速插入和移除元素的容器，不支持快速隨機(jī)訪問。本文將模擬實(shí)現(xiàn)forward_list，感興趣的可以了解一下

forward_list 概述

forward_list 是 C++ 11 新增的容器，它的實(shí)現(xiàn)為單鏈表。

forward_list 是支持從容器中的任何位置快速插入和移除元素的容器，不支持快速隨機(jī)訪問。forward_list 和 list 的主要區(qū)別在于，前者的迭代器屬于單向的 Forward Iterator，后者的迭代器屬于雙向的 Bidirectional Iterator。

下面實(shí)現(xiàn)的單鏈表為單向帶頭循環(huán)鏈表，實(shí)現(xiàn)為循環(huán)鏈表只是因為這樣實(shí)現(xiàn)比較簡單，更容易處理 end 的指向。

文章完整代碼：ForwardList · 秦1230/STL study

接口總覽

namespace qgw {
	/// @brief forward_list 中每個節(jié)點(diǎn)
	/// @tparam T 節(jié)點(diǎn)存儲的數(shù)據(jù)類型
	template <class T>
	struct _forward_list_node {
		_forward_list_node(const T& data = T());	// 節(jié)點(diǎn)類的構(gòu)造函數(shù)
			
		_forward_list_node<T>* _next;				// 指向后一節(jié)點(diǎn)
		T _data;									// 存儲節(jié)點(diǎn)數(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);

		// 各種運(yùn)算符重載
		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é)點(diǎn)
	};

	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é)點(diǎn)

forward_list 節(jié)點(diǎn)的設(shè)計與 list 的節(jié)點(diǎn)類似，只需兩個成員變量：一個節(jié)點(diǎn)指針和數(shù)據(jù)。

構(gòu)造函數(shù)將數(shù)據(jù)初始化為給定數(shù)據(jù)，再將 _next 指針初始化為空。

/// @brief 節(jié)點(diǎn)類的構(gòu)造函數(shù)
/// @param data 用來構(gòu)造節(jié)點(diǎn)的初值
_forward_list_node(const T& data = T())
    : _data(data) {
        _next = nullptr;
    }

默認(rèn)成員函數(shù)

默認(rèn)構(gòu)造函數(shù)

因為實(shí)現(xiàn)的是的單向帶頭循環(huán)鏈表，所以要在構(gòu)造函數(shù)創(chuàng)建一個頭節(jié)點(diǎn)，并將 _next 指針指向自己。

/// @brief 構(gòu)造一個空鏈表
forward_list() {
    _node = new forward_list_node;    // 創(chuàng)建一個頭節(jié)點(diǎn)
    _node->_next = _node;            // 后面指向自己
}

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

forward_list 的析構(gòu)函數(shù)，先調(diào)用 clear 釋放數(shù)據(jù)資源，再 delete 掉頭節(jié)點(diǎn)即可。

/// @brief 釋放資源
~forward_list () {
    clear();
    delete _node;
    _node = nullptr;
}

forward_list 的迭代器

forward_list 的節(jié)點(diǎn)在內(nèi)存中不是連續(xù)存儲的，因此不能使用原生指針作為 forward_list 的迭代器。

由于 forward_list 是一個單向鏈表，迭代器必須具備后移的能力，所以 forward_list 提供的是 Forward Iterator。

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

forward_list 的迭代器中成員變量只有一個節(jié)點(diǎn)指針，將其初始化為給定的節(jié)點(diǎn)指針。

/// @brief 迭代器的構(gòu)造函數(shù)
/// @param node 用來構(gòu)造的節(jié)點(diǎn)
_forward_list_iterator(forward_list_node* node = nullptr) {
    _node = node;
}

operator==

兩個 forward_list 迭代器的比較，實(shí)際上比較的是迭代器所指向的節(jié)點(diǎn)，指向同一節(jié)點(diǎn)即為兩迭代器相同。

/// @brief 判斷兩迭代器指向的節(jié)點(diǎn)是否相同
/// @param x 用來比較的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const {
    return _node == x._node;
}

operator!=

operator!= 的實(shí)現(xiàn)可以借助 operator==，直接調(diào)用判斷是否相等的函數(shù)，然后返回相反的結(jié)果。

/// @brief 判斷兩迭代器指向的節(jié)點(diǎn)是否不同
/// @param x 用來比較的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const {
    return !operator==(x);
}

operator*

當(dāng)我們對一個指針進(jìn)行解引用時會發(fā)生什么，我們會得到指針指向的數(shù)據(jù)。同理，我們對迭代器進(jìn)行解引用，得到的是迭代器中節(jié)點(diǎn)指針?biāo)赶蜃兞康闹怠?/p>

/// @brief 獲取指向節(jié)點(diǎn)中的數(shù)據(jù)值
/// @return 返回指向節(jié)點(diǎn)數(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é)點(diǎn)中的變量。也就是說，我們有一迭代器 iter，其中迭代器中存儲的數(shù)據(jù)類型為 Person，當(dāng)我們使用 iter->height 時，可以直接獲取到身高。

/// @brief 獲取節(jié)點(diǎn)中數(shù)據(jù)的地址
/// @return 返回節(jié)點(diǎn)指向的數(shù)據(jù)的地址
pointer operator->() const {
    return &(operator*());
}

看了實(shí)現(xiàn)你可能會疑惑 iter-> 獲得的明明是結(jié)構(gòu)體的指針，后面應(yīng)該再跟一個 -> 箭頭才對。是的沒錯，確實(shí)應(yīng)該是這樣，不過 iter->->height 的可讀性比較差，所以編譯器會在編譯時自動為我們添加一個箭頭。

operator++

operator++ 運(yùn)算符的作用是讓迭代器指向 forward_list 中下一節(jié)點(diǎn)。因為 forward_list 是單鏈表不能向前移動，所以不用實(shí)現(xiàn) operator--。

前置實(shí)現(xiàn)的思路是：通過迭代器中的節(jié)點(diǎn)指針找到下一節(jié)點(diǎn)，然后賦值給迭代器中的節(jié)點(diǎn)指針。

后置實(shí)現(xiàn)的思路是：先拷貝一份當(dāng)前位置的迭代器，然后調(diào)用前置 ++，最后返回臨時變量。

需要注意的是：前置 ++ 返回的是前進(jìn)后迭代器的引用，后置 ++ 返回的是一個臨時變量。

/// @brief 前置 ++
/// @return 返回前進(jìn)一步后的迭代器
self& operator++() {
    _node = _node->_next;
    return *this;
}

/// @brief 后置 ++
/// @param  無作用，只是為了與前置 ++ 進(jìn)行區(qū)分，形成重載
/// @return 返回當(dāng)前的迭代器
self operator++(int) {
    self tmp = *this;
    ++(*this);
    return tmp;
}

元素訪問

front

front 獲取容器首元素的引用，調(diào)用 begin 得到首元素的迭代器，再解引用即可。

因為 forward_list 的迭代器只能單向移動，故不能快速獲得鏈表中最后一個節(jié)點(diǎn)。

/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() {
    return *begin();
}

// 與上面唯一不同就是用于 const 容器
const_reference front() const {
    return *begin();
}

迭代器

begin

begin 獲取的是首元素的迭代器，根據(jù)上圖，直接返回頭節(jié)點(diǎn)的下一位置即可。

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
    // 根據(jù)節(jié)點(diǎn)指針構(gòu)造迭代器
    return iterator(_node->_next);
}

// const 版本供 const 容器使用
const_iterator begin() const {
    return const_iterator(_node->_next);
}

end

end 獲取的是最后一個元素下一個位置的迭代器，根據(jù)上圖就是 _node 所指向的節(jié)點(diǎn)。

/// @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é)點(diǎn)，鏈表為空。

/// @brief 檢查容器是否無元素
/// @return 若容器為空則為 true，否則為 false
bool empty() const {
    return begin() == end();
}

修改器

insert_after

根據(jù) STL 的習(xí)慣，插入操作會將新元素插入于指定位置之前，而非之后。然而 forward_list 是一個單向鏈表，它沒有任何方便的方法可以定位出前一個位置，它必須從頭找。因此，forward_list 中提供的插入操作，是插入在指定位置之后。

下圖為：只有 0、1 兩個元素的單鏈表，在 0 之后插入元素值為 2 的節(jié)點(diǎn)的示意圖。

插入的過程非常簡單：

1.創(chuàng)建一個要插入的節(jié)點(diǎn)

2.插入節(jié)點(diǎn)的 _next 指向 pos 后一位置的節(jié)點(diǎn)

3.pos 的 _next 指向要插入的節(jié)點(diǎn)

/// @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é)點(diǎn)
    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é)點(diǎn)對應(yīng)的迭代器位置。

/// @brief 頭插給定元素 val 到容器起始
/// @param val 要頭插的元素值
void push_front(const_reference val) {
    // end() 返回頭節(jié)點(diǎn)位置的迭代器，在這之后插入是頭插
    insert_after(end(), val);
}

erase_after

下圖為：有三個元素 0、1、2 的鏈表，刪除 pos 指向節(jié)點(diǎn)之后節(jié)點(diǎn)（值為 1）的示意圖。

刪除的過程非常簡單：

1.記錄 pos 的下一節(jié)點(diǎn) nextNode

2.將 pos 的 _next 指向 nextNode 的下一個節(jié)點(diǎn)

3.delete 釋放掉 nextNode 所指向的節(jié)點(diǎn)

/// @brief 從容器移除 pos 后面一個元素
/// @param pos 指向要被移除元素前一個元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) {
    forward_list_node* nextNode = pos._node->_next;        // 記錄 pos 指向節(jié)點(diǎn)的下一節(jié)點(diǎn)
    pos._node->_next = nextNode->_next;                    // (1)
    delete (nextNode);
    return (iterator)(pos._node->_next);
}

pop_front

pop_front 移除容器的首元素，也就是 end 指向的下一節(jié)點(diǎn)。

/// @brief 移除容器首元素
void pop_front() {
    erase_after(end());
}

clear

clear 用于清空容器所有數(shù)據(jù)，不清理頭節(jié)點(diǎn)。

要注意 erase_after 刪除給定位置下一個節(jié)點(diǎn)，end 的下一個是第一個元素，這樣以次刪除直到容器為空，即只剩一個頭節(jié)點(diǎn)。

/// @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模擬實(shí)現(xiàn)forward_list的詳細(xì)內(nèi)容，更多關(guān)于C++ STL forward_list的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片