日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

詳解C++?STL模擬實現forward_list_C 語言

作者：叫我小秦就好了 ? 更新時間： 2023-03-03 編程語言

forward_list 概述

forward_list 是 C++ 11 新增的容器，它的實現為單鏈表。

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

下面實現的單鏈表為單向帶頭循環鏈表，實現為循環鏈表只是因為這樣實現比較簡單，更容易處理 end 的指向。

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

接口總覽

namespace qgw {
	/// @brief forward_list 中每個節點
	/// @tparam T 節點存儲的數據類型
	template <class T>
	struct _forward_list_node {
		_forward_list_node(const T& data = T());	// 節點類的構造函數
			
		_forward_list_node<T>* _next;				// 指向后一節點
		T _data;									// 存儲節點數據
	};

	/// @brief forward_list 的迭代器
	/// @tparam T forward_list 數據的類型
	/// @tparam Ref 數據的引用類型
	/// @tparam Ptr 數據的指針類型
	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;

		// 構造函數
		_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;	// 指向對應的 forward_list 節點
	};

	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:
		// 默認成員函數
		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 的節點

forward_list 節點的設計與 list 的節點類似，只需兩個成員變量：一個節點指針和數據。

構造函數將數據初始化為給定數據，再將 _next 指針初始化為空。

/// @brief 節點類的構造函數
/// @param data 用來構造節點的初值
_forward_list_node(const T& data = T())
    : _data(data) {
        _next = nullptr;
    }

默認成員函數

默認構造函數

因為實現的是的單向帶頭循環鏈表，所以要在構造函數創建一個頭節點，并將 _next 指針指向自己。

/// @brief 構造一個空鏈表
forward_list() {
    _node = new forward_list_node;    // 創建一個頭節點
    _node->_next = _node;            // 后面指向自己
}

析構函數

forward_list 的析構函數，先調用 clear 釋放數據資源，再 delete 掉頭節點即可。

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

forward_list 的迭代器

forward_list 的節點在內存中不是連續存儲的，因此不能使用原生指針作為 forward_list 的迭代器。

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

構造函數

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

/// @brief 迭代器的構造函數
/// @param node 用來構造的節點
_forward_list_iterator(forward_list_node* node = nullptr) {
    _node = node;
}

operator==

兩個 forward_list 迭代器的比較，實際上比較的是迭代器所指向的節點，指向同一節點即為兩迭代器相同。

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

operator!=

operator!= 的實現可以借助 operator==，直接調用判斷是否相等的函數，然后返回相反的結果。

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

operator*

當我們對一個指針進行解引用時會發生什么，我們會得到指針指向的數據。同理，我們對迭代器進行解引用，得到的是迭代器中節點指針所指向變量的值。

/// @brief 獲取指向節點中的數據值
/// @return 返回指向節點數據的引用
reference operator*() const {
    return (*_node)._data;
}

operator->

假如我們有如下數據類：

// 有一個 Person 類，里面有身高和體重兩個成員
struct Person {
    double height;
    double weight;
};

此時，我們的數據不再是單一的變量了，而是一個結構體變量。我們想讀取其中的數據，該怎么操作呢？

Person p1 = { 165, 105 };
Person* p = &p1;
cout << (*p).height << endl;    // 獲取身高數據
cout << p->weight << endl;        // 獲取體重數據

我們可以先對直接解引用得到一個 Person 對象，再用 . 操作符訪問其中的變量。

當然我們也可以選擇對 Person* 使用 -> 操作符訪問結構體內的變量。

于是乎，operator-> 的功能也就很清晰了。當我們對迭代器使用 -> 時我們可以直接訪問節點中的變量。也就是說，我們有一迭代器 iter，其中迭代器中存儲的數據類型為 Person，當我們使用 iter->height 時，可以直接獲取到身高。

/// @brief 獲取節點中數據的地址
/// @return 返回節點指向的數據的地址
pointer operator->() const {
    return &(operator*());
}

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

operator++

operator++ 運算符的作用是讓迭代器指向 forward_list 中下一節點。因為 forward_list 是單鏈表不能向前移動，所以不用實現 operator--。

前置實現的思路是：通過迭代器中的節點指針找到下一節點，然后賦值給迭代器中的節點指針。

后置實現的思路是：先拷貝一份當前位置的迭代器，然后調用前置 ++，最后返回臨時變量。

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

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

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

元素訪問

front

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

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

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

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

迭代器

begin

begin 獲取的是首元素的迭代器，根據上圖，直接返回頭節點的下一位置即可。

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
    // 根據節點指針構造迭代器
    return iterator(_node->_next);
}

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

end

end 獲取的是最后一個元素下一個位置的迭代器，根據上圖就是 _node 所指向的節點。

/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() {
    // 調用 iterator 構造函數
    return iterator(_node);
}

const_iterator end() const {
    return const_iterator(_node);
}

容量

empty

begin 和 end 指向相同，說明鏈表此時只有一個頭節點，鏈表為空。

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

修改器

insert_after

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

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

插入的過程非常簡單：

1.創建一個要插入的節點

2.插入節點的 _next 指向 pos 后一位置的節點

3.pos 的 _next 指向要插入的節點

/// @brief 在容器中的指定位置后插入元素
/// @param pos 內容將插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val) {
    forward_list_node* tmp = new forward_list_node(val);    // 創建要插入的節點
    tmp->_next = pos._node->_next;                            // (1)
    pos._node->_next = tmp;                                    // (2)
    return tmp;
}

push_front

push_front 的作用是在容器起始處插入元素。

直接調用 insert_after 插入就行，需要注意的是，insert_after 是在給定位置之后插入，所以應傳入頭節點對應的迭代器位置。

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

erase_after

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

刪除的過程非常簡單：

1.記錄 pos 的下一節點 nextNode

2.將 pos 的 _next 指向 nextNode 的下一個節點

3.delete 釋放掉 nextNode 所指向的節點

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

pop_front

pop_front 移除容器的首元素，也就是 end 指向的下一節點。

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

clear

clear 用于清空容器所有數據，不清理頭節點。

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

/// @brief 從容器擦除所有元素
void clear() {
    while (!empty()) {
        erase_after(end());
    }
}

swap

swap 用來交換兩個 forward_list容器，不用交換 forward_list 中每個元素的值，直接交換 _node 指針即可。

/// @brief 將內容與 other 的交換
/// @param other 要與之交換內容的容器
void swap(forward_list& other) {
    std::swap(_node, other._node);
}

原文鏈接：https://blog.csdn.net/qq_40080842/article/details/128647168

欄目分類
最近更新