list模擬實(shí)現(xiàn)

成員類型表

這個(gè)表中列出了C++標(biāo)準(zhǔn)庫(kù)中l(wèi)ist容器的一些成員類型定義。這些類型定義是為了使list能夠與C++標(biāo)準(zhǔn)庫(kù)的其他組件協(xié)同工作，并提供一些通用的標(biāo)準(zhǔn)接口。每個(gè)成員類型的用處：

value_type: 這個(gè)成員類型代表list容器中存儲(chǔ)的數(shù)據(jù)類型，即模板參數(shù)T的類型。

allocator_type: 這個(gè)成員類型代表分配器的類型，用于為容器的內(nèi)存分配和管理。默認(rèn)情況下，使用allocator<value_type>作為分配器。

reference: 這個(gè)成員類型表示對(duì)元素的引用類型。對(duì)于默認(rèn)分配器，它是value_type&，即對(duì)元素的引用。

const_reference: 這個(gè)成員類型表示對(duì)常量元素的引用類型。對(duì)于默認(rèn)分配器，它是const value_type&，即對(duì)常量元素的引用。

pointer: 這個(gè)成員類型表示指向元素的指針類型。對(duì)于默認(rèn)分配器，它是value_type*，即指向元素的指針。

const_pointer: 這個(gè)成員類型表示指向常量元素的指針類型。對(duì)于默認(rèn)分配器，它是const value_type*，即指向常量元素的指針。

iterator: 這個(gè)成員類型是一個(gè)雙向迭代器類型，可以用于遍歷容器的元素。它可以隱式轉(zhuǎn)換為const_iterator，允許在遍歷時(shí)修改元素。

const_iterator: 這個(gè)成員類型也是一個(gè)雙向迭代器類型，用于遍歷常量容器的元素，不允許修改元素。

reverse_iterator: 這個(gè)成員類型是iterator的逆向迭代器，可以從容器尾部向頭部遍歷。

const_reverse_iterator: 這個(gè)成員類型是const_iterator的逆向迭代器，用于從常量容器的尾部向頭部遍歷。

difference_type: 這個(gè)成員類型表示兩個(gè)迭代器之間的距離，通常使用的是ptrdiff_t，與指針的差值類型相同。

size_type: 這個(gè)成員類型表示非負(fù)整數(shù)的類型，通常使用的是size_t，用于表示容器的大小。

這些成員類型的定義使得list容器能夠與其他C++標(biāo)準(zhǔn)庫(kù)的組件以及用戶自定義的代碼進(jìn)行交互，從而實(shí)現(xiàn)更加通用和靈活的功能。

list_node節(jié)點(diǎn)結(jié)構(gòu)定義

定義鏈表的節(jié)點(diǎn)結(jié)構(gòu) list_node，用于存儲(chǔ)鏈表中的每個(gè)元素。讓我們逐一解釋每個(gè)部分的含義。

template<class T>
struct list_node
{
    T _data;            // 存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)
    list_node<T>* _next;  // 指向下一個(gè)節(jié)點(diǎn)的指針
    list_node<T>* _prev;  // 指向前一個(gè)節(jié)點(diǎn)的指針

    // 構(gòu)造函數(shù)
    list_node(const T& x = T())
        :_data(x)        // 使用參數(shù) x 初始化 _data
        , _next(nullptr) // 初始化 _next 為 nullptr
        , _prev(nullptr) // 初始化 _prev 為 nullptr
    {}
};

T _data;：存儲(chǔ)節(jié)點(diǎn)中的數(shù)據(jù)，類型為模板參數(shù) T，可以是任意數(shù)據(jù)類型。

list_node<T>* _next;：指向下一個(gè)節(jié)點(diǎn)的指針，用于構(gòu)建鏈表結(jié)構(gòu)。初始時(shí)設(shè)為 nullptr，表示當(dāng)前節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)。

list_node<T>* _prev;：指向前一個(gè)節(jié)點(diǎn)的指針，同樣用于構(gòu)建鏈表結(jié)構(gòu)。初始時(shí)設(shè)為 nullptr，表示當(dāng)前節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)。

構(gòu)造函數(shù) list_node(const T& x = T())：構(gòu)造函數(shù)可以接收一個(gè)參數(shù) x，用于初始化節(jié)點(diǎn)的數(shù)據(jù)。如果沒有傳入?yún)?shù)，默認(rèn)構(gòu)造一個(gè)空節(jié)點(diǎn)。

通過(guò)這個(gè)節(jié)點(diǎn)結(jié)構(gòu)，你可以創(chuàng)建一個(gè)雙向鏈表list，將不同類型的數(shù)據(jù)存儲(chǔ)在節(jié)點(diǎn)中，并連接節(jié)點(diǎn)以構(gòu)建鏈表的結(jié)構(gòu)。這個(gè)節(jié)點(diǎn)結(jié)構(gòu)為鏈表的實(shí)現(xiàn)提供了基礎(chǔ)。

std::__reverse_iterator逆向迭代器實(shí)現(xiàn)

#pragma once

namespace xzq
{
	// 復(fù)用，迭代器適配器
	template<class Iterator, class Ref, class Ptr>
	struct __reverse_iterator
	{
		Iterator _cur;
		typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;

		__reverse_iterator(Iterator it)
			:_cur(it)
		{}

		RIterator operator++()
		{
			--_cur;
			return *this;
		}

