目錄

1、list介紹

所要實現(xiàn)類及其成員函數(shù)接口總覽?

2、結點類的模擬實現(xiàn)?

基本框架

構造函數(shù)

3、迭代器類的模擬實現(xiàn)

迭代器類存在的意義

3.1、正向迭代器?

基本框架

默認成員函數(shù)

構造函數(shù)

++運算符重載

--運算符重載?

!=運算符重載

==運算符重載?

*運算符重載?

->運算符重載?

3.2、反向迭代器

4、list類的模擬實現(xiàn)

基本框架

4.1、默認成員函數(shù)?

構造函數(shù)

拷貝構造函數(shù)

賦值運算符重載函數(shù)?

析構函數(shù)

4.2、迭代器相關函數(shù)

begin和end

rbegin和rend

4.3、訪問容器相關函數(shù)?

front和back

4.4、增加的相關函數(shù)?

insert

push_back尾插

push_front頭插?

4.5、刪除的相關函數(shù)?

erase

pop_back尾刪?

pop_front頭刪?

4.6、其他函數(shù)

size

resize

clear?

empty

empty_init空初始化

swap交換?

---

1、list介紹

在STL的底層實現(xiàn)當中，list其實就是一個帶頭雙向循環(huán)鏈表：

我們現(xiàn)在要模擬實現(xiàn)list，要實現(xiàn)以下三個類：

1. 模擬實現(xiàn)結點類
2. 模擬實現(xiàn)迭代器的類
3. 模擬list主要功能的類

第三個類的實現(xiàn)是基于前兩個類。我們依次遞進進行講解。?

---

所要實現(xiàn)類及其成員函數(shù)接口總覽?

namespace Fan
{//模擬實現(xiàn)list當中的結點類template<class T>struct _list_node{//成員函數(shù)_list_node(const T& val = T()); //構造函數(shù)//成員變量T _data;                  //數(shù)據(jù)域_list_node<T>* _next;    //后驅(qū)指針_list_node<T>* _prev;    //前驅(qū)指針}; //模擬實現(xiàn)list迭代器template<class T,class Ref,class Ptr>struct _list_iterator{typedef _list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(Node*node);  //構造函數(shù)//各種運算符重載函數(shù)self operator++();self operator--();self operator++(int);self operator--(int);bool operator==(const self& s)const;bool operator!=(const self& s)const;Ref operator*();Ptr operator->();//成員變量Node* _node; //一個指向結點的指針};//模擬實現(xiàn)listtemplate<class T>class list{public:typedef _list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默認成員函數(shù)list();list(const list<T>& lt);list<T>& operator=(const list<T>& lt);~list();//迭代器相關函數(shù)iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//訪問容器相關函數(shù)T& front();T& back();const T& front()const;const T& back() const;//插入、刪除函數(shù)void insert(iterator pos, const T& x);iterator erase(iterator pos);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();//其它函數(shù)size_t size()const;void resize(size_t n, const T& val = T());void clear();bool empty()const;void swap(list<T>& lt);private:Node* _head; //指向鏈表頭結點的指針};
}

---

2、結點類的模擬實現(xiàn)?

基本框架

因為list的本質(zhì)為帶頭雙向循環(huán)鏈表，所以我們要確保其每個結點有以下成員：

1. 前驅(qū)指針
2. 后繼指針
3. data值存放數(shù)據(jù)

//模擬實現(xiàn)list當中的結點類template<class T>struct _list_node{//成員變量T _data;                  //數(shù)據(jù)域_list_node<T>* _next;    //后驅(qū)指針_list_node<T>* _prev;    //前驅(qū)指針}; 

---

構造函數(shù)

對于結點類的成員函數(shù)，我們只需要實現(xiàn)一個構造函數(shù)即可。結點的釋放則由list默認生成的析構函數(shù)來完成。

//構造函數(shù)
_list_node(const T& val=T()):_data(val),_next(nullptr),_prev(nullptr)
{}

---

