結點類的模擬實現

list是一個帶頭雙向循環鏈表

因需要實現一個節點類，其中包含哨兵位（用來標識位置），節點信息（val數據，prev后指針，next后指針）

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){}
};

知識點：構造函數

• 在后面要new開空間，需要構造分為要帶參和不帶的?--》全缺省 T()給個缺省值應對不同類型
• 為什么用struct--》當類中全部都是公有，一般用struct （其實和class沒什么區別）

迭代器類的模擬實現

模擬迭代器的意義

之前模擬實現string和vector時都沒有說要實現一個迭代器類，為什么實現list的時候就需要實現一個迭代器類了呢？

string和vector

因為string和vector對象都將其數據存儲在了一塊連續的內存空間，我們通過指針進行自增、自減以及解引用等操作，就可以對相應位置的數據進行一系列操作，因此string和vector當中的迭代器就是原生指針。

list?

list來說，其各個結點在內存當中的位置是隨機的，并不是連續的，我們不能僅通過結點指針的自增、自減以及解引用等操作對相應結點的數據進行操作。

?

總結： list迭代器類，實際上就是對結點指針進行了封裝，對其各種運算符進行了重載。?

?普通迭代器

構造函數

// 構造函數，接收一個節點指針，用于初始化迭代器，使其指向傳入的節點list_iterator(Node* node) :_node(node) {} 

前置 ++ 運算符重載（operator++()?）

前置 ++ 原本的作用是將數據自增，然后返回自增后的數據。對于鏈表迭代器的前置 ++，目的是讓迭代器指向下一個節點并返回修改后的迭代器自身。

// 前置++
Self& operator++() 
{_node = _node->_next; // 讓結點指針指向下一個結點return *this; // 返回自增后的迭代器自身引用
}

此函數先讓迭代器指向的節點指針移動到下一個節點，再返回修改后的迭代器自身引用。

前置 -- 運算符重載（operator--()?）

前置 -- 原本的作用是將數據自減，然后返回自減后的數據。對于鏈表迭代器的前置 --，要讓迭代器指向前一個節點并返回修改后的迭代器自身。

// 前置--
Self& operator--() 
{_node = _node->_prev; // 讓結點指針指向前一個結點return *this; // 返回自減后的迭代器自身引用
}

該函數讓迭代器的節點指針移動到前一個節點，再返回移動后的迭代器自身引用。

后置 ++ 運算符重載（operator++(int)?）

后置 ++ 原本是先返回數據原來的值，然后再將數據自增。對于鏈表迭代器的后置 ++，需先記錄當前迭代器狀態，再讓迭代器移動到下一個節點，最后返回原始狀態的迭代器。

// 后置++
Self operator++(int) 
{Self tmp(*this); // 記錄當前結點指針的指向，也就是記錄迭代器當前狀態_node = _node->_next; // 讓結點指針指向下一個結點return tmp; // 返回自增前的迭代器，即記錄的原始狀態的迭代器
}

函數先保存迭代器原始狀態，再使其移動到下一個節點，最后返回原始迭代器。

知識點：C++ 規定后置自減運算符重載函數需要帶一個 int 類型的參數，這個參數在函數實現中通常不會被使用，它僅僅是作為一個標記，用于編譯器區分前置和后置運算符。 ?

后置 -- 運算符重載（operator--(int)?）

后置 -- 原本是先返回數據原來的值，然后再將數據自減。對于鏈表迭代器的后置 --，要先記錄當前迭代器狀態，再讓迭代器移動到前一個節點，最后返回原始狀態的迭代器。

// 后置--
Self operator--(int) 
{Self tmp(*this); // 記錄當前結點指針的指向，即記錄迭代器當前狀態_node = _node->_prev; // 讓結點指針指向前一個結點return tmp; // 返回自減前的迭代器，即記錄的原始狀態的迭代器
}

此函數先保存迭代器當前狀態，再讓其指向前一個節點，最后返回原始迭代器。

解引用運算符重載（operator*()?）