		RIterator operator--()
		{
			++_cur;
			return *this;
		}

		Ref operator*()
		{
			auto tmp = _cur;
			--tmp;
			return *tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		bool operator!=(const RIterator& it)
		{
			return _cur != it._cur;
		}
	};
}

說(shuō)明：

__reverse_iterator 類模板定義了一個(gè)逆向迭代器，它有三個(gè)模板參數(shù)：Iterator（迭代器的類型）、Ref（引用類型）和 Ptr（指針類型）。
_cur 是一個(gè)私有成員變量，保存當(dāng)前迭代器的位置。
構(gòu)造函數(shù)接受一個(gè)正向迭代器作為參數(shù)，并將其存儲(chǔ)在 _cur 成員變量中。
operator++() 重載了遞增操作符，讓迭代器向前移動(dòng)一個(gè)位置。
operator--() 重載了遞減操作符，讓迭代器向后移動(dòng)一個(gè)位置。
operator*() 重載了解引用操作符，返回逆向迭代器指向的元素的引用。
operator->() 重載了成員訪問(wèn)操作符，返回逆向迭代器指向的元素的指針。
operator!=() 重載了不等于操作符，用于判斷兩個(gè)逆向迭代器是否不相等。

這個(gè)逆向迭代器可以用于支持從容器的尾部向頭部的方向進(jìn)行迭代。在 C++ 標(biāo)準(zhǔn)庫(kù)中，std::reverse_iterator 用于實(shí)現(xiàn)類似的功能。

這個(gè)代碼實(shí)現(xiàn)了一個(gè)迭代器適配器。迭代器適配器是一種在現(xiàn)有迭代器基礎(chǔ)上提供不同功能的封裝器，使得原本的迭代器能夠適應(yīng)新的使用場(chǎng)景。

__reverse_iterator 就是一個(gè)逆向迭代器適配器。它封裝了一個(gè)正向迭代器，但通過(guò)重載操作符等方式，使其可以從容器的尾部向頭部進(jìn)行迭代。這樣的適配器能夠讓原本的正向迭代器在逆向遍歷時(shí)更加方便。在下面的list模擬實(shí)現(xiàn)中的反向迭代器函數(shù)需要用到，當(dāng)然它也可以適用于其他容器的模擬實(shí)現(xiàn)，因場(chǎng)景而定，并不是所有容器都可以適用。

list迭代器 __list_iterator定義

迭代器 __list_iterator，用于遍歷鏈表中的節(jié)點(diǎn)。讓我們逐一解釋每個(gè)部分的含義。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    
	typedef list_node<T> Node;  // 定義一個(gè)類型別名 Node，用于表示 list 節(jié)點(diǎn)的類型

	typedef __list_iterator<T, Ref, Ptr> iterator;  // 定義一個(gè)類型別名 iterator，用于表示 list 迭代器的類型

	typedef bidirectional_iterator_tag iterator_category;  // 定義迭代器的分類，這里是雙向迭代器
	
	typedef T value_type;  // 定義元素的類型，即模板參數(shù) T

	typedef Ptr pointer;  // 定義指向元素的指針類型，用于迭代器

	typedef Ref reference;  // 定義對(duì)元素的引用類型，用于迭代器

	typedef ptrdiff_t difference_type;  // 定義表示迭代器之間距離的類型

    Node* _node;  // 指向鏈表中的節(jié)點(diǎn)

    __list_iterator(Node* node)
        :_node(node)  // 初始化迭代器，指向給定的節(jié)點(diǎn)
    {}

    bool operator!=(const iterator& it) const
    {
        return _node != it._node;  // 比較兩個(gè)迭代器是否不相等
    }

    bool operator==(const iterator& it) const
    {
        return _node == it._node;  // 比較兩個(gè)迭代器是否相等
    }

    Ref operator*()
    {
        return _node->_data;  // 返回當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
    }

    Ptr operator->()
    { 
        return &(operator*());  // 返回當(dāng)前節(jié)點(diǎn)數(shù)據(jù)的地址
    }

    // ++it
    iterator& operator++()
    {
        _node = _node->_next;  // 迭代器自增，指向下一個(gè)節(jié)點(diǎn)
        return *this;
    }
    
    // it++
    iterator operator++(int)
    {
        iterator tmp(*this);  // 創(chuàng)建一個(gè)臨時(shí)迭代器保存當(dāng)前迭代器
        _node = _node->_next;  // 迭代器自增，指向下一個(gè)節(jié)點(diǎn)
        return tmp;  // 返回保存的臨時(shí)迭代器
    }

    // --it
    iterator& operator--()
    {
        _node = _node->_prev;  // 迭代器自減，指向前一個(gè)節(jié)點(diǎn)
        return *this;
    }

    // it--
    iterator operator--(int)
    {
        iterator tmp(*this);  // 創(chuàng)建一個(gè)臨時(shí)迭代器保存當(dāng)前迭代器
        _node = _node->_prev;  // 迭代器自減，指向前一個(gè)節(jié)點(diǎn)
        return tmp;  // 返回保存的臨時(shí)迭代器
    }
};

這個(gè)迭代器結(jié)構(gòu)為鏈表提供了遍歷節(jié)點(diǎn)的能力。它可以用于循環(huán)遍歷鏈表的每個(gè)元素，提供了類似于指針的行為，使得遍歷鏈表變得更加方便。

這里提一下迭代器類型的分類：