3、迭代器類的模擬實現(xiàn)

迭代器類存在的意義

我們知道list是帶頭雙向循環(huán)鏈表，對于鏈表，我們知道其內(nèi)存空間并不是連續(xù)的，是通過結點的指針順次鏈接。而string和vector都是將數(shù)據(jù)存儲在一塊連續(xù)的內(nèi)存空間，我們可以通過指針進行自增、自減以及解引用等操作，就可以對相應位置的數(shù)據(jù)進行一系列操作，因此string和vector的迭代器都是原生指針。而對于list，其各個結點在內(nèi)存中的位置是隨機的，并不是連續(xù)的，我們不能通過結點指針的自增、自減以及解引用等操作來修改對應結點數(shù)據(jù)。為了使得結點指針的各種行為和普通指針一樣，我們對結點指針進行封裝，對其各種運算符進行重載，使得我們可以用和string和vector當中的迭代器一樣的方式使用list當中的迭代器。

---

3.1、正向迭代器?

基本框架

//模擬實現(xiàn)list迭代器
template<class T,class Ref,class Ptr>
struct _list_iterator
{typedef _list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;//成員變量Node* _node; //一個指向結點的指針
};

• 注意：

我們這里迭代器類的模板參數(shù)里面包含了3個參數(shù)：

template<class T,class Ref,class Ptr>

在后文list類的模擬實現(xiàn)中，我對迭代器進行了兩種typedef：

typedef _list_iterator<T, T&, T*> iterator;//普通迭代器
typedef _list_iterator<T, const T&, const T*> const_iterator;//const迭代器

根據(jù)這里的對應關系：Ref對應的是&引用類型，Ptr對應的是*指針類型。當我們使用普通迭代器時，編譯器就會實例化出一個普通迭代器對象；當我們使用const迭代器時，編譯器就會實例化出一個const迭代器對象。提高代碼復用性。

---

默認成員函數(shù)

這里的默認成員函數(shù)我們只需要寫構造函數(shù)。

• 析構函數(shù)—結點并不屬于迭代器，不需要迭代器釋放
• 拷貝構造—編譯器默認生成的淺拷貝即可
• 賦值重載—編譯器默認生成的淺拷貝即可

---

構造函數(shù)

我們這里通過結點的指針即可完成構造。

//構造函數(shù)
_list_iterator(Node* node):_node(node)
{}

---

++運算符重載

++運算符非為前置++和后置++

• 前置++

迭代器++的返回值還是迭代器。對于結點指針的前置++，我們就應該先讓結點指針指向后一個結點，然后返回“自增”后的結點指針。

//前置++
self& operator++()
{_node = _node->_next; //直接讓自己指向下一個結點即可實現(xiàn)++return *this;         //返回自增后的結點指針
}

• 后置++

為了和前置++進行區(qū)分，后置++通常需要加上一個參數(shù)。此外，后置++是返回自增前的結點指針。

//后置++
self operator++(int) //加參數(shù)以便于區(qū)分前置++
{self tmp(*this);      //拷貝構造tmp_node = _node->_next; //直接讓自己指向下一個結點即可實現(xiàn)++return tmp;
}

---

--運算符重載?

--運算符分為前置--和后置--

• 前置--

前置--是讓結點指針指向上一個結點，然后再返回“自減”后的結點指針即可。

//前置--
self operator--()
{_node = _node->_prev; //讓結點指針指向前一個結點return *this;         //返回自減后的結點指針
}

• 后置--

先記錄當前結點指針的指向，然后讓結點指針指向前一個結點，最后返回“自減”前的結點指針即可。

//后置--
self operator--(int) //加參數(shù)以便于區(qū)分前置--
{self tmp(*this); //拷貝構造tmp_node = _node->_prev;return tmp;
}

---

!=運算符重載

這里的比較是兩個迭代器的比較，我們直接返回兩個結點的位置是否不同即可。

//!=運算符重載
bool operator!=(const self& it)
{return _node != it._node; //返回兩個結點指針的位置是否不同即可
}

