溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“C++ list怎么實現”，在日常操作中，相信很多人在C++ list怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++ list怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
對于鏈表的節點我們都很熟悉了，節點中包含兩個域，一個指針域一個數據域，為了讓list能夠通用，我們選擇使用模板。
節點的結構如下：
template<class T>
//struct也能定義類，默認類的訪問限定符是 public
struct list_node
{
//這個指針指向前一個節點
list_node<T>* _prev;
//這個指針指向后一個節點
list_node<T>* _next;
//這個是數據域中的元素
T _data;
//對節點使用匿名對象進行初始化
list_node(const T& data = T())
:_prev(nullptr)
,_next(nullptr)
,_data(data)
{}
};現在我們已經有了節點了，我們還要有迭代器，如果沒有迭代器我們就不能很好的訪問每一個節點。
對于迭代器我們要讓它指向我們想要的節點，這才能便于我們的訪問，于是很明顯我們迭代器的成員變量就要是一個節點的指針！同時為了讓list能夠通用，我們選擇使用模板來定義迭代器。
迭代器的結構如下：
//這里后面的兩個參數，在實際應用時通常是T& , T* 或者是 const T& , const T*
//根據加與不加const 可以分別實例化出：普通正向迭代器與正向const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
//將節點的類型進行typedef方便使用
typedef list_node<T> node;
//將類自己進行typedef方便使用
typedef __list_iterator<T,Ref,Ptr> self;
//成員變量 是一個指向節點的指針
node* _pnode;
//構造函數 用一個節點的地址對迭代器進行初始化，
__list_iterator(node* pnode)
:_pnode(pnode)
{}
};由于list是帶頭雙向循環鏈表，我們只需要一個指向頭節點的指針便能夠管理所有的節點了。
template<class T>
class list
{
public:
//將節點的類型進行typedef方便使用
typedef list_node<T> node;
//將迭代器進行typedef方便使用
typedef __list_iterator<T, T&, T*> iterator;
//將const迭代器進行typedef方便使用
typedef __list_iterator<T, const T&, const T*> const_iterator;
//默認構造函數
list()
{
empty_init();
}
//初始化函數
void empty_init()
{
//申請一個頭節點，將節點的地址給_head
_head = new node;
//讓哨兵位節點的 前指針指向自己
_head->_prev = _head;
//讓哨兵位節點的 后指針指向自己
_head->_next = _head;
}
private:
//指向哨兵位節點的指針
node* _head;
};到此為止我們一共建立了三個類，下面我們模擬實現鏈表的各種接口時，我們還要繼續豐富迭代器類的接口與list類的接口
由于鏈表的許多操作都要用到迭代器，但是迭代器的一些其他接口我們還沒有實現，在這里我們來實現迭代器的所有接口。
對于原生指向節點的指針來說*運算符能讓我們拿到節點，但還無法拿到節點數據域中的數據，但是對于迭代器來說*運算符就要拿到容器中存儲的數據，所以我們還要對迭代器的*運算符進行重載。
// *運算符重載
Ref operator*()
{
//迭代器中的那個指針不能是nullptr
assert(_pnode);
//返回節點中的數據域中的數據
return _pnode->_data;
}++運算符分為兩種：一種是前置++一種是后置++，這兩個函數構成函數重載，后置++的參數部分會多一個int類型。（--運算符同理）
對于原生指向節點的指針來說：++指針是讓指針移動到下一個緊挨著的同類型的指針位置，但是對于迭代器來說：++是讓迭代器指向下一個節點的位置，這兩者并不匹配，所以我們要對++運算符進行函數重載。
//前置++運算符
self& operator++()
{
_pnode = _pnode->_next;
return (*this);
}
//后置++運算符
self operator++(int)
{
//先保存++之前的結果
self tmp(*this);
_pnode = _pnode->_next;
//返回++之前的值
return tmp;
}
//前置--運算符
self& operator--()
{
_pnode = _pnode->_prev;
return (*this);
}
//后置--運算符
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}雖然在前面我們已經實現了迭代器*的運算符重載，已經可以訪問數據域中的數據了。但是當我們的list里面存儲的是自定義類型的數據，而我們想要訪問自定義類型中的成員變量時迭代器*的運算符就不能夠幫到我們了。
例如：
struct Date
{
int _year;
int _month;
int _day;
}
//it是迭代器，指向了存儲了Date類型的節點
//假設:在沒有->操作符時,我們想要修改_year的值,
(*it)._year = 2023;
//如果有了-> 操作符，我們就能這樣操作，更加符合我們的使用習慣
it->_year = 2023;于是我們來實現：->運算符的重載，我們先來看代碼：
// ->運算符重載
Ptr operator->()
{
return &(_pnode->_data);
}看到這里你可能會覺得很奇怪，覺得這段代碼是錯誤的,下面我們就來詳細講解這里的問題和注意事項。
_pnode是迭代器的成員變量，是一個節點的指針，它使用的->是C++的內置類型的操作符，這段代碼(_pnode->date) 是拿到的是節點中存儲的數據，這段代碼&(_pnode->date) 是拿到的是節點中存儲的數據的地址，返回之后我們好像并沒有得到自定義類型中的數據，好像還差一次->操作，比如這樣：
it->->_year = 2023; //it-> 等價于 (&(_pnode->date)) //(&(_pnode->date))->year = 2023;
實際上按上面的運算符重載函數寫法確實是少了一次->，但是C++為了代碼的簡潔性在這里進行了特殊處理，我們寫->的運算符重載時只需要返回list里面自定義類型的地址就行了，在外面實際應用時，編譯器在編譯時會為我們自動加上一次->。
我們在使用迭代器進行遍歷數據的時候，經常要使用關系運算符 != ==來判斷條件是否達到，在這里我們對關系運算符 != ==進行函數重載。
判斷兩個迭代器是否相等的辦法就是兩個迭代器是不是指向同一個位置！
// !=運算符重載
bool operator!=(const self& s)
{
return _pnode != s._pnode;
}
// ==運算符重載
bool operator==(const self& s)
{
return _pnode == s._pnode;
}在實現完迭代器之后，我們就要實現list的其他接口了。
雖然在list的類外我們已經實現了迭代器的各種接口，但是list類內我們還沒有提供使用迭代器的接口的函數，這個函數就是我們常用的begin()與end()函數！下面我們來一起實現一下。
//正向迭代器
iterator begin()
{
//_head指向的是哨兵位的頭節點，_head的下一個才是第一個節點！
//這里使用的是一個指針構造的匿名對象做返回值，編譯器會對此進行優化，能夠增加效率
return iterator(_head->_next);
}
iterator end()
{
//由于是雙向循環鏈表，所以最后一個節點的下一個位置就是哨兵位節點
return iterator(_head);
}//const迭代器的思路與普通迭代器類似
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}list鏈表的插入很簡單，我們需要先申請一個新節點存儲我們想要插入的數據，然后將新節點的_prev指針指向前一個節點，同時新節點的_next指針指向當前節點。同時再對當前節點與前一個節點中相應的指針進行更新，就完成了指針的鏈接。
void insert(iterator pos, const T& x)
{
//先申請一個節點，存儲我們要插入的數據
node* new_node = new node(x);
node* prev = pos._pnode->_prev;
//鏈接過程
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = pos._pnode;
pos._pnode->_prev = new_node;
}插入函數寫完以后，我們的頭插尾插函數也就相當于寫完了
頭插函數
void push_front(const T& x)
{
//在begin()位置進行插入就是頭插！
insert(begin(), x);
}尾插函數
//尾插函數
void push_back(const T& x)
{
//在end()位置進行插入，就是尾插
insert(end(), x);
}鏈表的刪除沒有順序表那么復雜，但是我們應該注意：應該先將前后節點的連接關系給建立好，然后再刪除節點！
iterator erase(iterator pos)
{
assert(pos != end());
//鏈接過程
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
//刪除節點
delete pos._pnode;
//返回指向原節點的下一個節點的迭代器，外部接收后可以防止迭代器失效！
return iterator(next);
}同理刪除函數寫完以后，我們的頭刪尾刪函數也就相當于寫完了！
頭刪函數
void pop_front()
{
erase(begin());
}尾刪函數
void pop_back()
{
//由于end()是最后一個節點的下一個位置，所以這里要對end()進行一次自減運算
erase(--end());
}清除函數的作用就是刪除除了哨兵位節點以外所有節點，現在我們有了迭代器我們訪問每個節點都變得非常容易，刪除相應的節點也變的非常容易，我們只需要遍歷一遍鏈表逐一進行刪除就行了。
void clear()
{
list<T>::iterator it = begin();
while (it != end())
{
//erase函數刪除相應節點以后會返回下一個節點的迭代器
it = erase(it);
}
}對于鏈表的交換我們只需要交換list的成員變量中指向哨兵位節點的指針（即_head指針）就可以完成整個鏈表的交換了！
//swap函數
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}此函數的作用就是用一個迭代器的區間來構造一個鏈表，要實現這個函數我們只需要用迭代器進行遍歷，然后將遍歷到的數據一個一個尾插就能構成一個新的鏈表了，同時為了能夠支持更多的迭代器能夠去構造鏈表，我們可以將該函數變成一個函數模板。
//迭代器區間構造,傳入的迭代器應該至少是一個二元迭代器，能支持向前和向后遍歷，這時鏈表的最低要求。
template<class Biditerator>
list(Biditerator first, Biditerator last)
{
//調用初始化函數
empty_init();
//遍歷迭代器同時將數據形成一個新節點插入鏈表中
while (first != last)
{
push_back(*first);
++first;
}
}有了迭代器區間構造和交換函數我們就可以寫現代寫法的拷貝構造了！
現代寫法的拷貝構造就是用迭代器區間構造一個完整的鏈表，然后交換給拷貝對象。
//拷貝構造
list(const list<T>& lt)
{
//初始化
empty_init();
//用迭代器區間構造創建一個新的list對象
list<T> tmp(lt.begin(), lt.end());
//將this指針指向的對象與這個新的tmp對象進行交換，拷貝就變相完成了
swap(tmp);
}有了拷貝構造和交換函數，我們還是可以采用現代版本的賦值重載，原理與上面的拷貝構造同理。
//賦值運算符重載
//注意這里的傳參方式是傳值傳參
list<T>& operator=(list<T> lt)
{
//將this指針指向的對象與這個lt對象進行交換，賦值就變相完成了
swap(lt);
return (*this);
}最后就是析構函數了，由于我們已經實現過了clear函數，所以我們可以先調用clear函數刪除所有有效節點，然后再刪除哨兵位的節點就行了！
~list()
{
clear();
delete _head;
_head = nullptr;
}到此，關于“C++ list怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