C++ 標(biāo)準(zhǔn)庫(kù)中的迭代器分為五種主要類型，每種類型提供了不同的功能和支持的操作。這些類型分別是：

輸入迭代器（Input Iterator）：只允許從容器中讀取元素，但不能修改容器內(nèi)的元素。只支持逐個(gè)移動(dòng)、解引用、比較以及比較是否相等等操作。輸入迭代器通常用于算法中，如 std::find()。

輸出迭代器（Output Iterator）：只允許向容器寫入元素，但不能讀取容器內(nèi)的元素。支持逐個(gè)移動(dòng)和逐個(gè)寫入元素等操作。

前向迭代器（Forward Iterator）：類似于輸入迭代器，但支持多次解引用。前向迭代器可以用于一些需要多次迭代的操作，如遍歷一個(gè)單鏈表。

雙向迭代器（Bidirectional Iterator）：在前向迭代器的基礎(chǔ)上，增加了向前遍歷的能力。除了支持輸入迭代器的操作外，還支持向前移動(dòng)和逐個(gè)向前移動(dòng)元素等操作。

隨機(jī)訪問(wèn)迭代器（Random Access Iterator）：是最強(qiáng)大的迭代器類型。除了支持前向迭代器和雙向迭代器的所有操作外，還支持類似指針的算術(shù)操作，如加法、減法，以及隨機(jī)訪問(wèn)容器中的元素。隨機(jī)訪問(wèn)迭代器通常用于數(shù)組等支持隨機(jī)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)中。

在上面的代碼中，typedef bidirectional_iterator_tag iterator_category; 表示這個(gè)迭代器是雙向迭代器類型，因此它應(yīng)該支持前向和雙向迭代器的所有操作，包括移動(dòng)、解引用、比較等。這是為了確保這個(gè)迭代器在遍歷 list 類的容器元素時(shí)能夠正常工作。

list類成員定義

下面的代碼是C++ 中雙向鏈表模板類 list 的類定義部分。這個(gè)類定義了一些公共的成員類型和私有成員變量來(lái)支持鏈表的操作。讓我們逐一解釋每個(gè)部分的含義。

template<class T>
class list
{
    typedef list_node<T> Node;
public:
    // 定義迭代器類型
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;

    typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

private:
    Node* _head;
};

typedef list_node<T> Node;：定義一個(gè)別名 Node，代表鏈表節(jié)點(diǎn)類型 list_node<T>。

typedef __list_iterator<T, T&, T*> iterator;：定義了鏈表的正向迭代器類型 iterator，它使用 __list_iterator 結(jié)構(gòu)模板，并指定了相應(yīng)的參數(shù)類型。

typedef __list_iterator<T, const T&, const T*> const_iterator;：定義了鏈表的常量正向迭代器類型 const_iterator，用于在不修改鏈表元素的情況下遍歷鏈表。

typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;：定義了鏈表的反向迭代器類型 reverse_iterator，這個(gè)迭代器從鏈表末尾向鏈表開頭遍歷。

typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;：定義了鏈表的常量反向迭代器類型 const_reverse_iterator。

Node* _head;：鏈表的私有成員變量，指向鏈表的頭節(jié)點(diǎn)。

這個(gè)部分的代碼定義了 list 類的公共成員類型和私有成員變量，為實(shí)現(xiàn)鏈表的操作和管理提供了基礎(chǔ)。

list成員函數(shù)定義

1.begin()、end()、rbegin()和rend()

const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

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

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

這部分代碼是關(guān)于 list 類的迭代器成員函數(shù)的定義。它們用于返回不同類型的迭代器，使得用戶可以遍歷 list 容器的元素。

const_iterator begin() const: 這是一個(gè)常量成員函數(shù)，返回一個(gè)常量迭代器，它指向容器中的第一個(gè)元素（節(jié)點(diǎn)）。由于是常量迭代器，所以不允許通過(guò)它修改容器內(nèi)的元素。

const_iterator end() const: 這也是一個(gè)常量成員函數(shù)，返回一個(gè)常量迭代器，它指向容器末尾的“尾后”位置，即不存在的元素位置。常量迭代器不能用于修改元素。

iterator begin(): 這是一個(gè)非常量成員函數(shù)，返回一個(gè)非常量迭代器，它指向容器中的第一個(gè)元素（節(jié)點(diǎn)）。允許通過(guò)這個(gè)迭代器修改容器內(nèi)的元素。

iterator end(): 這也是一個(gè)非常量成員函數(shù)，返回一個(gè)非常量迭代器，它指向容器末尾的“尾后”位置，即不存在的元素位置。非常量迭代器可以用于修改元素。

reverse_iterator rbegin(): 這是一個(gè)返回反向迭代器的函數(shù)，它將 end() 的迭代器作為參數(shù)傳遞給 reverse_iterator 構(gòu)造函數(shù)，從而返回一個(gè)指向容器末尾的反向迭代器。

reverse_iterator rend(): 這是一個(gè)返回反向迭代器的函數(shù)，它將 begin() 的迭代器作為參數(shù)傳遞給 reverse_iterator 構(gòu)造函數(shù)，從而返回一個(gè)指向容器開始的反向迭代器。

這些函數(shù)的目的是為了方便用戶在不同情況下遍歷容器元素，包括正向遍歷和反向遍歷，以及使用常量或非常量迭代器。通過(guò)這些迭代器，用戶可以在 list 容器中輕松訪問(wèn)和操作元素。