---

==運算符重載?

我們直接返回兩個結點指針是否相同即可。

//==運算符重載
bool operator==(const self& it)
{return _node == it._node; //返回兩個結點指針是否相同
}

---

*運算符重載?

當我們使用解引用操作符時，是想要得到該位置的數(shù)據(jù)內(nèi)容。因此我們直接返回結點指針指向的_data即可。

//*運算符重載
Ref operator*() //結點出了作用域還在，我們用引用返回
{return _node->_data; //返回結點指向的數(shù)據(jù)
}

---

->運算符重載?

假設出現(xiàn)此類情形，我們鏈表中存儲的不是內(nèi)置類型，而是自定義類型，如下：

struct AA
{AA(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};
void test()
{Fan::list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));lt.push_back(AA(4, 4));
}

對于內(nèi)置類型和自定義類型成員的指針，其訪問方式是不同的：

int*  *it
AA*   (*it). 或者 it->

這里我們應該重載一個->運算符。以便于訪問自定義類型成員的指針的數(shù)據(jù)。

//->運算符重載
Ptr operator->()
{return &(operator*()); //返回結點指針所指向的數(shù)據(jù)的地址//或者return &_node->_data;
}

實現(xiàn)了->運算符重載后，我們執(zhí)行it->_a1，編譯器就將其轉(zhuǎn)換成it.operator->()，此時獲得的是結點位置的地址即AA*，這里應該還有一個箭頭->才能獲取數(shù)據(jù)，也就是這樣：it.operator->()->_a1

• 編譯器為了可讀性將其進行優(yōu)化處理，如果不進行優(yōu)化應該是it->->a1,優(yōu)化以后省略了一個箭頭->。

---

3.2、反向迭代器

反向迭代器是一種適配器模式(后面我們會講到適配器)。相比于正向迭代器，反向迭代器主要有以下三種變化。

• 反向迭代器里面的++執(zhí)行的操作是正向迭代器里面的--。
• 反向迭代器里面的--執(zhí)行的操作是正向迭代器里面的++。
• 反向迭代器里面的*解引用和->操作指向的是前一個數(shù)據(jù)。

?反向迭代器是一種適配器模式。任何容器的迭代器封裝適配一下都能夠生成對應的反向迭代器。

?反向迭代器里面的*解引用和->操作指向的是前一個數(shù)據(jù)。其目的主要是為了對稱設計。在代碼實現(xiàn)當中，rbegin函數(shù)對應的是end函數(shù)，rend函數(shù)對應的是begin函數(shù)。

代碼如下：

namespace Fan
{template<class Iterator,class Ref,class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;//構造函數(shù)Reverse_iterator(Iterator it):_it(it){}//*運算符重載Ref operator*(){Iterator tmp = _it;//返回上一個數(shù)據(jù)return *(--tmp);}//->運算符重載Ptr operator->(){//復用operator*,返回上一個數(shù)據(jù)return &(operator*());}//++運算符重載Self& operator++(){--_it;return *this;}Self operator++(int){Iterator tmp = _it;--_it;return tmp;}//--運算符重載Self& operator--(){++_it;return *this;}Self operator--(int){Iterator tmp = _it;++_it;return tmp;}//!=運算符重載bool operator!=(const Self& s){return _it != s._it;}//==運算符重載bool operator==(const Self& s){return _it == s._it;}};
}

---

4、list類的模擬實現(xiàn)

基本框架

在list類中的唯一一個成員變量即為先前的結點類構成的頭結點指針：

//模擬實現(xiàn)list
template<class T>
class list
{
public:typedef _list_node<T> Node;//正向迭代器typedef _list_iterator<T, T&, T*> iterator;  //普通迭代器typedef _list_iterator<T, const T&, const T*> const_iterator;  //const迭代器//反向迭代器typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;private:Node* _head; //指向鏈表頭結點的指針
};

---

4.1、默認成員函數(shù)?

構造函數(shù)

• 無參構造：

