C++：List的使用和模擬實現

???學習的道路很枯燥，希望我們能并肩走下來!

文章目錄

前言

一 list的介紹及使用

1.1 list的介紹

1.2 list的使用?

1.2.1?list的構造

1.2.2 list iterator的使用

1.2.3 list capacity?

1.2.4 list element access?

?1.2.5 list modifiers

1.2.6 list的迭代器失效?

?1.2.7?List中sort的效率測試

二、list的模擬實現

?2.1 正向迭代器的實現

2.1.1 正向迭代器的封裝?

?2.1.2 迭代器的使用

2.2?list相關的成員函數

?2.2.1?構造函數

2.2.1.1 默認構造函數

?2.2.1.2 有參構造函數

?2.2.1.3 迭代器區間構造函數?

2.2.1.4 拷貝構造?

1.傳統?

2.現代?

2.2.2 析構函數和clear

2.2.2.1 析構函數

2.2.2.2 clear()

?2.2.3 賦值重載

2.2.4.1?empty、size

?2.2.4.2 insert

2.2.4.3 erase?

2.2.4.4 尾插尾刪頭插頭刪?

2.3 反向迭代器的實現?

三 list模擬實現的全部代碼

總

前言

本篇詳細介紹了list的使用和模擬實現，讓使用者了解list，而不是僅僅停留在表面，更好的模擬，為了更好的使用. 文章可能出現錯誤，如有請在評論區指正，讓我們一起交流，共同進步！

一 list的介紹及使用

1.1 list的介紹

list文本介紹

1. list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。

2. list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。

3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。

4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好。

5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list 的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素)

1.2 list的使用?

list中的接口比較多，此處類似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達到可擴展的能力。以下為list中一些常見的重要接口。

1.2.1?list的構造

構造函數（ (constructor)）	接口說明
list (size_type n, const value_type& val = value_type())	構造的list中包含n個值為val的元素
list()	構造空的list
list (const list& x)	拷貝構造函數
list (InputIterator first, InputIterator last)	用[first, last)區間中的元素構造list

1.2.2 list iterator的使用

此處，大家可暫時將迭代器理解成一個指針，該指針指向list中的某個節點

函數聲明	接口說明
begin + end	返回第一個元素的迭代器+返回最后一個元素下一個位置的迭代器
rbegin + rend	返回第一個元素的reverse_iterator,即end位置，返回最后一個元素下一個位置的 reverse_iterator,即begin位置

【注意】

1. begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動

2. rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動?

1.2.3 list capacity?

函數聲明	接口說明
empty	檢測list是否為空，是返回true，否則返回false
size	返回list中有效節點的個數

1.2.4 list element access?

函數聲明	接口說明
front	返回list的第一個節點中值的引用
back	返回list的最后一個節點中值的引用

?1.2.5 list modifiers

函數聲明	接口說明
push_front	在list首元素前插入值為val的元素
pop_front	刪除list中第一個元素
push_back	在list尾部插入值為val的元素
pop_back	刪除list中最后一個元素
insert	在list position 位置中插入值為val的元素
erase	刪除list position位置的元素
swap	交換兩個list中的元素
clear	清空list中的有效元素

list中還有一些操作，需要用到時大家可參閱list的文檔說明。

1.2.6 list的迭代器失效?

前面說過，此處大家可將迭代器暫時理解成類似于指針

迭代器失效即迭代器所指向的節點的無效，即該節點被刪除了。

因為list的底層結構為帶頭結點的雙向循環鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。

void TestListIterator1(){int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函數執行后，it所指向的節點已被刪除，因此it無效，在下一次使用it時，必須先給
其賦值l.erase(it);  ++it;}}// 改正
void TestListIterator(){int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++);    }}

?1.2.7?List中sort的效率測試

我們用一段代碼來測試一下list中sort的性能

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
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的模擬實現

?2.1 正向迭代器的實現

2.1.1 正向迭代器的封裝?

我們在學習vector的時候，發現vector的迭代器就是一個原生指針T*，這得益于vector的空間的連續性

那我們還能像vector一樣用原生指針去修飾迭代器嗎？

不能，鏈表空間上是不連續的，那我們對一個節點指針進行加減，就很難說能不能找到下一個節點，更多的是找不到的情況

我們在數據結構中訪問下一個節點，往往是利用當前節點存的下一節點的地址來進行訪問的

所以我們可以將迭代器單獨封裝成一個類去管理節點

template<class T, class Ref, class Ptr> //Ref == T& Ptr == T*
struct ListIterator //這里使用struct是因為我們要多次訪問成員，也可使用class+public
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr) :_pNode(pNode){}ListIterator(const Self& l) :_pNode(l._pNode){}T& operator*() //解引用{return _pNode->_val;}T* operator->() {return &_pNode->_val;}Self& operator++() //前置++{_pNode = _pNode->_pNext;return *this;}Self operator++(int) //后置++{Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--() //前置--{_pNode = _pNode->_pPre;return *this;}Self& operator--(int) //后置--{Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l) //不相等判斷{return _pNode != l._pNode;}bool operator==(const Self& l) //相等判斷{return !(*this != l);}PNode _pNode;
};

?T* operator->()? 大家可能有疑惑

?當我們的節點里存的是內置類型或者STL容器是，庫里面的<<重載了這些來讀取數據

但如果是我們自己寫的類型（如class CH），<<并不能讀取該類型的數據

因此我們要取來節點自定義類的指針，來訪問該類的內部的數據（因為最底層都是內置類型