2.empty_init()

void empty_init()
{
    _head = new Node; // 創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為鏈表頭部
    _head->_next = _head; // 將頭部節(jié)點(diǎn)的下一個(gè)指針指向自身，表示鏈表為空
    _head->_prev = _head; // 將頭部節(jié)點(diǎn)的前一個(gè)指針也指向自身，表示鏈表為空
}

這是 list 類中的一個(gè)私有成員函數(shù) empty_init()，它用于初始化一個(gè)空的鏈表。

該函數(shù)的目的是在創(chuàng)建一個(gè)新的空鏈表時(shí)，為頭部節(jié)點(diǎn) _head 初始化正確的指針，使得鏈表為空。鏈表的頭部節(jié)點(diǎn) _head 用來(lái)標(biāo)識(shí)鏈表的起始位置和結(jié)束位置。

在這個(gè)函數(shù)中，首先通過(guò) new 運(yùn)算符創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為鏈表的頭部。然后，將頭部節(jié)點(diǎn)的 _next 指針和 _prev 指針都指向自身，表示鏈表為空。這種情況下，鏈表的頭部節(jié)點(diǎn)既是首節(jié)點(diǎn)也是尾節(jié)點(diǎn)，形成一個(gè)環(huán)狀的鏈表結(jié)構(gòu)。

在 list 類的構(gòu)造函數(shù)中，通過(guò)調(diào)用 empty_init() 來(lái)創(chuàng)建一個(gè)空鏈表。這在后續(xù)的操作中為鏈表的插入、刪除等操作提供了正確的基礎(chǔ)。

3.構(gòu)造函數(shù)定義

template <class InputIterator>  
list(InputIterator first, InputIterator last)
{
    empty_init(); // 初始化一個(gè)空鏈表

    while (first != last)
    {
        push_back(*first); // 將當(dāng)前迭代器指向的元素添加到鏈表尾部
        ++first; // 移動(dòng)迭代器到下一個(gè)元素
    }
}

list 類的構(gòu)造函數(shù)模板，它接受一個(gè)范圍內(nèi)的元素，并將這些元素添加到鏈表中。
這個(gè)構(gòu)造函數(shù)使用了一個(gè)模板參數(shù) InputIterator，它表示輸入迭代器的類型。這樣，構(gòu)造函數(shù)可以接受不同類型的迭代器，例如普通指針、list 的迭代器等。

在構(gòu)造函數(shù)中，首先調(diào)用 empty_init() 函數(shù)來(lái)初始化一個(gè)空鏈表，確保鏈表頭部的 _head 節(jié)點(diǎn)正確初始化。

然后，使用一個(gè)循環(huán)遍歷輸入迭代器范圍內(nèi)的元素。在每次循環(huán)中，通過(guò) push_back() 函數(shù)將當(dāng)前迭代器指向的元素添加到鏈表的尾部。之后，將迭代器向前移動(dòng)一個(gè)位置，以便處理下一個(gè)元素。

list()
{
    empty_init(); // 初始化一個(gè)空鏈表
}

這是 list 類的無(wú)參構(gòu)造函數(shù)，它用于創(chuàng)建一個(gè)空的鏈表。

這個(gè)構(gòu)造函數(shù)不接受任何參數(shù)，它只是在對(duì)象創(chuàng)建時(shí)將 _head 節(jié)點(diǎn)初始化為一個(gè)空鏈表。調(diào)用 empty_init() 函數(shù)會(huì)創(chuàng)建一個(gè)只包含 _head 節(jié)點(diǎn)的鏈表，該節(jié)點(diǎn)的 _next 和 _prev 都指向自身，表示鏈表為空。

list(const list<T>& lt)
{
    empty_init(); // 初始化一個(gè)空鏈表

    list<T> tmp(lt.begin(), lt.end()); // 使用迭代器從 lt 創(chuàng)建一個(gè)臨時(shí)鏈表
    swap(tmp); // 交換臨時(shí)鏈表和當(dāng)前鏈表，完成拷貝操作
}

這是 list 類的拷貝構(gòu)造函數(shù)，它用于創(chuàng)建一個(gè)新鏈表，該鏈表與另一個(gè)已存在的鏈表 lt 相同

在這個(gè)構(gòu)造函數(shù)中，首先通過(guò)調(diào)用 empty_init() 函數(shù)初始化了一個(gè)空鏈表，然后創(chuàng)建了一個(gè)臨時(shí)鏈表 tmp，這個(gè)臨時(shí)鏈表的元素和鏈表 lt 中的元素相同，通過(guò)迭代器從 lt 范圍內(nèi)創(chuàng)建。接著，通過(guò)調(diào)用 swap() 函數(shù)將當(dāng)前鏈表與臨時(shí)鏈表 tmp 交換，從而實(shí)現(xiàn)了鏈表的拷貝。

這種方式能夠?qū)崿F(xiàn)拷貝構(gòu)造的效果，因?yàn)樵?swap() 函數(shù)中，臨時(shí)鏈表 tmp 的資源會(huì)交給當(dāng)前鏈表，而臨時(shí)鏈表 tmp 會(huì)被銷毀，從而實(shí)現(xiàn)了鏈表內(nèi)容的拷貝。

4.swap

void swap(list<T>& x)
{
    std::swap(_head, x._head); // 交換兩個(gè)鏈表的頭結(jié)點(diǎn)指針
}