list是一個帶頭雙向循環(huán)鏈表，在構造一個list對象時，我們直接申請一個頭結點，并讓其前驅(qū)指針和后繼指針都指向自己即可。

//構造函數(shù)
list()
{_head = new Node();//申請一個頭結點_head->_next = _head;//頭結點的下一個結點指向自己構成循環(huán)_head->_prev = _head;//頭結點的上一個結點指向自己構成循環(huán)
}

• 傳迭代器區(qū)間構造：

先進行初始化，然后利用循環(huán)對迭代器區(qū)間的元素挨個尾插。

//傳迭代器區(qū)間構造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last){push_back(*first);first++;}
}

---

拷貝構造函數(shù)

假設我們要用lt1去拷貝構造lt2。

• 傳統(tǒng)寫法：

我們首先復用empty_init對頭結點進行初始化，接著遍歷lt1的元素，在遍歷的過程中將lt1的元素尾插到lt2上即可。接著使用push_back自動開辟空間完成深拷貝。

//傳統(tǒng)寫法
list(const list<T>& lt)
{//先初始化lt2empty_init();//遍歷lt1，把lt1的元素push_back到lt2里面for (auto e : lt){push_back(e); //自動開辟新空間，完成深拷貝}
}

• 現(xiàn)代寫法：

這里我們先初始化lt2，然后把lt1引用傳參傳給lt，傳lt的迭代器區(qū)間構造tmp，復用swap交換頭結點指針即可完成深拷貝的現(xiàn)代寫法。

//現(xiàn)代寫法
list(const list<T>& lt)
{//先進行初始化empty_init();list<T>tmp(lt.begin(), lt.end());  //用迭代器區(qū)間去構造tmpswap(tmp);
}

---

賦值運算符重載函數(shù)?

對于賦值運算符的重載，我們?nèi)匀惶峁﹥煞N寫法：

• 傳統(tǒng)寫法

先調(diào)用clear函數(shù)將原容器清空，然后再將lt當中的數(shù)據(jù)通過遍歷的方式一個個尾插到清空后的容器當中即可。

//傳統(tǒng)寫法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) //避免自己給自己賦值{clear();  //清空容器for (const auto& e : lt){push_back(e); //將容器lt當中的數(shù)據(jù)一個個尾插到鏈表后面}}return *this; //支持連續(xù)賦值
}

• 現(xiàn)代寫法

利用編譯器機制，故意不使用引用傳參，通過編譯器自動調(diào)用list的拷貝構造函數(shù)構造出一個list對象lt，然后調(diào)用swap函數(shù)將原容器與該list對象進行交換即可。

//現(xiàn)代寫法
list<T>& operator=(list<T> lt) //編譯器接收右值的時候自動調(diào)用其拷貝構造函數(shù)
{swap(lt); //交換這兩個對象return *this; //支持連續(xù)賦值
}

---

析構函數(shù)

我們可以先復用clear函數(shù)把除了頭結點的所有結點給刪除掉，最后delete頭結點即可。

//析構函數(shù)
~list()
{clear();delete _head; //刪去哨兵位頭結點_head = nullptr;
}

---

4.2、迭代器相關函數(shù)

begin和end

• begin的作用是返回第一個位置的結點的迭代器，而第一個結點就是哨兵位頭結點的下一個結點。因此我們直接返回_head的_next即可。
• end的作用是返回最后一個有效數(shù)據(jù)的下一個位置的迭代器，對于list指的就是哨兵位頭結點_head的位置。

begin和end均分為普通對象調(diào)用和const對象調(diào)用，因此我們要寫兩個版本。

• 普通對象調(diào)用

//begin
iterator begin() //begin返回的就是第一個有效數(shù)據(jù)，即頭結點的下一個結點
{return iterator(_head->_next);//return _head->_next;
}//end
iterator end()
{return iterator(_head);//return _head;
}

• const對象調(diào)用

