送給大家一句話(huà)：
若結(jié)局非你所愿，就在塵埃落定前奮力一搏。—— 《夏目友人帳》
1 前言
List是C++標(biāo)準(zhǔn)模板庫(kù)(STL)中的一個(gè)成員，其本質(zhì)為帶頭雙向循環(huán)鏈表。不同于連續(xù)的、緊密排列的數(shù)組容器Vector，List容器的內(nèi)部是由雙向鏈表構(gòu)成的，使得它在插入和刪除操作上，就如同行云流水一般順暢，不需移動(dòng)其它元素。
1.1 底層結(jié)構(gòu)
List容器的底層結(jié)構(gòu)，是一個(gè)經(jīng)典的帶頭雙向循環(huán)鏈表。每個(gè)節(jié)點(diǎn)包含：
- 數(shù)據(jù)
- 指向前一個(gè)節(jié)點(diǎn)的指針
- 指向后一個(gè)節(jié)點(diǎn)的指針。
這種結(jié)構(gòu)賦予了List靈動(dòng)的特性：它能夠輕松地在任意位置增加或移除元素，而這種操作幾乎是與容器大小無(wú)關(guān)的，體現(xiàn)了時(shí)間復(fù)雜度上的優(yōu)勢(shì)。但這種優(yōu)勢(shì)的代價(jià)是，與數(shù)組相比，List在訪(fǎng)問(wèn)元素時(shí)的速度會(huì)較慢，因?yàn)樗枰獜念^開(kāi)始遍歷。這也決定了list的更適合頻繁插入的動(dòng)態(tài)數(shù)據(jù)。
來(lái)看STL源碼中的節(jié)點(diǎn)結(jié)構(gòu)：
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
1.2 使用場(chǎng)景
List最適合的場(chǎng)景是那些需要頻繁進(jìn)行插入和刪除操作的場(chǎng)合。
例如，如果你正在管理一個(gè)動(dòng)態(tài)變化的列表，如任務(wù)調(diào)度、人員排隊(duì)等場(chǎng)景，List的特性將大放異彩。但是如果你的應(yīng)用場(chǎng)景更多地需要隨機(jī)訪(fǎng)問(wèn)元素，那么向量（Vector）或者數(shù)組可能是更佳的選擇。因?yàn)長(zhǎng)ist的順序訪(fǎng)問(wèn)性能相比之下會(huì)顯得有些力不從心。
- 所以如果需要頻繁隨機(jī)的訪(fǎng)問(wèn)數(shù)據(jù)，那么選擇vector容器
- 如果需要頻繁插入刪除數(shù)據(jù)，那么選擇list容器
- 排序不要選擇list ！??！其刪除節(jié)點(diǎn)的過(guò)程就決定了其速度不會(huì)太快。
1.3 功能簡(jiǎn)介
功能簡(jiǎn)介我們可以參考STL官方庫(kù) :list文檔介紹
- 插入與刪除：List的插入和刪除操作非常高效，它可以在任意位置快速地添加或移除元素，而不需要像連續(xù)內(nèi)存容器那樣進(jìn)行大量元素的移動(dòng)。
- 多種構(gòu)造：類(lèi)都應(yīng)該包含多種構(gòu)造函數(shù)
- 支持迭代器：迭代器是C++重要的特性，我們寫(xiě)的list 也一定要支持迭代器。
2 框架搭建
現(xiàn)在我們開(kāi)始實(shí)現(xiàn)list 容器，首先先要思考一下框架結(jié)構(gòu)：
- 首先我們需要一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體（類(lèi)似源碼中的節(jié)點(diǎn)）
- 其次我們的list 類(lèi)要帶一個(gè)頭結(jié)點(diǎn)，讓我們更方便進(jìn)行插入刪除操作
基本就是這樣，現(xiàn)在我們開(kāi)始手搓
2.1 節(jié)點(diǎn)類(lèi)
// 節(jié)點(diǎn) 結(jié)構(gòu)體
template<class T>
struct ListNode
{
ListNode* _next;
ListNode* _prev;
T _data;
ListNode(T x = T()) :
_next(nullptr),
_prev(nullptr),
_data(x)
{}
//ListNode(T x = T())
//{
// _next = nullptr;
// _prev = nullptr;
// _data = x;
//}
~ListNode()
{
_next = nullptr;
_prev = nullptr;
}
};
這里使用模版來(lái)適配更多的情景，然后基本的數(shù)據(jù)，前后指針都很簡(jiǎn)單。在編寫(xiě)一個(gè)構(gòu)造函數(shù)，==構(gòu)造函數(shù)使用初始化列表，并不是必須使用。析構(gòu)函數(shù)避免野指針出現(xiàn)，將指針賦值為nullptr就可以了。
2.2 list 類(lèi)
我們先進(jìn)行簡(jiǎn)單的框架書(shū)寫(xiě)，構(gòu)造函數(shù)需要?jiǎng)?chuàng)建一個(gè)頭結(jié)點(diǎn)，因?yàn)槲覀円獎(jiǎng)?chuàng)建雙向循環(huán)鏈表，所以頭尾都要指向頭結(jié)點(diǎn)本身。 _size賦初值。
template<class T>
class list
{
public:
//設(shè)置適配的節(jié)點(diǎn)
typedef ListNode<T> Node;
//空初始化
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//構(gòu)造函數(shù)
list() :
_head(nullptr)
{
empty_init();
}
private:
Node* _head;
size_t _size;
};
接下來(lái)我們來(lái)逐步完成功能書(shū)寫(xiě)，由于我們還沒(méi)有進(jìn)行迭代器的書(shū)寫(xiě)
2.3 迭代器類(lèi)
我們思考一下這里能不能使用原生指針來(lái)完成迭代器的操作（++ == != --）當(dāng)然是不能的，因?yàn)殒湵淼奈锢淼刂凡⒉皇沁B續(xù)的，對(duì)原生指針的++或–操作是沒(méi)有意義的，所以我們需要自行編寫(xiě)迭代器類(lèi)，對(duì)原生指針進(jìn)行封裝，來(lái)滿(mǎn)足我們特殊的++和–操作。
//這里的模板可以再次升級(jí) 先簡(jiǎn)單寫(xiě)一下
template<class T>
class ListIterator
{
public:
//重命名方便書(shū)寫(xiě)
typedef ListNode<T> Node;
typedef ListIterator<T> Self;
Node* _node;
ListIterator(Node* x ):
_node(x)
{}
//操作符重載 前置++ 與 后置++的區(qū)別是參數(shù)是否帶（int）
//++t
Self operator++()
{
_node = _node->_next;
return *this;
}
//t++
Self operator++(int)
{
Self tmp(*this);//淺拷貝即可
_node = _node->_next;
return tmp;
}
//--t
Self operator--()
{
_node = _node->_prev;
return *this;
}
//t--
Self operator--(int)
{
Self tmp(*this);//淺拷貝即可
_node = _node->_prev;
return tmp;
}
//判斷是否相等 比較指針地址是否相同即可
bool operator!=(const Self& it)
{
return _node != it._node;
}
//判斷是否相等 比較指針地址是否相同即可
bool operator==(const Self& it)
{
return _node == it._node;
}
// 解引用操作 *it 返回節(jié)點(diǎn)數(shù)據(jù)的引用 可以進(jìn)行修改
T& operator*()
{
return _node->_data;
}
//因?yàn)橹羔槻拍苁褂?> 所以->要返回地址（指針）
T* operator->()//編譯器會(huì)進(jìn)行省略->
{
return &_node->_data;
}
};
這樣迭代器類(lèi)就大致寫(xiě)好了，那么一般我們的迭代器應(yīng)該還要支持const，不然我們傳入一個(gè)不可修改的鏈表（const list l）,就會(huì)反生報(bào)錯(cuò)，那么我們還要書(shū)寫(xiě)一份const版的迭代器。如果進(jìn)行編寫(xiě)，那么是不是會(huì)有大部分與剛才我們書(shū)寫(xiě)的迭代器重復(fù)（++ -- == != 都是一樣的），只有operator*()和operator->()返回值不一致：
- 因?yàn)槭浅５鳎褂脠?chǎng)景是對(duì)
const list<T> l進(jìn)行操作，那么節(jié)點(diǎn)數(shù)據(jù)不可改變，所以不影響++ -- == !=這些操作，受影響的是operator*()和operator->()返回值（該情況下鏈表本身是只讀的，又因?yàn)椴荒軐?quán)限進(jìn)行擴(kuò)大，所以返回值應(yīng)該也是只讀的（const））。 - 那這樣就發(fā)現(xiàn)了不同常迭代器應(yīng)該為
const T& operator*()和const T* operator->(),所以有沒(méi)有一種辦法可以簡(jiǎn)單解決呢，當(dāng)然有了，我們?cè)O(shè)置一個(gè)新模版（帶有三個(gè)參數(shù)），創(chuàng)建的時(shí)候就傳入對(duì)應(yīng)參數(shù)
我們將模版修改為這樣，
//reference 引用 pointer 指針
template<class T , class Ref ,class Ptr>
對(duì)應(yīng)返回值也改變：
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
那么類(lèi)實(shí)例化的時(shí)候傳入對(duì)應(yīng)參數(shù)就好了：
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
這樣就實(shí)現(xiàn)了迭代器的創(chuàng)建，是不是就非常簡(jiǎn)潔了呢
3 功能實(shí)現(xiàn)
3.1 begin() 與 end()
使用迭代器即可，注意end()是頭結(jié)點(diǎn)，因?yàn)楸闅v過(guò)程中，全部遍歷后會(huì)回到頭結(jié)點(diǎn)，所以直接判斷是否為頭結(jié)點(diǎn)就能控制結(jié)束位置。
//普通迭代器
typedef ListIterator<T, T&, T*> iterator;
//常迭代器
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin() { return _head->_next; }
iterator end() { return _head; }
const_iterator begin() const { return _head->_next; }
const_iterator end() const { return _head; }
3.2 插入操作
插入操作我們很熟悉，步驟是創(chuàng)建一個(gè)新節(jié)點(diǎn)，然后通過(guò)改變指針指向來(lái)完成插入操作：
來(lái)看尾插操作，
void push_back(const T& x = T())
{
//創(chuàng)建新節(jié)點(diǎn)
Node* node = new Node(x);
//找尾
Node* tail = _head->_prev;
//進(jìn)行插入
node->_next = _head;
node->_prev = tail;
tail->_next = node;
_head->_prev = node;
//別忘記大小++
_size++;
}
任意位置插入，操作思路依然是對(duì)前后節(jié)點(diǎn)與新節(jié)點(diǎn)的指針指向進(jìn)行操作，來(lái)完成插入。
void insert(iterator pos = begin(), T x = T())
{
//創(chuàng)建新節(jié)點(diǎn)
Node* node = new Node(x);
//前節(jié)點(diǎn) 后節(jié)點(diǎn)
Node* prev = pos._node->_prev;
Node* next = pos._node;
//處理新節(jié)點(diǎn)
node->_prev = prev;
node->_next = next;
//出現(xiàn)前后節(jié)點(diǎn)
prev->_next = node;
next->_prev = node;
//別忘記大小++
_size++;
}
頭插，直接干脆調(diào)用insert就可以了
void push_front(const T& x = T())
{
insert(begin(), x);
}
3.3 刪除操作
刪除操作，同樣是使用指針操作，來(lái)達(dá)到刪除的效果。注意要對(duì)刪除的節(jié)點(diǎn)進(jìn)行釋放空間操作（delete），不然會(huì)發(fā)生內(nèi)存泄漏?。?！
尾刪
void pop_back()
{
Node* tail = _head->_prev;
Node* prev = tail->_prev;
prev->_next = _head;
_head->_prev = prev;
delete tail;
_size--;
}
//頭刪
void pop_front()
{
Node* head = _head->_next;
Node* next = head->_next;
_head->_next = next;
next->_prev = _head;
delete head;
_size--;
}
//任意位置刪除
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return iterator(next);
}
需要注意的是，任意位置刪除因?yàn)槭褂昧说鳎瑒h除后會(huì)造成迭代器失效，所以需要更新迭代器，返回被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的迭代器即可。
3.4 拷貝構(gòu)造
拷貝構(gòu)造直接將數(shù)據(jù)一個(gè)一個(gè)插入到該鏈表中即可：
list(const list<T>& l)
{
empty_init();
iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
it++;
}
}
這樣十分方便快捷?。?！
3.5 析構(gòu)函數(shù)
void clear()
{
//依次釋放
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
//需要單獨(dú)釋放頭結(jié)點(diǎn)空間
delete _head;
_head = nullptr;
}
3.6 其他函數(shù)
返回大?。?/p>
size_t size() const { return _size; }
判斷是否為空：
bool empty()
{
return _size == 0;
}
清空數(shù)據(jù)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-846832.html
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
4 總結(jié)
本文我們實(shí)現(xiàn)了STL庫(kù)中重要的list 的模擬實(shí)現(xiàn)，其中最重要莫過(guò)于迭代器的封裝類(lèi)的書(shū)寫(xiě)，這是前所未有的操作（對(duì)于我來(lái)說(shuō)，我是第一次使用這種結(jié)構(gòu)）。通過(guò)list 的模擬實(shí)現(xiàn)也幫我們鞏固了類(lèi)與對(duì)象的知識(shí)，也強(qiáng)化了指針操作的思路。歡迎大家討論分析。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-846832.html
Thanks?(?ω?)?謝謝閱讀?。。?/h2>
下一篇文章見(jiàn)?。?！
到了這里，關(guān)于【C++】手搓 list 容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