這是 list 類的成員函數(shù) swap，它用于交換兩個(gè)鏈表的內(nèi)容。

在這個(gè)函數(shù)中，通過(guò)調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù) std::swap，將當(dāng)前鏈表的頭結(jié)點(diǎn)指針 _head 與另一個(gè)鏈表 x 的頭結(jié)點(diǎn)指針 _head 進(jìn)行交換。這個(gè)操作會(huì)導(dǎo)致兩個(gè)鏈表的內(nèi)容被互相交換，但是實(shí)際上并沒有復(fù)制鏈表中的元素，只是交換了鏈表的結(jié)構(gòu)。

這種交換操作通常在需要交換兩個(gè)對(duì)象的內(nèi)容時(shí)使用，它可以在不復(fù)制數(shù)據(jù)的情況下實(shí)現(xiàn)兩個(gè)對(duì)象之間的內(nèi)容互換，從而提高了效率。

需要注意的是，這個(gè)函數(shù)只是交換了鏈表的頭結(jié)點(diǎn)指針，而鏈表中的元素順序沒有改變。

5.析構(gòu)函數(shù)定義

~list()
{
    clear();         // 清空鏈表中的所有元素
    delete _head;    // 刪除頭結(jié)點(diǎn)
    _head = nullptr; // 將頭結(jié)點(diǎn)指針置為空指針
}

這是 list 類的析構(gòu)函數(shù)，用于銷毀鏈表對(duì)象。

在這個(gè)析構(gòu)函數(shù)中，首先調(diào)用了成員函數(shù) clear() 來(lái)清空鏈表中的所有元素，確保在刪除鏈表之前釋放所有資源。然后，使用 delete 關(guān)鍵字釋放頭結(jié)點(diǎn)的內(nèi)存。最后，將頭結(jié)點(diǎn)指針 _head 置為空指針，以避免出現(xiàn)野指針。

這樣，在鏈表對(duì)象被銷毀時(shí)，它所占用的內(nèi)存將會(huì)被正確地釋放，從而防止內(nèi)存泄漏。

6.clear()

void clear()
{
    iterator it = begin(); // 獲取鏈表的起始迭代器
    while (it != end())    // 遍歷鏈表
    {
        it = erase(it);    // 使用 erase() 函數(shù)刪除當(dāng)前元素，并將迭代器指向下一個(gè)元素
    }
}

這是 list 類的 clear() 成員函數(shù)，用于清空鏈表中的所有元素。

在這個(gè)函數(shù)中，首先獲取鏈表的起始迭代器 begin()，然后通過(guò)一個(gè)循環(huán)遍歷鏈表中的所有元素。在循環(huán)內(nèi)部，調(diào)用了 erase() 函數(shù)來(lái)刪除當(dāng)前迭代器指向的元素，并將迭代器更新為指向被刪除元素的下一個(gè)元素。這樣可以確保鏈表中的所有元素都被逐個(gè)刪除。

需要注意的是，erase() 函數(shù)在刪除元素后會(huì)返回指向下一個(gè)元素的迭代器，因此在每次循環(huán)迭代時(shí)更新迭代器是必要的，以便繼續(xù)正確地遍歷鏈表。

總之，這個(gè) clear() 函數(shù)用于釋放鏈表中的所有元素，并確保鏈表變?yōu)榭真湵怼?/p>

7.push_back

void push_back(const T& x)
{
    Node* tail = _head->_prev; // 獲取當(dāng)前鏈表的末尾節(jié)點(diǎn)
    Node* newnode = new Node(x); // 創(chuàng)建一個(gè)新節(jié)點(diǎn)，保存新元素 x

    tail->_next = newnode; // 更新末尾節(jié)點(diǎn)的下一個(gè)指針，指向新節(jié)點(diǎn)
    newnode->_prev = tail; // 新節(jié)點(diǎn)的前一個(gè)指針指向原末尾節(jié)點(diǎn)
    newnode->_next = _head; // 新節(jié)點(diǎn)的下一個(gè)指針指向頭節(jié)點(diǎn)
    _head->_prev = newnode; // 頭節(jié)點(diǎn)的前一個(gè)指針指向新節(jié)點(diǎn)，完成插入操作
}

這是 list 類的 push_back() 成員函數(shù)，用于在鏈表的末尾添加一個(gè)新元素。

在這個(gè)函數(shù)中，首先獲取當(dāng)前鏈表的末尾節(jié)點(diǎn)（尾節(jié)點(diǎn)的 _prev 指向鏈表的最后一個(gè)元素），然后創(chuàng)建一個(gè)新的節(jié)點(diǎn) newnode，并將新元素 x 存儲(chǔ)在新節(jié)點(diǎn)中。接著，更新末尾節(jié)點(diǎn)的 _next 指針，使其指向新節(jié)點(diǎn)，然后更新新節(jié)點(diǎn)的 _prev 指針，使其指向原末尾節(jié)點(diǎn)。同時(shí)，將新節(jié)點(diǎn)的 _next 指針指向頭節(jié)點(diǎn)，完成循環(huán)鏈表的連接。最后，更新頭節(jié)點(diǎn)的 _prev 指針，使其指向新節(jié)點(diǎn)，確保鏈表的連接是完整的。

需要注意的是，這個(gè)函數(shù)在鏈表末尾添加了一個(gè)新元素，不影響其他元素的相對(duì)位置。

