STL容器-- list的模擬實現(附源碼)
List的實現主要時考察我們對list這一容器的理解,和代碼的編寫能力,通過上節對list容器的使用,我們對list容器已經有了一些基本的了解·,接下來就讓我們來實現一些list容器常見的功能函數來加深我們對c++工程的理解:

一、基本框架的搭建
首先我們需要將基本的框架搭建好, 從之前我們學數據結構時,對list的一些認識并結合c++ stl標準可以得出:
- 定義節點的構造
- 明確指針的指向
- list的封裝
根據c++中的便準我們可以的位置,list時一個雙向迭代器, 所以對應的, 我們需要定義的雙向循環鏈表:
1.1節點的構造
template <class T>
struct ListNode
{T _data;ListNode<T>* _next;ListNode<T>* _prev;// 節點的構造函數ListNode(const T& val):_data(val),_next(nullptr),_prev(nullptr){}
};
在定義一個節點的時候,我們先讓這個節點的_next and _prev指針為空
1.2 list的封裝
template <class T>
struct ListNode
{T _data;ListNode<T>* _next;ListNode<T>* _prev;// 節點的構造函數ListNode(const T& val = T()):_data(val),_next(nullptr),_prev(nullptr){}
};template<class T>
class list
{
public:typedef ListNode<T> node;void empty_init(){// zdl :: 在初始化一個空鏈表時, 先定義一個哨兵位_head = new node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}// functon define:}private:node* _head;
};
同時為了方式訪問沖突,我們可以將我們自己實現的類,放在我們自己定義的命名域中:
namespace zdl
{template <class T>struct ListNode{T _data;ListNode<T>* _next;ListNode<T>* _prev;// 節點的構造函數ListNode(const T& val):_data(val),_next(nullptr),_prev(nullptr){}};template <class T>struct ListNode{T _data;ListNode<T>* _next;ListNode<T>* _prev;// 節點的構造函數ListNode(const T& val = T()):_data(val),_next(nullptr),_prev(nullptr){}};template<class T>class list{public:typedef ListNode<T> node;void empty_init(){// zdl :: 在初始化一個空鏈表時, 先定義一個哨兵位_head = new node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}// functon define:}private:node* _head;};
}
這樣list的基本框架就搭建好了!!
二、節點的尾插和頭插
2.1 節點的頭插 (push_back)

通過前面數據結構的學習。我們已經清楚了鏈表的結構,在進行數據尾插時, 就只是在改變指針的指向罷了:
void push_back(const T& val){node* creat = new node(val);node* tail = _head->_prev;tail->_next = creat;creat->_prev = tail;creat->_next = _head;_head->_prev = creat; }
2.2 節點的頭插(push_front)
節點的頭插和尾插十分的相似,
這里我們就直接展示一下代碼:
void push_front(const T& val){node* fnode = new node(val);fnode->_next = _head->_next;fnode->_prev = _head;_head->_next->_prev = fnode;_head->_next = fnode;}
2.3 數據插入驗證
為了方便起見, 我這里再再這個類里面定義一個打印鏈表的函數:
void Print_list(){node* cur = _head->_next;while (cur != _head){cout << cur->_data << " ";cur = cur->_next;}cout << endl;}
完成了list容器的頭插和尾插操作接下來我們可以來驗證一下,我們的函數實現是否有問題:
#include"list.h"int main()
{zdl::list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_front(3);l1.Print_list();return 0;
}
通過運行可知, 這里的函數沒有問題:

三、list迭代器的實現
list迭代器的功能和vetor的功能有很多相似的地方,但是二者在底層實現時,使用的不同的方法:
基于,list迭代器的特殊性質,我們會采用類封裝的方式來滿足list_iterator的特殊性質:
3.1迭代器基本功能的實現和封裝處理
template<class T>struct list_iterator{typedef ListNode<T> node;typedef list_iterator<T> self;node* _nd;list_iterator(node* nd):_nd(nd){}// zdl:: 實現迭代器的基本功能:// 解引用數值T& operator*(){return _nd->_data;}// zdl:: 前置++ / --self& operator++(){_nd = _nd->_next;return *this;}self& operator--(){_nd = _nd->_prev;return *this;}// zdl:: 后置 ++ / --self operator++(int){self tmp = _nd;_nd = _nd->_next;return tmp;}self operator--(int){self tmp = _nd;_nd = _nd->_prev;return tmp;}// zdl:: != 運算bool operator!=(const self& s){return _nd != s._nd;}};
實現了list_iterator的功能后,我們就只需要將他封裝道list類中就可以正常使用了:


基本的邏輯都是十分的簡單的接下來我們來簡單的驗證一代碼是否可行:

3.2 對結構體(類)的解引用
對
->運算符的重載
大家現在可以想象一下這樣的場景,假設我現在在llist中存儲的不是基礎類型的元素,而是類等較為復雜的對象時,我們應當怎么正常的使用這個類對象的成員呢?
這時,我們就可以考慮對->運算符重載, 通過返回對象的地址,來訪問成員變量和成員函數等!
下面我們就來舉個例子:
假設我現在我要在list中存儲pos類:
struct pos
{int row;int col;//構造函數pos(const int& x = 0, const int& y = 0):row(x),col(y){}//成員函數void pos_show(){printf("(%d, %d) ",row, col);}
};
我們就只需要重載->運算符:
T* operator->()
{return &_nd->_data;
}
運行后可以得到:

但是大家可能會覺得很奇怪,通過->重載,返回的只是_data的地址,為什么能直接訪問到元素呢?不應該使用it->->解引用兩次才行啊?
這個其實就只是c++便準下為我們提供的特殊語法, 通過這樣的規定使我們能夠直接訪問到元素, 當然c++也是支持這樣的寫法的:

但是不支持這樣的寫法:

3.3const迭代器的實現與模板參數的巧用
前面我們已經實現了,可讀可寫的迭代器,現在我們就來實現一下只讀迭代器:
const iterator,
其實從功能上看,這個迭代器與原來的迭代器十分的相似,只是不能對指向對象的值進行修改,因此我們就只需要對* 和 ->運算符重載的時候稍加修改就可以得到我們想要的結果,即再創建一個類:

其他的共同功能粗需要改動,只需要改動下面兩個重載函數:
const T& operator*()
{return _nd->_data;
}
const T* operator->()
{return &_nd->_data;
}
緊接著我們還需要在llist類中實現const對象專用的begin()、end()


接下來我們來驗證一下效果:

現在consr iterator也實現好了,但是這里依然還存在問題,這樣我們將相當于為迭代器實現了兩個類,這兩個類的攻擊能還高度重合,這并沒有,體現出模板函數的簡潔性,因此我們還可以通過其他的方式來優化我們現在的代碼。
通過對源碼的分析,參照我們或許可以從中得到一些啟發, 從源碼中可知我們可以得知,通過對模板參數的巧用就可以的實現代碼的簡化:

接下來我們就只需要將代碼稍加改動就可以實現我們的目的:


接下來,我們再次運行看看是否可以達到簡化代碼的效果:

可以發現現在的代碼依然有效,代碼簡化成功!!
四、豐富構造函數、list增刪查改的實現
現在我們已經完成了list的簡單構造函數,現在我們就可以參照 c++ library完成其他的構造函數:
4.1 list(size_t n, const T& x = T())
我們要實現的這個函數和標準庫中的一樣,并且直接復用我峨嵋你已經實現的函數就好了:
list(size_t n, const T& x = T())
{for (int i = 0; i < n; i++){push_back(x);}
}
直接來演示一下的效果:

4.2 拷貝構造
我們就只需要將被拷貝鏈表的元素一個一個的拷貝進鏈表就行了:
list(const list<T>& l1)
{empty_init();for (auto& e : l1) push_back(e);
}
我們來測試一下效果:

4.3 插入函數的實現(insert)
想要在這個雙向鏈表中插入節點,我們就需要
-
待插入的值
-
待插入位置
所以,insert函數定義為: void insert(iterator pos, const T& val = T())
iterator insert(iterator pos, const T& val = T())
{node* cur = pos._nd;node* prev = pos._nd->_prev;node* insrt = new node(val);prev->_next = insrt;insrt->_prev = prev;insrt->_next = cur;cur->_prev = insrt;return iterator(cur->_prev);}
這個函數也十分的簡單如果,有的uu還沒有接觸過鏈表,或者是已經忘了鏈表的增刪查改,可以移步去看看我之前的博客:鏈表的介紹
4.4鏈表的刪除(earse)
關于erase和函數的定義,我們就只需要拿到需要刪除的位置就可以了, 所以定義為:void erase(iterator pos)
iterator erase(iterator pos)
{assert(pos != end()); //! 注意不能夠將哨兵位刪除!!node* cur = pos._nd;node* prev = cur->_prev;prev->_next = cur->_next;cur->_next->_prev = prev;delete cur;return iterator(prev->_next);}
現在我們就直接來測試一下這個函數是否可以滿足我們的要求:

由此可知我們實現的都沒有問題。
4.5鏈表元素的查找(find)
定義find函數時,我們就只需要給函數一個特定的需要查找到的值,然后使這個函數返回這個元素的位置(迭代器)
iterator find(const T& val)
{auto it = begin();while (it != end() && *it != val){it++;}if (*it == val) return it;return nullptr;}

4.6 頭刪和尾刪操作
前面我們已經實現了earse 現在我們就只需要對這個和拿書盡心你給復用就好了:
void pop_front()
{erase(++end());
}
void pop_back()
{erase(--end());
}
接下來我們就直接來演示這個函數是否有用:

五、析構函數與clear函數
最后我們就來實現一下list的析構函數,我們還是繼續函數的復用:
// zdl:: 析構類函數的實現:~list(){// ! 不僅要將所有的數值刪除還需要將哨兵位也清除!clear();delete _head;_head = nullptr; }void clear(){// !! 不能刪除哨兵位,就只是將所有的數值清空。auto it = begin();while (it != end()) it = erase(it);}
現在我們就將已有的鏈表清空試試:

六、代碼展示
list.h
#pragma once #include<iostream>
#include<cassert>
using namespace std;
namespace zdl
{template <class T>struct ListNode{T _data;ListNode<T>* _next;ListNode<T>* _prev;// 節點的構造函數ListNode(const T& val = T()):_data(val),_next(nullptr),_prev(nullptr){}};template<class T, class Ref, class Ptr>struct list_iterator{typedef ListNode<T> node;typedef list_iterator<T, Ref, Ptr> self;node* _nd;list_iterator(node* nd):_nd(nd){}// zdl:: 實現迭代器的基本功能:// 解引用數值Ref operator*(){return _nd->_data;}Ptr operator->(){return &_nd->_data;}// zdl:: 前置++ / --self& operator++(){_nd = _nd->_next;return *this;}self& operator--(){_nd = _nd->_prev;return *this;}self& operator+(size_t n){while (n--){_nd = _nd->_next;}return *this;}self& operator-(size_t n){while (n--){_nd = _nd->_prev;}return *this;}// zdl:: 后置 ++ / --self operator++(int){self tmp = _nd;_nd = _nd->_next;return tmp;}self operator--(int){self tmp = _nd;_nd = _nd->_prev;return tmp;}// zdl:: != 運算bool operator!=(const self& s){return _nd != s._nd;}};template<class T>class list{public:typedef ListNode<T> node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;void empty_init(){// zdl :: 在初始化一個空鏈表時, 先定義一個哨兵位_head = new node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}list(const list<T>& l1){empty_init();for (auto& e : l1) push_back(e);}list(size_t n, const T& x = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(x);}}void push_back(const T& val){node* creat = new node(val);node* tail = _head->_prev;tail->_next = creat;creat->_prev = tail;creat->_next = _head;_head->_prev = creat; }void push_front(const T& val){node* fnode = new node(val);fnode->_next = _head->_next;fnode->_prev = _head;_head->_next->_prev = fnode;_head->_next = fnode;}void Print_list(){node* cur = _head->_next;while (cur != _head){cout << cur->_data << " ";cur = cur->_next;}cout << endl;}// zdl:: 增刪查改的實現iterator insert(iterator pos, const T& val = T()){node* cur = pos._nd;node* prev = pos._nd->_prev;node* insrt = new node(val);prev->_next = insrt;insrt->_prev = prev;insrt->_next = cur;cur->_prev = insrt;return iterator(cur->_prev);}iterator erase(iterator pos){assert(pos != end()); //! 注意不能夠將哨兵位刪除!!node* cur = pos._nd;node* prev = cur->_prev;prev->_next = cur->_next;cur->_next->_prev = prev;delete cur;return iterator(prev->_next);}iterator find(const T& val){auto it = begin();while (it != end() && *it != val){it++;}if (*it == val) return it;return nullptr;}void pop_front(){erase(begin());}void pop_back(){erase(--end());}// zdl:: 析構類函數的實現:~list(){// ! 不僅要將所有的數值刪除還需要將哨兵位也清除!clear();delete _head;_head = nullptr; }void clear(){// !! 不能刪除哨兵位,就只是將所有的數值清空。auto it = begin();while (it != end()) it = erase(it);}
// zdl:: 使用類來模擬迭代器的行為iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}private:node* _head;};
}
test.cpp
#include"list.h"
#include<list>
struct pos
{int row;int col;//構造函數pos(const int& x = 0, const int& y = 0):row(x),col(y){}//成員函數void pos_show(){printf("(%d, %d) ",row, col);}
};
int main()
{// zdl::list<pos> l1;// pos p[] = {{1, 2}, {3, 4}, {5, 6}};// for (int i = 0; i < 3; i++) l1.push_back(p[i]);// auto it = l1.begin();// while (it != l1.end())// {// it->pos_show();// it++;// cout << endl;// }// cout << endl;// zdl::list<int> l2(5, 4);// for (auto&i : l2) cout << i << " ";// cout << endl;// zdl::list<int> l4(3, 3);// l4.Print_list();// l4.insert(l4.begin() + 2, 2);// l4.Print_list();// l4.erase(l4.begin() + 2);// l4.Print_list();// zdl::list<int>l5;// for (int i = 1; i <= 10; i++) l5.push_back(i);// cout << "原數組:" << endl;// l5.Print_list();// // zdl:: 現在我們要借助 find + erase函數來刪除元素:5// l5.erase(l5.find(5));// cout << "刪除后:" << endl;// l5.Print_list();// zdl:: 進行頭刪和尾刪// cout << "進行尾刪和頭刪后:" << endl;// l5.pop_back();// l5.pop_front();// l5.Print_list();// cout << "現在將所有的元素都刪除!" << endl;// l5.clear();// l5.Print_list();zdl::list<int> l1(10, 10);cout <<"l1:" << endl;l1.Print_list();zdl::list<int> l2(l1);cout << "l2:" << endl;l2.Print_list();return 0;
}
好,常用的接口我們就實現了,list學習到此告一段落,再見!!