//begin
const_iterator begin() const
{return const_iterator(_head->_next);//return _head->_next; 
}
//end
const_iterator end() const
{return const_iterator(_head);//return _head;  也可以這樣寫
}

---

rbegin和rend

rbegin就是正向迭代器里的end()位置，rend就是正向迭代器里的begin()位置。

rbegin和rend同樣分為普通對象調(diào)用和const對象調(diào)用：

• 普通對象調(diào)用?

//rbegin()
reverse_iterator rbegin()
{return reverse_iterator(end());
}
//rend
reverse_iterator rend()
{return reverse_iterator(begin());
}

• const對象調(diào)用

//const反向迭代器
const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}

---

4.3、訪問容器相關函數(shù)?

front和back

front和back函數(shù)分別用于獲取第一個有效數(shù)據(jù)和最后一個有效數(shù)據(jù)，因此在實現(xiàn)front和back函數(shù)時，直接返回第一個有效數(shù)據(jù)和最后一個有效數(shù)據(jù)的引用即可。

• 普通對象調(diào)用

//front
T& front()
{return *begin(); //直接返回第一個有效數(shù)據(jù)的引用
}
T& back()
{return *(--end()); //返回最后一個有效數(shù)據(jù)的引用
}

• const對象調(diào)用

const T& front() const
{return *begin(); //直接返回第一個有效數(shù)據(jù)的引用
}
const T& back() const
{return *(--end()); //返回最后一個有效數(shù)據(jù)的引用
}

---

4.4、增加的相關函數(shù)?

insert

實現(xiàn)insert首先創(chuàng)建一個新的結點存儲插入的值，接著取出插入位置pos處的結點指針保存在cur里面，記錄cur的上一個結點位置prev，先銜接prev和newnode，再鏈接newnode和cur即可，最后返回新插入元素的迭代器位置。

• list的insert不存在野指針失效的迭代器失效問題。

//頭插
void push_front(const T& x)
{insert(begin(), x);
}
//insert，插入pos位置之前
iterator insert(iterator pos, const T& x)
{Node* newnode = new Node(x);//創(chuàng)建新的結點Node* cur = pos._node; //迭代器pos處的結點指針Node* prev = cur->_prev;//prev newnode cur//鏈接prev和newnodeprev->_next = newnode;newnode->_prev = prev;//鏈接newnode和curnewnode->_next = cur;cur->_prev = newnode;//返回新插入元素的迭代器位置return iterator(newnode);
}

---

push_back尾插

• 法一

首先要創(chuàng)建一個新結點用來存儲尾插的值，接著找到尾結點。將尾結點和新結點前后鏈接并將頭結點和新結點前后鏈接構成循環(huán)即可。

//尾插
void push_back(const T& x)
{Node* tail = _head->_prev; //找尾Node* newnode = new Node(x); //創(chuàng)建一個新的結點//_head tail newnode//鏈接tail和newnodetail->_next = newnode;newnode->_prev = tail;//鏈接newnode和頭結點_headnewnode->_next = _head;_head->_prev = newnode;
}

• 法二

這里也可以直接復用insert函數(shù)，當insert中的pos位置為哨兵位頭結點的位置時，實現(xiàn)的就是尾插。

//尾插
void push_back(const T& x)
{//法二：復用insertinsert(end(), x);
}

---

push_front頭插?

直接復用insert函數(shù)，當pos位置為begin()時，獲得的pos就是第一個有效結點數(shù)據(jù)，即可滿足頭插。

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

---

4.5、刪除的相關函數(shù)?

erase

erase刪除的是pos位置的結點。我們首先取出pos位置的結點指針cur，記錄cur上一個結點位置為prev，再記錄cur下一個結點位置為next，鏈接prev和next，最后delete釋放掉cur的結點指針即可。返回刪除元素后一個元素的迭代器位置。

//erase
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev cur next//鏈接prev和nextprev->_next = next;next->_prev = prev;//delete要刪除的結點delete cur;//返回刪除元素后一個元素的迭代器位置//return next;return iterator(next);
}

---