8.push_front

void push_front(const T& x)
{
    insert(begin(), x); // 調(diào)用 insert 函數(shù)，在頭部插入新元素 x
}

這個(gè)函數(shù)簡(jiǎn)單地調(diào)用了 insert 函數(shù)，將新元素 x 插入到鏈表的頭部。

9.insert

iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node; // 獲取當(dāng)前位置的節(jié)點(diǎn)
    Node* prev = cur->_prev; // 獲取當(dāng)前位置節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

    Node* newnode = new Node(x); // 創(chuàng)建一個(gè)新節(jié)點(diǎn)，保存新元素 x

    prev->_next = newnode; // 更新前一個(gè)節(jié)點(diǎn)的下一個(gè)指針，指向新節(jié)點(diǎn)
    newnode->_prev = prev; // 新節(jié)點(diǎn)的前一個(gè)指針指向前一個(gè)節(jié)點(diǎn)
    newnode->_next = cur; // 新節(jié)點(diǎn)的下一個(gè)指針指向當(dāng)前位置節(jié)點(diǎn)
    cur->_prev = newnode; // 當(dāng)前位置節(jié)點(diǎn)的前一個(gè)指針指向新節(jié)點(diǎn)，完成插入操作

    return iterator(newnode); // 返回指向新節(jié)點(diǎn)的迭代器
}

在 insert 函數(shù)中，首先獲取當(dāng)前位置節(jié)點(diǎn) pos 和其前一個(gè)節(jié)點(diǎn) prev，然后創(chuàng)建一個(gè)新節(jié)點(diǎn) newnode 并將新元素 x 存儲(chǔ)在新節(jié)點(diǎn)中。接著，更新前一個(gè)節(jié)點(diǎn)的 _next 指針，使其指向新節(jié)點(diǎn)，然后更新新節(jié)點(diǎn)的 _prev 指針，使其指向前一個(gè)節(jié)點(diǎn)。同時(shí)，將新節(jié)點(diǎn)的 _next 指針指向當(dāng)前位置節(jié)點(diǎn) cur，完成插入操作。最后，更新當(dāng)前位置節(jié)點(diǎn)的 _prev 指針，使其指向新節(jié)點(diǎn)，確保鏈表的連接是完整的。最后，函數(shù)返回一個(gè)指向新節(jié)點(diǎn)的迭代器，表示插入操作完成后的位置。

10.erase

iterator erase(iterator pos)
{
    assert(pos != end()); // 斷言：確保 pos 不等于鏈表的結(jié)束迭代器

    Node* cur = pos._node; // 獲取當(dāng)前位置的節(jié)點(diǎn)
    Node* prev = cur->_prev; // 獲取當(dāng)前位置節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    Node* next = cur->_next; // 獲取當(dāng)前位置節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)

    prev->_next = next; // 更新前一個(gè)節(jié)點(diǎn)的下一個(gè)指針，指向后一個(gè)節(jié)點(diǎn)
    next->_prev = prev; // 更新后一個(gè)節(jié)點(diǎn)的前一個(gè)指針，指向前一個(gè)節(jié)點(diǎn)
    delete cur; // 刪除當(dāng)前位置的節(jié)點(diǎn)

    return iterator(next); // 返回指向后一個(gè)節(jié)點(diǎn)的迭代器，表示刪除操作完成后的位置
}

這部分代碼實(shí)現(xiàn)了從鏈表中刪除指定位置元素的功能。

在 erase 函數(shù)中，首先使用斷言來(lái)確保刪除位置 pos 不是鏈表的結(jié)束迭代器。然后，獲取當(dāng)前位置節(jié)點(diǎn) pos、其前一個(gè)節(jié)點(diǎn) prev 和后一個(gè)節(jié)點(diǎn) next。接著，更新前一個(gè)節(jié)點(diǎn)的 _next 指針，使其指向后一個(gè)節(jié)點(diǎn)，同時(shí)更新后一個(gè)節(jié)點(diǎn)的 _prev 指針，使其指向前一個(gè)節(jié)點(diǎn)。這樣，當(dāng)前位置節(jié)點(diǎn)就從鏈表中斷開了。最后，釋放當(dāng)前位置節(jié)點(diǎn)的內(nèi)存空間，并返回一個(gè)指向后一個(gè)節(jié)點(diǎn)的迭代器，表示刪除操作完成后的位置。

11.pop_back()和pop_front()

void pop_back()
{
    erase(--end()); // 通過(guò) erase 函數(shù)刪除鏈表末尾的元素
}

pop_back 函數(shù)通過(guò)將鏈表的結(jié)束迭代器向前移動(dòng)一個(gè)位置，然后調(diào)用 erase 函數(shù)來(lái)刪除該位置的元素，實(shí)現(xiàn)了從鏈表末尾刪除一個(gè)元素的操作。

void pop_front()
{
    erase(begin()); // 通過(guò) erase 函數(shù)刪除鏈表頭部的元素
}

pop_front 函數(shù)直接調(diào)用 erase 函數(shù)，刪除鏈表頭部的元素，實(shí)現(xiàn)了從鏈表頭部刪除一個(gè)元素的操作。

這兩個(gè)函數(shù)分別對(duì)應(yīng)于從鏈表的末尾和頭部刪除元素的操作，通過(guò)調(diào)用 erase 函數(shù)來(lái)完成刪除操作，從而保持了鏈表的連接性。