解引用運算符?*?原本用于獲取指針所指向的數據。對于鏈表迭代器的?*?運算符重載，目的是獲取當前所指向節點存儲的數據的引用，以便讀寫。

// 解引用運算符重載
T& operator*() 
{return _node->_data; // 返回當前節點存儲的數據的引用
}

該函數返回當前節點中存儲的數據的引用。

箭頭運算符重載（operator->()?）

箭頭運算符?->?通常用于通過指針訪問結構體或類的成員。對于鏈表迭代器的?->?運算符重載，是為了方便訪問當前所指向節點存儲數據的成員。

// 箭頭運算符重載
T* operator->() 
{return &_node->_data; // 返回當前節點存儲數據的指針
}

函數返回當前節點存儲數據的指針，可使用?迭代器->成員?訪問節點數據成員。

不等于運算符重載（operator!=()?）

不等于運算符?!=?用于判斷兩個對象是否不相等。對于鏈表迭代器的?!=?運算符重載，是為了判斷兩個迭代器是否指向不同的節點。

// 不等于運算符重載
bool operator!=(const Self& s) 
{return _node != s._node; // 判斷當前迭代器和傳入迭代器所指向的節點是否不同
}

此函數比較兩個迭代器所指向的節點指針是否不同，不同則返回?true。

const迭代器

const迭代器與普通不同點在于要單獨實現個類（const 迭代器負責只讀遍歷）并且在類中的 *， -> 的返回值和其他的不同

• 普通迭代器：可讀可寫，通過重載的?operator*?和?operator->?返回值無?const?修飾，能修改指向的 list 元素 。比如?*it = newValue;（it?為普通迭代器）可修改元素值。

• const 迭代器：只讀，?operator*?返回?const T&?，operator->?返回?const T*?，禁止通過迭代器修改 list 元素。若?*it = newValue;（it?為 const 迭代器），編譯器會報錯。

• const 迭代器指向的內容不能改變 所以要模擬前置const

?普通類和const類結合

先看編譯器底層

這里我們所實現的迭代器類的模板參數列表當中為什么有三個模板參數？

template<class T, class Ref, class Ptr>

普通迭代器和const迭代器。

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

這里我們就可以看出，迭代器類的模板參數列表當中的Ref和Ptr分別代表的是引用類型和指針類型。

當我們使用普通迭代器時，編譯器就會實例化出一個普通迭代器對象；當我們使用const迭代器時，編譯器就會實例化出一個const迭代器對象。

// 定義普通迭代器類型
// 這里使用了模板參數T，將list_iterator類模板實例化為普通迭代器，Ref為T&，Ptr為T*，意味著可以對元素進行讀寫操作
typedef list_iterator<T, T&, T*> iterator;
// 定義常量迭代器類型
// 同樣使用模板參數T，但Ref為const T&，Ptr為const T*，表示只能對元素進行只讀操作
typedef list_iterator<T, const T&, const T*> const_iterator;// 定義list_iterator類模板，包含三個模板參數
// T 表示鏈表中存儲的數據類型
// Ref 表示引用類型，用于operator*返回值的類型，普通迭代器時為T&，常量迭代器時為const T&
// Ptr 表示指針類型，用于operator->返回值的類型，普通迭代器時為T*，常量迭代器時為const T*
template<class T, class Ref, class Ptr>
struct list_iterator
{// 定義Node類型為list_node<T>，方便后續使用，list_node<T>應該是鏈表節點的類型typedef list_node<T> Node;// 定義Self類型為list_iterator<T, Ref, Ptr>，方便在類內使用自身類型typedef list_iterator<T, Ref, Ptr> Self;// 指向鏈表節點的指針，用于存儲迭代器當前指向的節點Node* _node;// 構造函數，接收一個節點指針，用于初始化迭代器，使其指向傳入的節點list_iterator(Node* node):_node(node){}// 重載*運算符，返回當前節點存儲的數據的引用// 返回值類型為Ref，根據模板參數不同，普通迭代器時為T&，常量迭代器時為const T&Ref operator*(){return _node->_data;}// 重載->運算符，返回當前節點存儲數據的指針// 返回值類型為Ptr，根據模板參數不同，普通迭代器時為T*，常量迭代器時為const T*Ptr operator->(){return &_node->_data;}// 重載前置++運算符，將迭代器指向下一個節點，并返回修改后的迭代器自身引用Self& operator++(){_node = _node->_next;return *this;}// 重載前置--運算符，將迭代器指向前一個節點，并返回修改后的迭代器自身引用Self& operator--(){_node = _node->_prev;return *this;}// 重載后置++運算符，先保存當前迭代器狀態，然后將迭代器指向下一個節點，最后返回保存的原始迭代器Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}// 重載后置--運算符，先保存當前迭代器狀態，然后將迭代器指向前一個節點，最后返回保存的原始迭代器Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 重載!=運算符，用于比較兩個迭代器是否指向不同的節點// 返回true表示兩個迭代器指向不同節點，否則返回falsebool operator!=(const Self& s){return _node != s._node;} // 重載==運算符，用于比較兩個迭代器是否指向相同的節點// 返回true表示兩個迭代器指向相同節點，否則返回falsebool operator==(const Self& s){return _node == s._node;}
};

