柚子快報激活碼778899分享：list結(jié)構(gòu)刨析與模擬實現(xiàn)
目錄
1.引言
2.C++模擬實現(xiàn)
2.1模擬實現(xiàn)結(jié)點
2.2模擬實現(xiàn)list前序
1）構(gòu)造函數(shù)
2）push_back函數(shù)
2.3模擬實現(xiàn)迭代器
1）iterator
構(gòu)造函數(shù)和析構(gòu)函數(shù)：
*操作符重載函數(shù)：
前置/后置++/--：
==/!=操作符重載函數(shù)：
->操作符重載函數(shù)：
2）const_iterator
2.4模擬實現(xiàn)list后序
3）insert函數(shù)
4）erase函數(shù)
5）頭插頭刪尾插尾刪函數(shù)
6）size函數(shù)
7）begin/end函數(shù)
8）clear函數(shù)
9）析構(gòu)函數(shù)
3.完整list
1.引言
先來說說為什么要模擬實現(xiàn)庫里的list？
我認(rèn)為，模擬實現(xiàn)list有以下幾個意義和好處:
1. 學(xué)習(xí)：通過自己實現(xiàn)一個類似于STL中的list數(shù)據(jù)結(jié)構(gòu)，可以加深對數(shù)據(jù)結(jié)構(gòu)和算法的理解。通過親自編碼實現(xiàn)，能更好地理解list的內(nèi)部工作原理，以及C++語言中與數(shù)據(jù)結(jié)構(gòu)相關(guān)的特性和語法。
2. 練習(xí)：編寫一個類似于STL中的list可以作為練習(xí)和提升編碼能力的手段。這有助于加強(qiáng)對C++語言的掌握，并提高面向?qū)ο缶幊痰募寄堋?/p>
3. 定制化需求：有時候，STL中提供的list功能不能完全滿足特定需求，此時可以通過自己實現(xiàn)一個list類來擴(kuò)展或定制list的功能，以更好地適應(yīng)特定的應(yīng)用場景。
2.C++模擬實現(xiàn)
? ? ? 提前聲明，由于list不同類型的函數(shù)重載太多太雜，本篇僅僅模擬實現(xiàn)簡單的構(gòu)造，析構(gòu)，操作符重載，深淺拷貝，增刪查改等部分函數(shù)的介紹，感謝讀者的支持！
? ? ? 建議先創(chuàng)建一個list.hpp頭文件，單獨創(chuàng)建一個命名空間，防止已經(jīng)展開了std的命名空間，實現(xiàn)的list與庫中l(wèi)ist發(fā)生沖突。
? ? ? 我們就定義命名空間為drw，接下來完成三個部分的編寫：
2.1模擬實現(xiàn)結(jié)點
思路：
我們先來定義一個結(jié)構(gòu)體__list_node來代表list中存放數(shù)據(jù)的結(jié)點，方便list中函數(shù)操作等等訪問要求設(shè)置一個模板class T來接受各種類型的顯式實例化這里不能將__list_node直接命名為Node是為了防止與其他同名結(jié)構(gòu)體沖突設(shè)置三個成員變量，分別為:prev? ? next? ? val，用來儲存前后結(jié)點以及此處結(jié)點的數(shù)值使用初始化列表完成構(gòu)造和析構(gòu)函數(shù)
實現(xiàn)：
template
struct __list_node
{
__list_node
__list_node
T val;
__list_node(const T& t=T())
:prev(nullptr)
,next(nullptr)
,val(t)
{}
~__list_node()
{
prev = nullptr;
next = nullptr;
val = 0;
}
};
2.2模擬實現(xiàn)list前序
? ? ? 由于list同樣需要模板class T來顯式實例化，那么我們先設(shè)置一個class T模板參數(shù)，為什么是先呢？是因為后面還會有補(bǔ)充，請耐心看完~
? ? ? 因為list不希望結(jié)點被外界訪問，將結(jié)點進(jìn)行了封裝，所以可以先將__list_node重命名為Node來方便表示，并且只能在public之外重命名，list類中只有一個私有成員變量，就是Node* _head，這代表頭結(jié)點。接下來完成成員函數(shù)：
1）構(gòu)造函數(shù)
思路：
這里我們實現(xiàn)兩個構(gòu)造函數(shù)，分別是直接構(gòu)造和拷貝構(gòu)造因為這兩種構(gòu)造都要先初始化一個頭結(jié)點，我們不妨設(shè)置一個Emptyinit函數(shù)來做這個事情，方便復(fù)用在Emptyinit函數(shù)中，先new一個Node，對val不做處理，讓prev指向自己，next也指向自己直接構(gòu)造：就是Emptyinit函數(shù)的過程，直接復(fù)用拷貝構(gòu)造：參數(shù)是const list
實現(xiàn)：
void Emptyinit()
{
Node* guard = new Node;
guard->prev = guard;
guard->next = guard;
_head = guard;
}
list()
{
Emptyinit();
}
list(const list
{
Emptyinit();
for (auto& e : l)//加上&防止自定義類型深拷貝
{
push_back(e);
}
}
2）push_back函數(shù)
思路：
先new一個新結(jié)點node，將t傳進(jìn)去初始化node再將新結(jié)點的prev設(shè)置為_head的prev，next為_head更新_head的prev以及原先_head之前結(jié)點的next
實現(xiàn)：
void push_back(const T& t)
{
Node* newnode = new Node(t);
newnode->prev = _head->prev;
_head->prev->next = newnode;
newnode->next = _head;
_head->prev = newnode;//雙向帶頭循環(huán)鏈表，需要復(fù)習(xí)！
}
void push_back(const T& t)
{
insert(_head, t);
}
這里還可以直接調(diào)用insert函數(shù)，后面介紹！由于后續(xù)函數(shù)需要迭代器，這里穿插介紹模擬實現(xiàn)迭代器：
2.3模擬實現(xiàn)迭代器
? ? ? 在使用list的時候，我們知道迭代器可以++/--，但是不能+/-，因為list迭代器屬于雙向迭代器但不屬于隨機(jī)迭代器，但每個結(jié)點存儲位置是分散開的啊，這怎么實現(xiàn)++/--呢，于是可以定義一個迭代器結(jié)構(gòu)體，將其封裝成類，就可以進(jìn)行這一操作了！
? ? ??設(shè)置模板template
1）iterator
構(gòu)造函數(shù)和析構(gòu)函數(shù)：
思路：直接使用初始化列表進(jìn)行賦值nullptr即可，同樣賦值nullptr進(jìn)行析構(gòu)，因為node已經(jīng)有默認(rèn)構(gòu)造和析構(gòu)，就不需要更多的處理
實現(xiàn)：
__list_iterator(Node* _node)
:node(_node)
{ }
~__list_iterator()
{
node = nullptr;
}
*操作符重載函數(shù)：
思路：直接返回node代表的val即可
實現(xiàn)：
T& operator*()
{
return node->val;
}
前置/后置++/--：
思路：++：前置就讓node指向next即可，后置就拷貝tmp，讓node指向next返回tmp
? ? ? ? ? ?--：前置node指向prev，后置拷貝tmp，node指向prev返回tmp
實現(xiàn)：
__list_iterator
{
node = node->next;
return *this;
}
__list_iterator
{
__list_iterator
node = node->prev;
return tmp;
}
__list_iterator
{
node = node->next;
return *this;
}
__list_iterator
{
__list_iterator
node = node->prev;
return tmp;
}
==/!=操作符重載函數(shù)：
思路：判斷一下是否相等即可
實現(xiàn)：
bool operator!=(const __list_iterator
{
return node != it.node;
}
bool operator==(const __list_iterator
{
return node == it.node;
}
->操作符重載函數(shù)：
思路：為什么要有這個函數(shù)？是因為如果list存儲的是含有多個成員變量的結(jié)構(gòu)體，那么想要訪問成員變量不應(yīng)該僅僅有*.還應(yīng)該提供->
? ? ? 這里直接返回T*類型的&(node->val)即可就不進(jìn)行實現(xiàn)展示了。
2）const_iterator
思考：const迭代器與iterator相差在哪里呢？無非就是*操作符重載函數(shù)多了一些const，其他大致相同，所以我們就不必再去大費周章重新寫，這里增加一個模板參數(shù)Ref，在顯式實例化的時候傳T&或者const T&就可以解決這個問題：
? ? ? ?那么這僅僅解決了*函數(shù)的重載問題，->函數(shù)呢？這當(dāng)然又需要一個模板參數(shù)Ptr，傳參方法是一樣的。為了簡化類型，將?__list_iterator
演示整個迭代器：
template
struct __list_iterator
{
typedef __list_node
typedef __list_iterator
Node* node;
__list_iterator(Node* _node)
:node(_node)
{ }
Ref operator*()
{
return node->val;
}
Ptr operator->()//為什么要重載訪問成員操作符呢？是因為顯式實例化傳參也就是vector里面可能保存的是自定義類型而不是內(nèi)置類型
{
return &(node->val);
}
self& operator++()//前置
{
node = node->next;
return *this;
}
self& operator++(int)//后置
{
self tmp(*this);
node = node->next;
return tmp;
}
self& operator--()//前置
{
node = node->prev;
return *this;
}
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;
}
~__list_iterator()
{
node = nullptr;
}
};
2.4模擬實現(xiàn)list后序
3）insert函數(shù)
思路：
insert函數(shù)就是在迭代器位置為pos的地方插入數(shù)據(jù)開辟一個新結(jié)點newnode，將數(shù)據(jù)傳入初始化，記錄一下pos的前一個結(jié)點地址prev讓prev的next指向newnode，newnode的prev指向prev，newnode的next指向pos，pos的prev指向newnode，返回newnode
實現(xiàn)：
iterator insert(iterator pos, const T& t)
{
//無需斷言
Node* prev = pos.node->prev;
Node* newnode = new Node(t);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos.node;
pos.node->prev = newnode;
return newnode;
}
4）erase函數(shù)
思路：
判斷一下pos是否合法，不能刪除頭結(jié)點記錄一下前一個和后一個結(jié)點地址，分別為prev和next讓prev的next指向next，next的prev指向prev釋放掉pos結(jié)點，返回next的地址，這是防止迭代器失效的措施
實現(xiàn)：
iterator erase(iterator pos)
{
assert(pos != end());//不能刪除頭結(jié)點
Node* prev = pos.node->prev;
Node* next = pos.node->next;
prev->next = next;
next->prev = prev;
delete pos.node;
return next;
}
5）頭插頭刪尾插尾刪函數(shù)
思路：
由于實現(xiàn)了insert和erase，這里直接復(fù)用就方便多了
實現(xiàn)：
void push_back(const T& t)
{
insert(_head, t);
}
void pop_back()
{
erase(_head->prev);
}
void push_front(const T& t)
{
insert(_head->next, t);
}
void pop_front()
{
erase(_head->next);
}
6）size函數(shù)
思路：
要計算鏈表中的結(jié)點個數(shù)，但不能算入頭結(jié)點定義size_t sz，從頭結(jié)點的下一個開始遍歷，到指針指向_head結(jié)束
實現(xiàn)：
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
7）begin/end函數(shù)
思路：
直接將_head的下一個結(jié)點或者_(dá)head返回，因為end代表最后一個元素的下一個位置
實現(xiàn)：
iterator begin()
{
return _head->next;
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->next;
}
const_iterator end()const
{
return _head;
}
8）clear函數(shù)
思路：
clear函數(shù)是將list中的每一個結(jié)點進(jìn)行釋放刪除，相當(dāng)于清空鏈表用循環(huán)實現(xiàn)即可，但是要注意迭代器的失效問題！erase之后的迭代器要及時更新
實現(xiàn)：
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);//迭代器失效了?。?！要注意！??！
}
}
9）析構(gòu)函數(shù)
思路：
調(diào)用clear函數(shù)之后釋放掉頭結(jié)點就完成了析構(gòu)
實現(xiàn)：
~list()
{
clear();
delete _head;
_head = nullptr;
}
3.完整list
這里給出完整的實現(xiàn)代碼：
#pragma once
#include
#include
using namespace std;
namespace drw
{
template
struct __list_node
{
__list_node
__list_node
T val;
__list_node(const T& t=T())
:prev(nullptr)
,next(nullptr)
,val(t)
{}
~__list_node()
{
prev = nullptr;
next = nullptr;
val = 0;
}
};
template
struct __list_iterator
{
typedef __list_node
typedef __list_iterator
Node* node;
__list_iterator(Node* _node)
:node(_node)
{ }
Ref operator*()
{
return node->val;
}
Ptr operator->()//為什么要重載訪問成員操作符呢？是因為顯式實例化傳參也就是vector里面可能保存的是自定義類型而不是內(nèi)置類型
{
return &(node->val);
}
self& operator++()//前置
{
node = node->next;
return *this;
}
self& operator++(int)//后置
{
self tmp(*this);
node = node->next;
return tmp;
}
self& operator--()//前置
{
node = node->prev;
return *this;
}
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;
}
~__list_iterator()
{
node = nullptr;
}
};
//這樣實現(xiàn)太過于累贅，最好再添加一個模版參數(shù)來實現(xiàn)
//template
//struct __const_list_iterator
//{
// typedef __list_node
// Node* node;
// __const_list_iterator(Node* _node)
// :node(_node)
// {
// }
// const T& operator*()const
// {
// return node->val;
// }
//__const_list_iterator
//{
// node = node->next;
// return *this;
//}
//__const_list_iterator
//{
// __const_list_iterator
// node = node->next;
// return tmp;
//}
// bool operator!=(const __const_list_iterator
// {
// return node != it.node;
// }
// bool operator==(const __const_list_iterator
// {
// return node == it.node;
// }
// ~__const_list_iterator()
// {
// node = nullptr;
// }
//};
template
class list
{
typedef __list_node
public:
/*typedef __list_iterator
typedef __const_list_iterator
//typedef const __list_iterator
typedef __list_iterator
typedef __list_iterator
void Emptyinit()
{
Node* guard = new Node;
guard->prev = guard;
guard->next = guard;
_head = guard;
}
list()
{
Emptyinit();
}
list(const list
{
Emptyinit();
for (auto& e : l)//加上&防止自定義類型深拷貝
{
push_back(e);
}
}
list
{
swap(_head, l._head);
return *this;
}
//void push_back(const T& t)
//{
// Node* newnode = new Node(t);
// newnode->prev = _head->prev;
// _head->prev->next = newnode;
// newnode->next = _head;
// _head->prev = newnode;//雙向帶頭循環(huán)鏈表，需要復(fù)習(xí)！
//}
void push_back(const T& t)
{
insert(_head, t);
}
void pop_back()
{
erase(_head->prev);
}
void push_front(const T& t)
{
insert(_head->next, t);
}
void pop_front()
{
erase(_head->next);
}
iterator begin()
{
return _head->next;
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->next;
}
const_iterator end()const
{
return _head;
}
iterator insert(iterator pos, const T& t)
{
//無需斷言
Node* prev = pos.node->prev;
Node* newnode = new Node(t);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos.node;
pos.node->prev = newnode;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());//不能刪除頭結(jié)點
Node* prev = pos.node->prev;
Node* next = pos.node->next;
prev->next = next;
next->prev = prev;
delete pos.node;
return next;
}
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);//迭代器失效了！??！要注意?。。?/p>
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
};
}
柚子快報激活碼778899分享：list結(jié)構(gòu)刨析與模擬實現(xiàn)
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Chewy寵物樂園