12.empty()、size()、front()和back()

bool list<T>::empty() const
{
    return begin() == end(); // 判斷 begin() 是否等于 end() 來(lái)確定是否為空
}

typename list<T>::size_t list<T>::size() const
{
    size_t count = 0;
    for (const_iterator it = begin(); it != end(); ++it)
    {
        ++count;
    }
    return count; // 遍歷鏈表來(lái)計(jì)算元素個(gè)數(shù)
}

typename list<T>::reference list<T>::front()
{
    assert(!empty()); // 如果鏈表為空，則拋出斷言
    return *begin(); // 返回鏈表的第一個(gè)元素
}

typename list<T>::const_reference list<T>::front() const
{
    assert(!empty()); // 如果鏈表為空，則拋出斷言
    return *begin(); // 返回鏈表的第一個(gè)元素
}

typename list<T>::reference list<T>::back()
{
    assert(!empty()); // 如果鏈表為空，則拋出斷言
    return *(--end()); // 返回鏈表的最后一個(gè)元素
}

typename list<T>::const_reference list<T>::back() const
{
    assert(!empty()); // 如果鏈表為空，則拋出斷言
    return *(--end()); // 返回鏈表的最后一個(gè)元素
}

上述代碼實(shí)現(xiàn)了 empty() 函數(shù)用于判斷鏈表是否為空，size() 函數(shù)用于獲取鏈表元素個(gè)數(shù)，front() 函數(shù)用于獲取鏈表第一個(gè)元素，以及 back() 函數(shù)用于獲取鏈表最后一個(gè)元素。注意函數(shù)中的斷言用于確保在鏈表為空時(shí)不執(zhí)行非法操作。

13.resize

template<class T>
void list<T>::resize(size_t n, const T& val)
{
    if (n < size()) {
        iterator it = begin();
        std::advance(it, n); // 定位到新的尾部位置
        while (it != end()) {
            it = erase(it); // 從尾部截?cái)?，刪除多余的元素
        }
    }
    else if (n > size()) {
        insert(end(), n - size(), val); // 插入足夠數(shù)量的默認(rèn)值元素
    }
}

如果 n 小于當(dāng)前鏈表的大小size()，意味著你想要縮小鏈表的大小。在這種情況下，函數(shù)會(huì)迭代遍歷鏈表，從尾部開始刪除多余的元素，直到鏈表的大小等于 n。

首先，函數(shù)會(huì)使用 begin() 獲取鏈表的起始迭代器，然后使用 std::advance 函數(shù)將迭代器向前移動(dòng) n 個(gè)位置，使其指向新的尾部位置。

接下來(lái)，函數(shù)使用 erase 函數(shù)將從新尾部位置到鏈表末尾的所有元素刪除，從而使鏈表的大小減小到 n。

如果 n 大于當(dāng)前鏈表的大小，表示你想要增大鏈表的大小。在這種情況下，函數(shù)會(huì)插入足夠數(shù)量的值為 val 的元素到鏈表的末尾，直到鏈表的大小等于 n。

函數(shù)會(huì)使用 insert 函數(shù)在鏈表的末尾插入 n - size() 個(gè)值為 val 的元素，從而使鏈表的大小增大到 n。

14.賦值運(yùn)算符重載

list<T>& operator=(list<T> lt)
{
    swap(lt); // 交換當(dāng)前對(duì)象和傳入對(duì)象的內(nèi)容
    return *this; // 返回當(dāng)前對(duì)象的引用
}

這是一個(gè)賦值運(yùn)算符重載函數(shù)，它采用了拷貝并交換（Copy and Swap）的技巧來(lái)實(shí)現(xiàn)賦值操作。

這是一個(gè)成員函數(shù)，用于將一個(gè) list<T> 類型的對(duì)象賦值給當(dāng)前的對(duì)象。
參數(shù) lt 是通過(guò)值傳遞的，所以會(huì)調(diào)用 list<T> 的拷貝構(gòu)造函數(shù)創(chuàng)建一個(gè)臨時(shí)副本。
然后，通過(guò) swap(lt) 調(diào)用 swap 函數(shù)來(lái)交換當(dāng)前對(duì)象和臨時(shí)副本的內(nèi)容。在交換后，臨時(shí)副本的數(shù)據(jù)會(huì)被賦值給當(dāng)前對(duì)象，而臨時(shí)副本會(huì)被銷毀。由于交換是高效的操作，可以避免大量的數(shù)據(jù)復(fù)制。
最后，函數(shù)返回當(dāng)前對(duì)象的引用，以支持連續(xù)賦值操作。
這種方式不僅避免了手動(dòng)管理內(nèi)存的麻煩，還確保了異常安全，因?yàn)榕R時(shí)副本在函數(shù)結(jié)束時(shí)會(huì)被正確銷毀。

list模擬實(shí)現(xiàn)全部代碼

#pragma once

#include <assert.h>
#include <iostream>