pop_back尾刪?

直接復用erase即可，當pos位置為--end()時，pos就是最后一個結點的位置，實現(xiàn)的就是尾刪。

//尾刪
void pop_back()
{erase(--end());
}

---

pop_front頭刪?

直接復用erase即可，當pos位置為begin()時，pos就是第一個有效數(shù)據(jù)，實現(xiàn)的就是頭刪。

//頭刪
void pop_front()
{erase(begin());
}

---

4.6、其他函數(shù)

size

size函數(shù)用于獲取當前容器當中的有效數(shù)據(jù)個數(shù)，因為list是鏈表，所以我們只能通過遍歷的方式逐個統(tǒng)計有效數(shù)據(jù)的個數(shù)。

//size
size_t size()const
{size_t sz = 0; //統(tǒng)計有效數(shù)據(jù)個數(shù)const_iterator it = begin(); //獲取第一個有效數(shù)據(jù)的迭代器while (it != end()) //通過遍歷統(tǒng)計有效數(shù)據(jù)個數(shù){sz++;it++;}return sz; //返回有效數(shù)據(jù)個數(shù)
}

---

resize

?resize函數(shù)的規(guī)則：

• 若當前容器的size小于所給n，則尾插結點，直到size等于n為止。
• 若當前容器的size大于所給n，則只保留前n個有效數(shù)據(jù)。

當我們實現(xiàn)resize函數(shù)時，我們不要直接調(diào)用size函數(shù)獲取當前容器的有效數(shù)據(jù)個數(shù)，因為當我們調(diào)用resize函數(shù)后就已經(jīng)遍歷了一次容器。如果結果是size大于n，那么還需要遍歷容器，找到第n個有效結點并釋放之后的結點。

這里實現(xiàn)resize的方法是：設置一個變量len，用于記錄當前所遍歷的數(shù)據(jù)個數(shù)，然后開始遍歷容器，在遍歷的過程中：

1. 當len大于或者是等于n時遍歷結束，此時說明該結點后的結點都應該被釋放，將之后的結點釋放即可。
2. 遍歷完容器，此時說明容器當中的有效數(shù)據(jù)個數(shù)小于n，則需要尾插結點，直到容器當中的有效數(shù)據(jù)個數(shù)為n時停止尾插即可。

void resize(size_t n, const T& val = T())
{iterator i = begin();  //獲取第一個有效數(shù)據(jù)的迭代器size_t len = 0;  //記錄當前所遍歷的數(shù)據(jù)個數(shù)while (len < n && i != end()){len++;i++;}if (len == n) //說明容器當中的有效數(shù)據(jù)個數(shù)大于或者是等于n{while (i != end()) //只保留前n個有效數(shù)據(jù){i = erase(i); //接收下一個數(shù)據(jù)的迭代器}}else  //說明容器當中的有效數(shù)據(jù)個數(shù)小于n{while (len < n){push_back(val);len++;}}
}

---

clear?

clear函數(shù)用于清空容器，我們通過遍歷的方式，逐個刪除結點，只保留頭結點即可。

void clear()
{iterator it = begin();while (it != end()){it = erase(it); //用it接收刪除后的下一個結點的位置}
}

---

empty

empty函數(shù)用于判斷容器是否為空，我們直接判斷該容器的begin函數(shù)和end函數(shù)所返回的迭代器是否是同一個位置的迭代器即可。(此時說明容器當中只有一個頭結點)

bool empty()const
{return begin() == end(); //判斷是否只有頭結點
}

---

empty_init空初始化

?該函數(shù)的作用是哨兵位的頭結點開出來，再對其進行初始化。該函數(shù)是庫里面的。

//空初始化  對頭結點進行初始化
void empty_init()
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}

---

swap交換?

對于鏈表的swap，我們直接交換頭結點指針的指向即可完成。直接復用庫函數(shù)的swap即可。

//swap交換函數(shù)
void swap(list<T>& lt)
{std::swap(_head, lt._head);//交換頭指針
}