目錄
list的介紹
List的迭代器失效問題
List中sort的效率測試
list 容器的模擬實現思想
模塊分析
作用分析
list_node類設計?
list 的迭代器類設計
迭代器類--存在的意義
迭代器類--模擬實現
模板參數 和 成員變量
構造函數?
* 運算符的重載
++運算符的重載??
?--?運算符的重載
?重載 != 和 ==
?-> 運算符的重載?
list 結構的完善
默認成員函數
構造函數
拷貝構造?
迭代器區間構造??
n個相同元素構造??
賦值重載?
析構函數?
迭代器相關函數
begin 和 end??
訪問容器相關函數
fron 和 back?
增刪改查相關函數
insert
earse?
push_back 和 pop_back
push_front 和 pop_front
容量相關函數
size
resize?
empty
clear
list?容器的模擬實現整體代碼
list.h?
list.cpp
list的介紹
1. list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好。
5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素
List的迭代器失效問題
我們之前學習vector的時候，知道了insert和erase都有可能存在迭代器失效的問題，那list會出現這種情況嗎？？下面來進行分析
insert插入新節點的迭代器，因此insert不可能會出現失效的問題。
?而earse必然會失效，因為該迭代器對應的節點被刪除了。如果我們想繼續用的話，就得利用返回值去更新迭代器，返回值是被刪除元素的下一個位置的迭代器。
List中sort的效率測試
void test_op()
{srand((unsigned int)time(NULL));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){int e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷貝到vector排序，排完以后再拷貝回來int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();//list調用自己的sortint begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
會發現哪怕我先拷貝到vector排完再拷貝回去效率都比list的sort效率高，所以list的sort實際中意義不是很大！！
list 容器的模擬實現思想
模塊分析
根據?list 容器圖可以分析一下?模擬實現?list容器?都要準備什么？
- 存儲元素需要結點--->結點類
- 使用迭代器訪問結點--->迭代器類
- 總體--->list類
作用分析
節點類
作用：存儲?list容器?的元素，因為list里面要存儲各種類型的元素，所以結點類需要定義成模版。結點類中的成員變量則是有三個，分別是：指向前一個結點的_prev指針，指向后一個結點的_next指針，存儲結點元素的_data變量。
迭代器類?
- 此時大家可以思考這樣一個問題，在模擬實現vector類時，我們是直接用結點指針作為迭代器來使用的，并沒有自己實現迭代器類。list中為什么需要單獨實現迭代器類？
原因：如上圖所示。vector容器是數組，它的空間是連續的，所以結點指針完全可以通過自增的方式來指向下一個結點。可是list容器是鏈表，它的空間并不連續，自然不可能直接通過結點指針的自增來指向下一個鏈表結點，所以我們才需要自己實現迭代器類，并且重載自增與自減運算符，這樣就可以通過迭代器的自增或自減來指向前后結點了。?
list類
?
?作用：實現鏈表各項功能的類，為主要部分?
list_node類設計?
list本身?和?list的結點?是兩個不同的結構，需要分開設計。以下是list的節點結構
首先，我們在自己的命名空間內模擬實現 list（為了防止與庫沖突），上面的代碼就是list節點的結構。在這里并沒有使用 class，因為 struct 默認訪問權限是 public，又因為節點是需要經常訪問的，所以使用struct更好。但是此結構體非C語言的結構體，已經是類了
list 的迭代器類設計
迭代器類--存在的意義
之前?模擬實現 string?和?vector?時都沒有說要實現一個迭代器類，為什么實現list的時候就需要實現一個迭代器類了呢？
因為?string?和?vector?對象都將其數據存儲在了一塊連續的內存空間，我們通過指針進行自增、自減以及解引用等操作，就可以對相應位置的數據進行一系列操作，因此string和vector當中的迭代器就是原生指針。
但是對于?list?來說，其各個結點在內存當中的位置是隨機的，并不是連續的，我們不能僅通過結點指針的自增、自減以及解引用等操作對相應結點的數據進行操作。
- ?而迭代器的意義就是，讓使用者可以不必關心容器的底層實現，可以用簡單統一的方式對容器內的數據進行訪問。
- 既然?list?的結點指針的行為不滿足迭代器定義，那么我們可以對這個結點指針進行封裝，對結點指針的各種運算符操作進行重載，使得我們可以用和string和vector當中的迭代器一樣的方式使用list當中的迭代器。例如，當你使用?list 當中的迭代器進行自增操作時，實際上執行了p = p->next語句，只是你不知道而已。
迭代器類--模擬實現
模板參數 和 成員變量
我們知道指針有兩種const形勢，一種是const T* ptr1;另一種是T* const? ptr2，那我們的const的迭代器是哪一種呢？
我們知道const迭代器是可以++的，它只是限制內容不能修改，但是它指針本身是可以++的。所以肯定是const T* prt1這種形式。T* const? ptr2的const本身修飾的是指針不能修改的
typedef const? _list_iterator<T> const_iterator;那我們這樣寫能行嗎？
不行的，這樣就是迭代器本身不能修改了。我們要的是它指向的內容不能修改的，那該怎么辦呢？
我們只需要讓它重載的*加上const就可以了 const T& operator*() 這樣當調用*的時候，就會提示不能修改內容了。
但是這樣設計太臃腫了。我們發現const_iterator和普通的iterator只有operator*()的返回值不一樣
那我們能不能通過一個類型去控制這個返回值呢？肯定是可以的，我們可以增加個模板參數
template<class T, class Ref, class Ptr>typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;我們知道一個類模板給兩個不同的參數就是兩個類?
- 這里我們就可以看出，迭代器類?的模板參數列表當中的?Ref?和?Ptr?分別代表的是?引用類型（T&）?和?指針類型（T *）。?
- 當我們使用?普通迭代器?時，編譯器就會實例化出一個?普通迭代器 對象；當我們使用?const迭代器時，編譯器就會實例化出一個?const迭代器對象。?
- 若該迭代器類不設計三個模板參數，那么就不能很好的區分-- 普通迭代器 和-- const迭代器。?
?因為?結點類?和?迭代器類?自身的類型名太長，寫起來太麻煩，所以我們用?typedef關鍵字?給這兩個類型取了別名。
我們為?結點類?的類型取的別名是?Node，為?迭代器類?取的別名是?Self。
template<typename T, typename Ref, typename Ptr>
struct _list_iterator
{typedef ListNode<T> Node; //為結點類取別名typedef _list_iterator<T, Ref, Ptr> self; //為正向迭代器類取別名//成員變量Node* _node; //指向結點的指針
}看這個代碼?list<int>::iterator it = lt.begin();?這里會發生拷貝構造，因為我們沒有自己寫，所以編譯器會調用默認拷貝構造。對于自定義類型的默認拷貝構造是值拷貝(淺拷貝)。那會有問題嗎？
答案是否定的，我們要的就是淺拷貝。對于 迭代器 來說，淺拷貝通常是完全合適的，因為：
- 迭代器本身只是容器中的一個元素的訪問者，它并不擁有實際的容器數據。它只是持有容器中元素的位置（指針或類似機制），而不直接管理數據。
- 所以拷貝一個迭代器通常不會影響容器的所有權或內存的生命周期，因為它只是一個指向容器的指針，拷貝它只是創建一個新的指針來訪問同樣的容器數據。
- 容器本身會負責管理數據，迭代器只需要能夠訪問和遍歷這些數據，所以淺拷貝是安全且有效的。
那為什么it和begin()都指向了第一個節點，不崩潰呢？
這個時候我們就要想想值拷貝崩潰的原因是什么了。以前我們了解到值拷貝崩潰的原因是進行了兩次析構。但是迭代器我們沒寫析構函數呀。因為這個節點不是屬于迭代器的，迭代器不是要做管理節點的工作，它只是訪問節點?
構造函數?
迭代器類?實際上就是對?結點指針進行了封裝，其成員變量就只有一個，那就是結點指針，其構造函數直接根據所給結點指針構造一個迭代器對象即可。
//正向迭代器構造函數
_list_iterator(Node* node = nullptr) // 默認構造函數:_node(node){}* 運算符的重載
當我們使用?解引用操作符?時，是想得到該位置的數據內容。因此，我們直接返回當前結點指針所指結點的數據即可，但是這里需要使用引用返回，因為解引用后可能需要對數據進行修改。
//重載*
//返回迭代器指向的結點的值域// T& operator*()Ref operator*()
{return _node->_data;
}++運算符的重載??
自增運算符的?重載?是迭代器類的核心。前置++重載中，要讓當前迭代器指向下一個結點后，再把迭代器返回。后置++中是把當前迭代器用臨時變量保存一份，再把迭代器指向下一個結點，然后返回臨時變量。注意：重載后置++或后置--時，必須在函數參數列表加一個int變量，這是語法規定。
- 重載前置++?和?后置++?時的返回值有所不同，前置++返回值類型是--------迭代器類型的引用，而后置++返回值類型是------ 迭代器類型。
- 前置++中，返回的是對?this?的解引用，this并不是局部變量，函數結束后依然存在，所以可以返回它的引用，減少值拷貝次數。
- 后置++中，返回的?temp?是函數中創建的局部對象，在函數結束后會被銷毀，所以返回值類型不可以是引用。這里就必須通過值拷貝來返回值。
//重載前置++
//返回迭代器對象自身的引用
//因為對象自身并不是該函數中的局部對象self& operator++()
{_node = _node->_next;return *this;
}//重載后置++
//此時需要返回temp對象，而不是引用
//因為temp對象是局部的對象
//函數結束后就被釋放self operator++(int a)
{self temp(*this);_node = _node->_next;return temp;
}?--?運算符的重載
前置--和后置--關于函數的返回類型跟重載++類似，這里就不再贅述。
//重載前置--
self& operator--()
{_node = _node->_prev;return *this;
}//重載后置--
self operator--(int a)
{self temp(*this);_node = _node->_prev;return temp;
}?重載 != 和 ==
這里只需要比較_node是否相同即可，因為_node本身就是指向結點的指針，保存著結點的地址，只要地址相同，那自然就是同一個結點了
//重載!=
bool operator!=(const self& s)const
{return _node != s._node;
}//重載==
bool operator==(const self& s)const
{return _node == s._node;
}?-> 運算符的重載?
? ?有時候，實例化的模板參數是自定義類型，我們想要像 指針 一樣訪問訪問自定義類型力的成員變量，這樣顯得更通俗易懂，所以就要重載 -> 運算符，它的返回值是 T*?
想想如下場景：?
當?list容器?當中的每個結點存儲的不是內置類型，而是自定義類型，例如數據存儲類，那么當我們拿到一個位置的迭代器時，我們可能會使用?->運算符訪問 Data?的成員：?
struct Data
{Data(int a = int(), double b = double(), char c = char()):_a(a), _b(b), _c(c){}int _a;double _b;char _c;
};void TestList()
{list<Data> lt;lt.push_back(Data(1, 2.2, 'A'));auto it = lt.begin();cout << (*it)._a << endl; //不使用 operator->() 比較別扭cout << it.operator->()->_b << endl; //這種寫法是真實調用情況cout << it->_c << endl; //編譯器直接優化為 it->
}int main()
{TestList();return 0;
}list 結構的完善
成員變量和模板參數
- 因為?list?可以存儲各種類型的元素，因此?list?類要設置為模板，T就是存儲的元素的類型。
- 因為?結點類?和?迭代器類?的類名太長，所以用?typedef?關鍵為它們取了別名。這里迭代器的三個參數之所以設置為<T , T& , T*>，是因為list類只給出了一個模板參數，而迭代器類應該有三個，因此用?T&?和?T*?作為另外兩個參數。
//帶頭結點的雙向鏈表
template<class T>
class list
{typedef ListNode<T> Node;
public:typedef _list_iterator<T, T&, T*> Iterator; //正向迭代器typedef _list_iterator<T, const T&, const T*> const_iterator;
private:Node* _head; //指向頭結點的指針
}默認成員函數
構造函數
list 的成員變量是 一個節點類，在構造頭節點時，需要將這單個頭節點構造成一個雙向循環鏈表；
//構造函數
list()
{_head = new Node; //new一個節點出來_head->_prev = _head; _head->_next = _head; //_prev 和 _next 同時指向了頭結點，形成了雙向循鏈表
}拷貝構造?
拷貝構造是用一個已有對象去構造出另一個對象，首先將待構造對象進行初始化，然后利用迭代器區間去構造一個和 lt1 一樣的臨時的 tmp 對象，再進行數據的交換，達到深拷貝的目的。??
//拷貝構造 --- 現代寫法 lt2(lt1)
list(const list<T>& lt)
{_head = new Node;_head->_prev = _head;_head->_next = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);
}
迭代器區間構造??
由于list可以存儲各種類型的元素，所以區間構造時自然也會用到各種類型的迭代器，因此區間構造也應該定義為模版，需要給出模版參數列表。具體實現和上一個函數是差不多的。
//迭代器區間構造
template<class iterator>
list(iterator first, iterator last)
{_head = new Node;_head->_prev = _head;_head->_next = _head;while (first != last){push_back(*first);//尾插數據，會根據不同類型的迭代器進行調用++first;}
}n個相同元素構造??
通過用?n 個 val 來對對象進行初始化，需要注意這里的?T( )是一個匿名對象，作為 val 的缺省參數，因為我們并不知道傳給val的是一個對象還是一個整形（或其他），給缺省參數的好處在于，對于自定義類型編譯器會去調用自定義類型的構造函數來對val進行初始化，如果是內置類型，它也是有自己的構造函數
//用n個val個構造
list(int n, const T& val = T())
{ _head = new Node;_head->_prev = _head;_head->_next = _head;for (int i = 0; i < n; i++){push_back(val);}
}賦值重載?
將賦值運算符重載的參數定義為 list 類型的對象而不是對象的引用，傳參時會發生值拷貝。因此我們可以把 list對象 的 this指針 和 拷貝出來的參數 L 指向頭結點的指針交換，這樣 this指針 就直接指向了拷貝出來的L的頭結點。L則指向了list對象的頭結點，在函數結束后，作為局部對象的L將被銷毀，它指向的空間也會被釋放。
//傳統寫法
list<T>& operator=(const list<T>& lt)
{if (this != <) //避免自己給自己賦值{clear(); //清空容器for (const auto& e : lt){push_back(e); //將容器lt當中的數據一個個尾插到鏈表后面}}return *this; //支持連續賦值
}析構函數?
對對象進行析構時，首先調用clear函數清理容器當中的數據，然后將頭結點釋放，最后將頭指針置空即可。
//析構函數
~list()
{clear(); //清理容器delete _head; //釋放頭結點_head = nullptr; //頭指針置空
}迭代器相關函數
begin 和 end??
首先我們應該明確的是：begin 函數返回的是第一個有效數據的迭代器，end函數返回的是最后一個有效數據的下一個位置的迭代器。
對于?list?這個?帶頭雙向循環鏈表?來說，其第一個有效數據的迭代器就是使用頭結點后一個結點的地址構造出來的迭代器，而其最后一個有效數據的下一個位置的迭代器就是使用頭結點的地址構造出來的迭代器。（最后一個結點的下一個結點就是頭結點）
iterator begin()
{//返回使用頭結點后一個結點的地址構造出來的普通迭代器return iterator(_head->_next); //這里也可以是隱式類型轉換
}
iterator end()
{//返回使用頭結點的地址構造出來的普通迭代器return iterator(_head);
}- 當然，還需要重載一對用于?const對象?的 begin函數 和 end函數。
const_iterator begin() const
{//返回使用頭結點后一個結點的地址構造出來的const迭代器return const_iterator(_head->_next);
}
const_iterator end() const
{//返回使用頭結點的地址構造出來的普通const迭代器return const_iterator(_head);
}訪問容器相關函數
fron 和 back?
front 和 back 函數分別用于獲取第一個有效數據和最后一個有效數據，因此，實現front和back函數時，直接返回第一個有效數據和最后一個有效數據的引用即可。?
T& front()
{return *begin(); //返回第一個有效數據的引用
}
T& back()
{return *(--end()); //返回最后一個有效數據的引用
}- 當然，這也需要重載一對用于const對象 的front函數 和 back函數，因為 const對象 調用front和back函數后所得到的數據不能被修改。
const T& front() const
{return *begin(); //返回第一個有效數據的const引用
}const T& back() const
{return *(--end()); //返回最后一個有效數據的const引用
}增刪改查相關函數
insert
insert函數可以在所給迭代器之前插入一個新結點。?
- 先根據所給迭代器得到該位置處的結點指針cur，然后通過cur指針找到前一個位置的結點指針prev，接著根據所給數據x構造一個待插入結點，之后再建立新結點與cur之間的雙向關系，最后建立新結點與prev之間的雙向關系即可。
//插入函數
void insert(iterator pos, const T& x)
{assert(pos._node); //檢測pos的合法性node* cur = pos._node; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* newnode = new Node(x); //根據所給數據x構造一個待插入結點//建立newnode與cur之間的雙向關系newnode->_next = cur;cur->_prev = newnode;//建立newnode與prev之間的雙向關系newnode->_prev = prev;prev->_next = newnode;
}earse?
先根據所給迭代器得到該位置處的結點指針cur，然后通過cur指針找到前一個位置的結點指針prev，以及后一個位置的結點指針next，緊接著釋放cur結點，最后建立prev和next之間的雙向關系即可。
//刪除函數
iterator erase(iterator pos)
{assert(pos._node); //檢測pos的合法性assert(pos != end()); //刪除的結點不能是頭結點node* cur = pos._node; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* next = cur->_next; //迭代器pos后一個位置的結點指針delete cur; //釋放cur結點//建立prev與next之間的雙向關系prev->_next = next;next->_prev = prev;return iterator(next); //返回所給迭代器pos的下一個迭代器
}這里如果返回當前的位置，也會有迭代器失效問題?
push_back 和 pop_back
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;
}
push_front 和 pop_front
?push_front函數就是在第一個有效結點前插入結點，而pop_front就是刪除第一個有效結點。
//頭插
void push_front(const T& x)
{insert(begin(), x); //在第一個有效結點前插入結點
}
//頭刪
void pop_front()
{erase(begin()); //刪除第一個有效結點
}容量相關函數
size
size函數用于獲取當前容器當中的有效數據個數，因為list是鏈表，所以只能通過遍歷的方式逐個統計有效數據的個數。?
size_t size() const
{size_t sz = 0; //統計有效數據個數const_iterator it = begin(); //獲取第一個有效數據的迭代器while (it != end()) //通過遍歷統計有效數據個數{sz++;it++;}return sz; //返回有效數據個數
}resize?
resize函數的規則：
- 若當前容器的size小于所給n，則尾插結點，直到size等于n為止。
- 若當前容器的size大于所給n，則只保留前n個有效數據。
實現resize函數時，不要直接調用size函數獲取當前容器的有效數據個數，因為當你調用size函數后就已經遍歷了一次容器了，而如果結果是size大于n，那么還需要遍歷容器，找到第n個有效結點并釋放之后的結點。
void resize(size_t n, const T& val = T())
{iterator i = begin(); //獲取第一個有效數據的迭代器size_t len = 0; //記錄當前所遍歷的數據個數while (len < n&&i != end()){len++;i++;}if (len == n) //說明容器當中的有效數據個數大于或是等于n{while (i != end()) //只保留前n個有效數據{i = erase(i); //每次刪除后接收下一個數據的迭代器}}else //說明容器當中的有效數據個數小于n{while (len < n) //尾插數據為val的結點，直到容器當中的有效數據個數為n{push_back(val);len++;}}
}empty
empty函數用于判斷容器是否為空，我們直接判斷該容器的begin函數和end函數所返回的迭代器，是否是同一個位置的迭代器即可。（此時說明容器當中只有一個頭結點）
bool empty() const
{return begin() == end(); //判斷是否只有頭結點
}clear
clear函數用于清空容器，我們通過遍歷的方式，逐個刪除結點，只保留頭結點即可。
void clear()
{iterator it = begin();while (it != end()) //逐個刪除結點，只保留頭結點{it = erase(it);}
}可能會有同學問：這個是清除全部操作 為啥沒有對it++進行遍歷刪除呢
這里 erase(it) 會刪除當前迭代器 it 指向的元素，并返回一個指向下一個元素的迭代器。所以就相當于++了
list?容器的模擬實現整體代碼
list.h?
#pragma once
#include <iostream>
#include <string>
#include <assert.h>
using std::ostream;
using std::istream;
using std::cin;
using std::cout;
using std::endl;// 為了避免和庫里的 list 產生沖突，在自己的命名空間內實現 list
// 帶頭---雙向---循環---鏈表
namespace xas_list
{// 通過模板能夠實現不同類型的數據存儲template<class T>// 鏈表節點的構造struct ListNode{ListNode<T>* _next; // 指向后面節點的指針ListNode<T>* _prev; // 指向前面節點的指針T _data; // 一個節點中的數據// 構造函數ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};// 模擬實現迭代器template<class T, class Ref, class Ptr>// 模式一個迭代器 類型struct _list_iterator{typedef ListNode<T> Node; // 為節點類 取別名//只要用自己的類型，就對其typedef成self，方便后續使用typedef _list_iterator<T, Ref, Ptr> self; // 為正向迭代器類 取別名// 成員變量Node* _node; // _node 表示一個節點_list_iterator(Node* node = nullptr) // 默認構造函數:_node(node){}// ++it 重載前置++ —— 讓鏈表能夠像數組一樣去++操作，訪問元素// 注意：這里的 this 不是局部變量，函數結束不會被銷毀，可以使用引用返回，減少拷貝次數self& operator++(){//前置++返回的是++之后的值，直接讓當前位置的結點指向下一個節點_node = _node->_next;return *this;}//重載后置++//此時需要返回temp對象，而不是引用//因為temp對象是局部的對象//函數結束后就被釋放//it++ 重載后置++ —— （這里需要加上int作為一個站位符，與前置++區分）self operator++(int a){self temp(*this);_node = _node->_next; //后置++返回的是++之前的值，需要保存當前節點，再指向下一個節點return temp;}//重載前置--self& operator--() {_node = _node->_prev;return *this;}//重載后置--self operator--(int a) {self temp(*this);_node = _node->_prev;return temp;}// 賦值重載重載 * //返回迭代器指向的結點的值域Ref operator*(){return _node->_data;}// 重載 -> 操作符 ---實現指針訪問元素Ptr operator->(){return &_node->date;}// 賦值重載 !=bool operator!=(const self& s) const{return _node != s._node;}// 賦值重載 ==bool operator==(const self& s) const{return _node == s._node;}};template<class T>// 創建一個 list 類class list{typedef ListNode<T> Node; // 重新命名節點(結構體)的名稱public:typedef _list_iterator<T, T&, T*> iterator; // 為 迭代器類型取 別名typedef _list_iterator<T, const T&, const T*> const_iterator;// 正向迭代器 和 正向 const 迭代器iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;// 默認成員函數list(); // 構造函數 --- 無參構造list(int n, const T& val = T()); // 用 n個val 構造template<class iterator>list(iterator first, iterator last) // 迭代器區間構造{empty_init();while (first != last){push_back(*first);++first;}}~list(); // 析構函數list(list<T>& lt); // 拷貝構造void empty_init(); // 初始化一個循環鏈表list<T>& operator=(list<T> lt); // 賦值運算符符重載// 容量相關的函數size_t size() const; // 計算節點的有效個數bool Empty()const; // 判空 不為空時，返回 truevoid clear(); // 清空數據void resize(size_t n, const T& val = T()); // 設置list對象的有效元素個數// 訪問容器相關函數T& front(); // 返回第一個有效數據T& back(); // 返回最后一個有效數據const T& front() const; const T& back() const;// 修改容器內容的相關函數void push_back(const T& x); // 尾插iterator insert(iterator pos, const T& x); // 插入void push_front(const T& x); // 頭插iterator erase(iterator pos); // 刪除void pop_back(); // 尾刪void pop_front(); // 頭刪void swap(list<T>& temp); // 交換函數private:Node* _head;};// 打印函數void printf_list(const list<int>& lt);
}list.cpp
#include "list.h"template<class T>
xas_list::list<T>::list() // 構造函數 --- 無參構造
{_head = new Node; //申請創建一個新的節點 --- 雙向循環_head->_next = _head; _head->_prev = _head;
}template<class T> // 用 n個val 進行構造
xas_list::list<T>::list(int n, const T& val)
{// 創建一個空節點_head = new Node;// 形成一個帶頭雙向循環鏈表_head->_prev = _head;_head->_next = _head;for (int i = 0; i < n; i++){push_back(val);}
}template<class T>
xas_list::list<T>::~list() // 析構函數
{clear();delete _head;_head = nullptr;}// 初始化一個循環鏈表
template<class T>
void xas_list::list<T>::empty_init()
{//申請創建一個新的節點 --- 雙向循環_head = new Node;_head->_next = _head;_head->_prev = _head;
}template<class T>
xas_list::list<T>::list( list<T>& lt)
{//申請創建一個新的節點 --- 雙向循環empty_init();for (auto& e : lt){push_back(e);}
}template<class T>
void xas_list::list<T>::swap(list<T>& temp)
{std::swap(_head, temp._head);
}// lt1 = lt2; --- 賦值重載
template<class T>
xas_list::list<T>& xas_list::list<T>::operator=(list<T> lt)
{//if (this != <) // 判斷一下是否有給自己賦值//{// // 將lt1 先清空，再將lt2 插入到 lt1中// // 注意 this 指針// clear();// for (const auto& e : lt)// {// push_back(e);// }//}swap(lt);return *this;
}template<class T>
void xas_list::list<T>::clear() // 清空數據
{//復用eraseiterator it = begin();while (it != end()){it = erase(it);//用it接收刪除后的下一個結點的位置}
}// 正向迭代器
// begin迭代器指向的是正方向第一個有效結點，也就是頭結點的下一個結點。
// 因為有 哨兵位的存在
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::begin()
{return iterator(_head->_next);
}// end迭代器指向的是正方向最后一個有效結點的下一個結點，也就是頭結點。
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::end()
{return iterator(_head);
}template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::begin()const
{return const_iterator(_head->_next);
}template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::end()const
{return const_iterator(_head);
}template<class T>
// ListNode(const T& x = T()) 這里的 T() 的給一個缺省值
void xas_list::list<T>::push_back(const T& x) // 尾插
{// 創建一個新的節點 ---- Node//Node* newnode = new Node(x);//Node* tail = _head->_prev; // 找尾節點--------頭節點的前一個節點進行尾插//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);
}// 頭插
template<class T>
void xas_list::list<T>::push_front(const T& x)
{insert(begin(), x);
}// 插入
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::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);
}// 刪除
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::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);
}// 尾刪
template<class T>
void xas_list::list<T>::pop_back()
{erase(--end());
}// 頭刪
template<class T>
void xas_list::list<T>::pop_front()
{erase(begin());
}// 判斷 list 的有效鏈表個數
template<class T>
size_t xas_list::list<T>::size() const
{size_t count = 0;list<T>::const_iterator it = begin();while (it != end()){count++;it++;}return count;
}// 判斷 list 是否為空
template<class T>
bool xas_list::list<T>::Empty() const
{return _head->_next == _head;
}template<class T>
void xas_list::list<T>::resize(size_t n, const T& val)
{list<T>::iterator it = begin(); //獲取第一個有效數據的迭代器size_t len = 0; //記錄當前所遍歷的數據個數while (len < n && it != end()){len++;it++;}if (len == n) //說明容器當中的有效數據個數大于或是等于n{while (it != end()) //只保留前n個有效數據{it = erase(it); //每次刪除后接收下一個數據的迭代器}}else //說明容器當中的有效數據個數小于n{while (len < n) //尾插數據為val的結點，直到容器當中的有效數據個數為n{push_back(val);len++;}}
}template<class T>
T& xas_list::list<T>::front()
{return *begin();
}template<class T>
T& xas_list::list<T>::back()
{return *(--end());
}template<class T>
const T& xas_list::list<T>::front() const
{return *begin();
}template<class T>
const T& xas_list::list<T>::back() const
{return *(--end());
}// 打印對應的鏈表
void xas_list::printf_list(const list<int>& lt)
{list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;
}// 遍歷的測試
void test1()
{xas_list::list<int> lt(5,6);lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_front(0);// 頭刪lt.pop_back();// 尾刪lt.pop_front();// -------------迭代器測試------------------// cout << "迭代器的測試" << endl;xas_list::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;cout << "范圍for的測試" << endl;// -------------范圍 for 測試------------------// for (auto e : lt){cout << e << " ";}cout << endl;cout << "清空數據" << endl;// 清空數據lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;}void test2()
{xas_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;cout << "拷貝構造" << endl;xas_list::list<int> copy(lt);for (auto e : copy){cout << e << " ";}cout << endl;cout << "賦值重載" << endl;xas_list::list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(33);lt = lt1;for (auto e : lt){cout << e << " ";}cout << endl;}// const 迭代器
void test3()
{xas_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);int arr[] = { 1,2,3,4,5,6,7,8,9,10 };xas_list::list<int> l3(arr, arr + 10); //迭代器區間構造cout << l3.size() << endl;cout << l3.Empty() << endl;l3.resize(12,2);cout << l3.back() << endl;cout << l3.front() << endl;printf_list(l3);
}int main()
{test3();return 0;})
下)