namespace xzq
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;

		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef ptrdiff_t difference_type;


		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

		bool operator!=(const iterator& it) const
		{
			return _node != it._node;
		}

		bool operator==(const iterator& it) const
		{
			return _node == it._node;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{ 
			return &(operator*());
		}

		// ++it
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		
		// it++
		iterator operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		// --it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// it--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
	};

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;


		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

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

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		template <class InputIterator>  
		list(InputIterator first, InputIterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list()
		{
			empty_init();
		}

		void swap(list<T>& x)
		{
			std::swap(_head, x._head);
		}
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

			//insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			Node* newnode = new Node(x);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

		bool list<T>::empty() const
		{
			return begin() == end(); // 判斷 begin() 是否等于 end() 來(lái)確定是否為空
		}

		typename list<T>::size_t list<T>::size() const
		{
			size_t count = 0;
			for (const_iterator it = begin(); it != end(); ++it)
			{
				++count;
			}
			return count; // 遍歷鏈表來(lái)計(jì)算元素個(gè)數(shù)
		}

		typename list<T>::reference list<T>::front()
		{
			assert(!empty()); // 如果鏈表為空，則拋出斷言
			return *begin(); // 返回鏈表的第一個(gè)元素
		}

		typename list<T>::const_reference list<T>::front() const
		{
			assert(!empty()); // 如果鏈表為空，則拋出斷言
			return *begin(); // 返回鏈表的第一個(gè)元素
		}

		typename list<T>::reference list<T>::back()
		{
			assert(!empty()); // 如果鏈表為空，則拋出斷言
			return *(--end()); // 返回鏈表的最后一個(gè)元素
		}

		typename list<T>::const_reference list<T>::back() const
		{
			assert(!empty()); // 如果鏈表為空，則拋出斷言
			return *(--end()); // 返回鏈表的最后一個(gè)元素
		}
		void resize(size_t n, const T& val = T())
		{
			if (n < size()) {
				iterator it = begin();
				std::advance(it, n);
				while (it != end()) {
					it = erase(it); // 從尾部截?cái)?，刪除多余的元素
				}
			}
			else if (n > size()) {
				insert(end(), n - size(), val); // 插入足夠數(shù)量的默認(rèn)值元素
			}
		}
	private:
		Node* _head;
	};
}

list 和 vector的區(qū)別

通過(guò)模擬實(shí)現(xiàn) list 和 vector，你可以更好地理解它們之間的區(qū)別和特點(diǎn)。這兩者是 C++ 標(biāo)準(zhǔn)庫(kù)中的序列式容器，但它們?cè)趦?nèi)部實(shí)現(xiàn)和使用場(chǎng)景上有很大的區(qū)別。

底層實(shí)現(xiàn)：

list 通常是一個(gè)雙向鏈表，每個(gè)節(jié)點(diǎn)都包含了數(shù)據(jù)和指向前一個(gè)和后一個(gè)節(jié)點(diǎn)的指針。這使得在任何位置進(jìn)行插入和刪除操作都是高效的，但隨機(jī)訪問(wèn)和內(nèi)存占用可能相對(duì)較差。
vector 是一個(gè)動(dòng)態(tài)數(shù)組，元素在內(nèi)存中是連續(xù)存儲(chǔ)的。這使得隨機(jī)訪問(wèn)非常高效，但插入和刪除操作可能需要移動(dòng)大量的元素，效率較低。

插入和刪除操作：

在 list 中，插入和刪除操作是高效的，無(wú)論是在容器的任何位置還是在開頭和結(jié)尾。這使得 list 在需要頻繁插入和刪除操作時(shí)非常適用。
在 vector 中，插入和刪除操作可能需要移動(dòng)元素，特別是在容器的中間或開頭。因此，當(dāng)涉及大量插入和刪除操作時(shí)，vector 可能不如 list 效率高。

隨機(jī)訪問(wèn)：

list 不支持隨機(jī)訪問(wèn)，即不能通過(guò)索引直接訪問(wèn)元素，必須通過(guò)迭代器逐個(gè)遍歷。
vector 支持隨機(jī)訪問(wèn)，可以通過(guò)索引快速訪問(wèn)元素，具有良好的隨機(jī)訪問(wèn)性能。

內(nèi)存占用：

由于 list 使用鏈表存儲(chǔ)元素，每個(gè)節(jié)點(diǎn)都需要額外的指針來(lái)指向前后節(jié)點(diǎn)，可能會(huì)導(dǎo)致更多的內(nèi)存占用。
vector 在內(nèi)存中是連續(xù)存儲(chǔ)的，通常占用的內(nèi)存較少。

迭代器失效：

在 list 中，插入和刪除操作不會(huì)導(dǎo)致迭代器失效，因?yàn)楣?jié)點(diǎn)之間的關(guān)系不會(huì)改變。
在 vector 中，插入和刪除操作可能導(dǎo)致內(nèi)存重新分配，從而使原來(lái)的迭代器失效。

綜上所述，如果你需要頻繁進(jìn)行插入和刪除操作，而對(duì)于隨機(jī)訪問(wèn)性能沒有特別高的要求，那么使用 list 是一個(gè)不錯(cuò)的選擇。而如果你更注重隨機(jī)訪問(wèn)性能，可以選擇使用 vector。當(dāng)然，在實(shí)際開發(fā)中，還需要根據(jù)具體情況權(quán)衡使用哪種容器。

結(jié)語(yǔ)

有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯(cuò)，請(qǐng)給個(gè)一鍵三連吧，蟹蟹你喲?。?！
制作不易，如有不正之處敬請(qǐng)指出
感謝大家的來(lái)訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力
在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！
（創(chuàng)作128天紀(jì)念日，暫時(shí)還沒有想好怎么分享，下次再寫嘍）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-652119.html

到了這里，關(guān)于C++初階之一篇文章教會(huì)你list（模擬實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！