知識點：對于->

當list容器當中的每個結點存儲的不是內置類型，而是自定義類型，例如日期類，那么當我們拿到一個位置的迭代器時，我們可能會使用->運算符訪問Date的成員：

	list<Date> lt;Date d1(2021, 8, 10);Date d2(1980, 4, 3);Date d3(1931, 6, 29);lt.push_back(d1);lt.push_back(d2);lt.push_back(d3);list<Date>::iterator pos = lt.begin();cout << pos->_year << endl; //輸出第一個日期的年份
//相當于cout << pos.operator->()->_year << endl;

對于->運算符的重載，我們直接返回結點當中所存儲數據的地址即可。

從邏輯上，原本應該是先調用重載的?operator->?得到自定義類型（如?Date?）的指針?pd?，然后再用這個指針?pd?去訪問成員變量，即?pd->year?，也就是理論上會出現?pos->->year?這種形式 。但 C++ 語法規定，當重載了?->?運算符返回一個指針后，編譯器會自動處理，使得我們可以直接寫?pos->year?，省略掉第二個?->?，編譯器會根據重載規則理解為先用?pos->?調用重載函數得到指針，再用指針訪問成員 。

?

默認成員函數

• 構造函數

list 是一個帶頭雙向循環鏈表。在構造一個 list 對象時，直接申請一個頭結點，并讓其前驅指針和后繼指針都指向自己。這樣就構建好了一個空鏈表的初始結構。

// 構造函數
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}

• 拷貝構造函數

拷貝構造函數的作用是根據所給 list 容器，構造出一個新對象。首先申請一個頭結點并完成初始化，然后遍歷原容器，將其中的數據逐個尾插到新構造的容器中。

// 拷貝構造函數
list(const list<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto it = lt.begin(); it != lt.end(); ++it){push_back(*it);}
}

1. 賦值運算符重載函數

• 寫法一：傳統寫法
  先調用 clear 函數將原容器清空，避免殘留數據干擾。然后遍歷傳入容器，將其中的數據逐個尾插到清空后的容器中，實現賦值操作。

// 傳統寫法
list<T>& operator=(const list<T>& lt)
{if (this != &lt){clear();for (auto it = lt.begin(); it != lt.end(); ++it){push_back(*it);}}return *this;
}

• 寫法二：現代寫法
  利用編譯器機制，故意不使用引用接收參數，讓編譯器自動調用拷貝構造函數構造出一個臨時 list 對象。然后調用 swap 函數將原容器與該臨時對象進行交換，實現高效賦值。

// 現代寫法
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

析構函數
對象析構時，先調用 clear 函數清理容器中的數據，釋放所有有效節點。接著釋放頭結點，最后將頭指針置空，完成資源的徹底釋放。

// 析構函數
~list()
{clear();delete _head;_head = nullptr;
}

迭代器相關函數

begin 和 end

• 對于普通 list 對象：
  begin 函數返回第一個有效數據的迭代器，即使用頭結點后一個結點的地址構造出來的迭代器；end 函數返回最后一個有效數據的下一個位置的迭代器，也就是頭結點地址構造的迭代器。

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

• 對于 const list 對象：
  重載 const 版本的 begin 和 end 函數，返回 const 迭代器，保證在遍歷 const 對象時不能修改數據。

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

訪問容器相關函數

front 和 back

對于普通 list 對象：
front 函數返回第一個有效數據的引用，通過解引用 begin 函數返回的迭代器實現；back 函數返回最后一個有效數據的引用，通過先將 end 函數返回的迭代器前置遞減，再解引用實現。

T& front()
{return *begin();
}
T& back()
{return *(--end());
}

• 對于 const list 對象：
  重載 const 版本的 front 和 back 函數，返回 const 引用，防止通過這些函數修改 const 對象中的數據。

const T& front() const
{return *begin();
}
const T& back() const
{return *(--end());
}

插入、刪除函數

insert

insert 函數可以在所給迭代器之前插入一個新結點。先根據迭代器得到對應位置的結點指針 cur，再找到 cur 的前驅結點指針 prev，根據給定數據構造待插入結點 newnode，然后建立 newnode 與 cur、prev 之間的雙向鏈接關系。

iterator insert(iterator pos, const T& x)
{assert(pos._node);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);
}

?

erase

erase 函數用于刪除所給迭代器位置的結點。先根據迭代器得到對應位置的結點指針 cur，以及其前驅結點指針 prev 和后繼結點指針 next，釋放 cur 結點，再建立 prev 和 next 之間的雙向鏈接關系，最后返回刪除位置的下一個迭代器。

// erase函數
// 功能：刪除所給迭代器pos位置的結點
// 參數：iterator pos，指定要刪除結點位置的迭代器
// 返回值：iterator，返回指向刪除位置下一個結點的迭代器
iterator erase(iterator pos)
{// 確保迭代器pos有效assert(pos._node);// 確保要刪除的不是end迭代器指向的位置（頭結點）assert(pos != end());// 獲取迭代器pos指向的結點指針Node* cur = pos._node;// 獲取cur結點的前驅結點指針Node* prev = cur->_prev;// 獲取cur結點的后繼結點指針Node* next = cur->_next;// 建立prev和next結點之間的雙向鏈接關系prev->_next = next;next->_prev = prev;// 釋放要刪除的cur結點delete cur;// 返回指向刪除位置下一個結點的迭代器return iterator(next);
}

push_back 和 pop_back

• push_back 函數在鏈表尾部插入數據，復用 insert 函數，在 end 迭代器位置前插入元素。

void push_back(const T& x)
{insert(end(), x);
}

• pop_back 函數刪除鏈表尾部元素，復用 erase 函數，刪除 end 迭代器前置遞減位置的元素。

void pop_back()
{assert(!empty());erase(--end());
}

push_front 和 pop_front

• push_front 函數在鏈表頭部插入數據，復用 insert 函數，在 begin 迭代器位置前插入元素。

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

• pop_front 函數刪除鏈表頭部元素，復用 erase 函數，刪除 begin 迭代器位置的元素。

void pop_front()
{assert(!empty());erase(begin());
}

其他函數

size

size 函數用于獲取當前容器中的有效數據個數。由于 list 是鏈表結構，只能通過遍歷的方式逐個統計元素個數。

size_t size() const
{size_t count = 0;for (auto it = begin(); it != end(); ++it){++count;}return count;
}

empty

empty 函數用于判斷容器是否為空，通過比較 begin 和 end 迭代器是否相等來判斷，相等則表示容器為空。

bool empty() const
{return begin() == end();
}

clear

clear 函數用于清空容器中的數據。從第一個有效數據結點開始，逐個刪除結點，直到只剩下頭結點，完成數據清理。

void clear()
{auto it = begin();while (it != end()){auto next = it;++next;delete it._node;it = next;}_head->_next = _head;_head->_prev = _head;
}