C++模擬實現(xiàn)list功能
更新時間：2021年08月11日 09:16:23 作者：可樂不解渴
list的底層是一個循環(huán)雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素，接下來通過本文給大家分享C++模擬實現(xiàn)list的示例代碼,需要的朋友可以參考下
努力的最大好處，就在于你可以選擇你想要的生活，而不是被迫隨遇而安。
list介紹
1、 list是可以在**常數(shù)范圍O(1)**內(nèi)在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代，但list容器不適合用來做排序。
2、list的底層是一個循環(huán)雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。
構(gòu)造函數(shù)
在C++98中l(wèi)ist的構(gòu)造函數(shù)加上拷貝構(gòu)造函數(shù)為如下四個。下面我們就模擬實現(xiàn)這里的全部的構(gòu)造函數(shù)。當然我們這里并沒有像標準庫一樣使用空間配置器來創(chuàng)建空間，使用的是new運算符，但原理都是創(chuàng)建一塊新的空間。
無參構(gòu)造函數(shù)
這里我們模擬默認的構(gòu)造函數(shù)，默認值為T()，其含義為：該類型的默認值int類型就為0，char類型為'\0',自定義類型會調(diào)用其構(gòu)造函數(shù)來初始化這個匿名對象得到默認值。
list() //無參默認構(gòu)造函數(shù)
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head; //創(chuàng)建頭結(jié)點，并讓頭結(jié)點的頭尾相連形成循環(huán)結(jié)構(gòu)
this->m_head->m_prev = this->m_head;
}
有參構(gòu)造函數(shù)
list(size_t size, const T& val=T()) //n個元素構(gòu)造函數(shù)
{
this->m_head = new node(T()); //創(chuàng)建頭結(jié)點，并讓頭結(jié)點的頭尾相連形成循環(huán)結(jié)構(gòu)
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
注意：
1、該構(gòu)造函數(shù)知道其需要用于存儲n個數(shù)據(jù)的空間，所以我們使用new運算符開辟好空間，后用push_back()函數(shù)來尾插入val值。
2、該構(gòu)造函數(shù)還需要實現(xiàn)兩個重載函數(shù)，如果不實現(xiàn)其重載函數(shù)，會導致本來想調(diào)用n個元素構(gòu)造函數(shù)時，編譯器會調(diào)用到我們下面要模擬實現(xiàn)的模板區(qū)間構(gòu)造函數(shù)。
list(long size, const T& val = T()) //n個元素構(gòu)造函數(shù)
{
assert(size > 0);
this->m_head = new node(T()); //創(chuàng)建頭結(jié)點，并讓頭結(jié)點的頭尾相連形成循環(huán)結(jié)構(gòu)
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
list(int size, const T& val = T()) //n個元素構(gòu)造函數(shù)
{
assert(size > 0);
this->m_head = new node(T()); //創(chuàng)建頭結(jié)點，并讓頭結(jié)點的頭尾相連形成循環(huán)結(jié)構(gòu)
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
可以看到，這兩個重載函數(shù)與之不同的就是其參數(shù)size的類型不同，但這卻是必要的，否則當我們使用以下代碼時，編譯器會優(yōu)先與模板區(qū)間構(gòu)造函數(shù)相匹配。
ZJ::list<int>L(2,1); //不實現(xiàn)重載版本會調(diào)用到模板區(qū)間構(gòu)造函數(shù)
并且因為構(gòu)造函數(shù)2當中對參數(shù)first和last進行了解引用(*)（而int類型不能進行解引用操作）而報錯。
模板區(qū)間構(gòu)造函數(shù)
最后就是我們上面一直說到的模板區(qū)間構(gòu)造函數(shù)了，因為該迭代器區(qū)間可以是其他容器的迭代器區(qū)間，該函數(shù)接收到的迭代器的類型是不確定的，所以我們這里需要將該構(gòu)造函數(shù)設計為一個函數(shù)模板，在函數(shù)體內(nèi)將該迭代器區(qū)間的數(shù)據(jù)一個個尾插到容器當中即可。
template <class InputIterator>
list(InputIterator first, InputIterator last) //區(qū)間構(gòu)造
{
this->m_head = new node(T()); //創(chuàng)建頭結(jié)點
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (first != last)
{
node* newnode = new node(*first);
node* tail = this->m_head->m_prev;
tail->m_next = newnode;
newnode->m_prev = tail;
newnode->m_next = this->m_head;
this->m_head->m_prev = newnode;
++first;
}
}
注意：
1、該區(qū)間必須是前閉后開[obj.begin()，obj.end());
拷貝構(gòu)造函數(shù)
拷貝構(gòu)造的思想是我們是很容易想到的，就是遍歷一遍我們要拷貝的對象obj鏈表，并將obj每個元素的值給this對象的每一個對應的結(jié)點，并將其每個結(jié)點都鏈接起來。
list(const list<T>& obj) //拷貝構(gòu)造函數(shù)
{
this->m_head = new node(T()); //創(chuàng)建頭結(jié)點，并讓頭結(jié)點的頭尾相連形成循環(huán)結(jié)構(gòu)
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
const_iterator it = obj.begin();
while (it != obj.end())
{
node* newnode = new node(it.m_pnode->m_val); //創(chuàng)建新結(jié)點并把值賦予給它
node* tail = this->m_head->m_prev;
tail->m_next = newnode;
newnode->m_prev = tail;
newnode->m_next = this->m_head;
this->m_head->m_prev = newnode;
++it;
}
}
賦值運算符重載
根據(jù)我們之前的博客的往歷，這里我們采用現(xiàn)代寫法，及用obj調(diào)用拷貝構(gòu)造函數(shù)創(chuàng)建一個臨時對象temp，并將temp與我們的this指針指向的對象的指針交換即可。
list<T>& operator=(const list<T>& obj) //賦值運算符重載
{
if (this != &obj) //防止自我賦值
{
list<T>temp(obj);
this->swap(temp);
}
return *this; //返回自己
}
注意：
1、上面的temp臨時對象出了if語句時就會自動調(diào)用析構(gòu)函數(shù)進行釋放內(nèi)存，故不會造成內(nèi)存的泄漏等問題。
析構(gòu)函數(shù)
析構(gòu)函數(shù)這里，我就有點偷懶啦，復用了我們下面要模擬實現(xiàn)的pop_front()函數(shù)，大致思路就是從頭到尾一個一個刪除結(jié)點，并把頭結(jié)點也刪除并至空。
~list() //析構(gòu)函數(shù)
{
iterator it = this->begin();
while (it != this->end()) //復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
{
++it;
this->pop_front();
}
delete this->m_head;
this->m_head = nullptr;
}
迭代器
在C++中我們的迭代器有如下幾種：
下面我只模擬begin()和end()迭代器。
iterator begin()
{
return iterator(this->m_head->m_next);
}
const_iterator begin() const
{
return const_iterator(this->m_head->m_next);
}
iterator end()
{
return iterator(this->m_head);
}
const_iterator end() const
{
return const_iterator(this->m_head);
}
上面我們模擬實現(xiàn)了我們的迭代器，并且有普通迭代器和const迭代器。但是我們還要了解迭代器的原理是上面，在之前我們的博客中我們說過并不是每個迭代器都是原生指針，其中我們的list就是封裝了一個指針變量來達到實現(xiàn)iterator的結(jié)果。
typedef list_iterator<T,T&,T*> iterator; //普通迭代器 typedef list_iterator<T,const T&,const T*> const_iterator; //常量迭代器
可能有人會疑惑，上面這兩個迭代器不都差不多嘛，只是名字不一樣，為什么不直接在類型上加const，而是在模板參數(shù)上指定加上const屬性呢？我們要知道由于const對象只能調(diào)用常函數(shù)，但是平時我們使用std::list時是不是可以支持 ++、-- 呢？如果是const對象，它只能調(diào)用常函數(shù)，一旦加上變成const函數(shù)，那我們的const迭代器就不能進行++、–、' * '等,而我們要達到的效果是可以進行++、–等，但僅僅是不能其元素的值而已。所以 我們這里封裝了一個模板指針。我們通過模板的參數(shù)不同來控制它的讀取操作。
迭代器構(gòu)造函數(shù)
就是將一個指針傳過來，并賦給我們的成員變量m_pnode。
list_iterator(node* pnode)
:m_pnode(pnode)
{}
迭代器關系運算符重載
因為我們要實現(xiàn)迭代器的相關遍歷操作例如下面的代碼：
ZJ::list<int>::iterator it = L1.begin(); it != L1.end()
bool operator!=(const myself&obj) const //重載！=號
{
return this->m_pnode != obj.m_pnode;
}
bool operator==(const myself& obj) const //重載==號
{
return this->m_pnode == obj.m_pnode;
}
迭代器++ --運算符重載
其中下面返回的myself類型其實就是我們的迭代器這個類的類型，只是我們將其typedef了一下代碼如下：
typedef list_iterator<T, Ref, Ptr>myself;
這里重載的前置與后置要分別開來，后置需要使用int占位符來占位，不然會發(fā)生錯誤。
myself& operator++() //重載前置++
{
//由于我們的list是雙向循環(huán)鏈表，我們的++，就是指向下一個結(jié)點
this->m_pnode = this->m_pnode->m_next;
return *this;
}
myself operator++(int) //重載后置++
{
const myself temp(*this);
this->m_pnode = this->m_pnode->m_next;
return temp;
}
myself& operator--() //重載前置--
{
//由于我們的list是雙向循環(huán)鏈表，我們的--就是得到它上一個結(jié)點的迭代器
this->m_pnode = this->m_pnode->m_prev;
return *this;
}
myself operator--(int) //重載后置--
{
const myself temp(*this);
this->m_pnode = this->m_pnode->m_prev;
return temp;
}
迭代器 * 運算符重載
由于我們知道Ref是由兩種類型的，一種是T&,另一種是const T&,所以當我們的對象是const對象時，我們可以控制它不讓其修改。
Ref operator* () //重載 *
{
return this->m_pnode->m_val;
}
迭代器 -> 運算符重載
為什么要重載->運算符呢？這是因為如果我們list中存儲的是自定義類型時，我們的迭代器無法使用->去得到其成員。
Ptr operator->() //重載 ->
{
return &this->m_pnode->m_val;
}
總結(jié)
到了這里可能會有人會問為什么我們不寫迭代器的拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)呢？
答：這是因為我們的迭代器是用來遍歷容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址，并且這些結(jié)點元素析構(gòu)和拷貝并不歸我們管，結(jié)點應該歸我們的list管，所以編譯器默認提供的淺拷貝就已經(jīng)足夠了。
容量相關函數(shù)
empty()
功能：是用來獲取容器中是否為空。
返回值：bool。
bool empty() const //判空
{
return this->begin() == this->end(); //就是begin()與end()同時指向頭結(jié)點時的情況
}
size()
功能：是用來獲取元素的個數(shù)。
返回值：size_t(無符號整型)。
注意：但是在鏈表中這個接口并不常用。如果頻繁的調(diào)用該接口會造成性能的下降。
//遍歷一遍鏈表來得到元素個數(shù)，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數(shù)，但如果頻繁的調(diào)用該接口會造成性能的下降
//此時我們應該在list類中將增加一個記錄元素個數(shù)的變量size
//如果有元素插入就增加，刪除就減少
size_t size() const //獲得元素個數(shù)
{
size_t size = 0;
const_iterator it = this->begin();
while(it!=this->end())
{
++it;
++size;
}
return size;
}
元素訪問相關函數(shù)
back()
- 功能：獲取最后一個元素的值。
- 返回值：存儲的類型的引用。
T& back()
{
assert(!this->empty());
return this->m_head->m_prev->m_val;
}
const T& back() const
{
assert(!this->empty());
return this->m_head->prev->m_val;
}
front()
- 功能：獲取第一個元素的值。
- 返回值：存儲的類型的引用。
T& front()
{
assert(!this->empty());
return this->m_head->m_next->m_val;
}
const T& front() const
{
assert(!this->empty());
return this->m_head->m_next->m_val;
}
修改相關函數(shù)
push_back()
- 功能：在尾部插入一個元素。
- 返回值：void（無返回值）。
void push_back(const T& val) //尾插
{
node* tail = this->m_head->m_prev; //指向尾部結(jié)點
node* newnode = new node(val); //創(chuàng)建新結(jié)點
newnode->m_next = tail->m_next; //將新結(jié)點的m_next指向頭結(jié)點
newnode->m_prev = tail; //將新結(jié)點m_prev指向tail結(jié)點
tail->m_next = newnode; //并將原來的尾結(jié)點的m_next指向newnode
this->m_head->m_prev = newnode; //并將頭結(jié)點的m_prev指向新的尾
}
push_front()
- 功能：在頭部插入一個元素。
- 返回值：void（無返回值）。
void push_front(const T& val) //頭插
{
node* newnode = new node(val); //創(chuàng)建新結(jié)點
node* next = this->m_head->m_next; //指向第一個結(jié)點
newnode->m_next = next; //將創(chuàng)建的新結(jié)點newnode的m_next指向我們原來的第一個元素next
this->m_head->m_next = newnode; //在將我們的頭結(jié)點的m_next指向新創(chuàng)建的結(jié)點
newnode->m_prev = this->m_head; //在將新結(jié)點的m_prev指向頭結(jié)點
next->m_prev = newnode; //在將原先第一個結(jié)點元素的m_prev指向新創(chuàng)建的結(jié)點
}
pop_back()
- 功能：在尾部刪除一個元素。
- 返回值：void（無返回值）。
void pop_back() //尾刪
{
assert(!empty()); //斷言 如果list已經(jīng)為空，則刪除不了
node* tail = this->m_head->m_prev; //先找到我們要刪除的尾結(jié)點
node* prev = tail->m_prev; //再找到要刪除的尾結(jié)點的前一個結(jié)點
this->m_head->m_prev = prev; //將頭結(jié)點的m_prev指向新的尾prev
prev->m_next = this->m_head; //再將prev的m_next指向頭結(jié)點
tail->m_next = tail->m_prev = nullptr; //把要刪除的元素的成員至nullptr
tail->m_val = T(); //將要刪除的元素的值置為匿名對象的默認值
delete tail; //刪除尾結(jié)點
}
pop_front()
- 功能：在頭部刪除一個元素。
- 返回值：void（無返回值）。
void pop_front() //頭刪
{
assert(!empty()); //斷言 如果list已經(jīng)為空，則刪除不了
node* delnode = this->m_head->m_next; //先找到我們要刪除的第一個結(jié)點位置
node* next = delnode->m_next; //在找到刪除結(jié)點的下一個結(jié)點的位置
this->m_head->m_next = next; //再將頭結(jié)點的m_next指向我們新的第一個結(jié)點
next->m_prev = this->m_head; //再將我們的新的第一個結(jié)點的m_prev指向頭結(jié)點
delnode->m_next = delnode->m_prev = nullptr; //把要刪除的元素的成員至nullptr
delnode->m_val = T(); //將要刪除的元素的值置為匿名對象的默認值
delete delnode; //刪除第一個結(jié)點
}
insert()
在c++98中我們的insert()函數(shù)有如下三種版本：
下面我們就將其模擬實現(xiàn)：
指定位置插入一個元素
- 功能：在指定位置插入一個元素。
- 返回值：插入的元素的位置的迭代器。
//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
node* newnode = new node(val); //創(chuàng)建新結(jié)點
node* cur = pos.m_pnode; //記錄當前結(jié)點的指針
node* prev = cur->m_prev; //記錄當前結(jié)點的前一個結(jié)點的指針
newnode->m_next = cur;
newnode->m_prev = prev;
prev->m_next = newnode;
cur->m_prev = newnode;
return iterator(newnode); //返回一個用當前的插入的元素的結(jié)點構(gòu)建的匿名對象的迭代器
}
指定位置插入n個相同的元素
- 功能：在指定位置插入一個元素。
- 返回值：void(無返回值)。
void insert(iterator pos, size_t n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
void insert(iterator pos, int n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(n > 0);
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
void insert(iterator pos, long n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(n > 0);
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
注意：這里的insert在指定位置插入為什么要實現(xiàn)三種重載版本呢？這與上面的構(gòu)造函數(shù)問題是相同類型的，都是與模板區(qū)間構(gòu)造有關，這里就不多贅述了。
指定位置插入?yún)^(qū)間內(nèi)的元素
- 功能：在指定位置插入?yún)^(qū)間內(nèi)的元素。
- 返回值：void(無返回值)。
- 注意：
1、該區(qū)間必須是前閉后開;
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last) //區(qū)間插入
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
while (first != last)
{
node* newnode = new node(*first);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
++first;
}
}
erase()
在C++98中erase()有兩種版本，一個是刪除指定位置，另一個是刪除區(qū)間內(nèi)的元素。如下圖所示：
刪除指定位置
- 功能：刪除指定位置的元素。
- 返回值：刪除指定位置的元素的下一個結(jié)點的迭代器。
//刪除指定位置的元素，返回下一個元素的迭代器，但要注意的是：
//如果刪除的最后一個元素，此時返回的是頭結(jié)點也就是end()位置的迭代器
iterator erase(iterator pos)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(pos != end()); //斷言 list內(nèi)元素為空及刪除頭結(jié)點的情況
node* next = pos.m_pnode->m_next;
node* prev = pos.m_pnode->m_prev;
prev->m_next = next;
next->m_prev = prev;
pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
pos.m_pnode->m_val = T();
delete pos.m_pnode;
return iterator(next);
}
刪除區(qū)間內(nèi)的元素
- 功能：刪除區(qū)間內(nèi)的元素。
- 返回值：刪除區(qū)間內(nèi)的元素的下一個結(jié)點的迭代器。也就是返回last迭代器這個位置。
- 注意：
1、該區(qū)間必須是前閉后開;
iterator erase(iterator first, iterator last) //區(qū)間刪除
{
node* prev = first.m_pnode->m_prev;
node* next = last.m_pnode;
while (first != last)
{
node* cur = first.m_pnode;
++first;
cur->m_next = cur->m_prev = nullptr;
cur->m_val = T();
delete cur;
cur = nullptr;
}
prev->m_next = next;
next->m_prev = prev;
return iterator(next);
}
clear()
- 功能：用于清空我們list中的所有元素的值，但不是要把list對象也刪除。
- 返回值：void（無返回值）。
void clear() //清空元素，而不是把整個鏈表刪除掉
{
iterator it = this->begin();
while (it != this->end())
//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
{
++it;
this->pop_front();
}
}
swap()
- 功能：swap顧名思義就是交換的意思，這里我們將這個swap作為我們的成員函數(shù)，用來交換兩個list鏈表。
- 返回值: void（無返回值）。
void swap(list<T>& obj)
{
node* temp = this->m_head;
this->m_head = obj.m_head;
obj.m_head = temp;
}
完整代碼如下
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
namespace ZJ
{
template<class T>
class list_node //結(jié)點
{
public:
list_node(T val=T()) //構(gòu)造函數(shù)
:m_val(val)
,m_prev(nullptr)
,m_next(nullptr)
{}
public:
T m_val; //值
list_node<T>* m_prev; //指向前一個的指針
list_node<T>* m_next; //指向下一個的指針
};
template<class T,class Ref,class Ptr> //封裝一個node型指針，制作成迭代器類
class list_iterator
{
public:
typedef list_node<T> node;
typedef list_iterator<T, Ref, Ptr>myself;
list_iterator(node* pnode)
:m_pnode(pnode)
{}
Ref operator* () //重載 *
{
return this->m_pnode->m_val;
}
Ptr operator->() //重載 ->
{
return &this->m_pnode->m_val;
}
bool operator!=(const myself&obj) const //重載！=號
{
return this->m_pnode != obj.m_pnode;
}
bool operator==(const myself& obj) const //重載==號
{
return this->m_pnode == obj.m_pnode;
}
myself& operator++() //重載前置++
{
this->m_pnode = this->m_pnode->m_next;
return *this;
}
myself operator++(int) //重載后置++
{
const myself temp(*this);
this->m_pnode = this->m_pnode->m_next;
return temp;
}
myself& operator--() //重載前置--
{
this->m_pnode = this->m_pnode->m_prev;
return *this;
}
myself operator--(int) //重載后置--
{
const myself temp(*this);
this->m_pnode = this->m_pnode->m_prev;
return temp;
}
public:
node* m_pnode;
};
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; //常量迭代器
public:
list() //無參默認構(gòu)造函數(shù)
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
}
list(size_t size, const T& val=T()) //n個元素構(gòu)造函數(shù)
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
list(long size, const T& val = T()) //n個元素構(gòu)造函數(shù)
{
assert(size > 0);
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
list(int size, const T& val = T()) //n個元素構(gòu)造函數(shù)
{
assert(size > 0);
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
template <class InputIterator>
list(InputIterator first, InputIterator last) //區(qū)間構(gòu)造
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (first != last)
{
node* newnode = new node(*first);
node* tail = this->m_head->m_prev;
tail->m_next = newnode;
newnode->m_prev = tail;
newnode->m_next = this->m_head;
this->m_head->m_prev = newnode;
++first;
}
}
list(const list<T>& obj) //拷貝構(gòu)造函數(shù)
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
const_iterator it = obj.begin();
while (it != obj.end())
{
node* newnode = new node(it.m_pnode->m_val);
node* tail = this->m_head->m_prev;
tail->m_next = newnode;
newnode->m_prev = tail;
newnode->m_next = this->m_head;
this->m_head->m_prev = newnode;
++it;
}
}
list<T>& operator=(const list<T>& obj) //賦值運算符重載
{
if (this != &obj)
{
list<T>temp(obj);
this->swap(temp);
}
return *this;
}
~list() //析構(gòu)函數(shù)
{
iterator it = this->begin();
while (it != this->end()) //復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
{
++it;
this->pop_front();
}
delete this->m_head;
this->m_head = nullptr;
}
iterator begin()
{
return iterator(this->m_head->m_next);
}
const_iterator begin() const
{
return const_iterator(this->m_head->m_next);
}
iterator end()
{
return iterator(this->m_head);
}
const_iterator end() const
{
return const_iterator(this->m_head);
}
bool empty() const //判空
{
return this->begin() == this->end(); //就是begin()與end()同時指向頭結(jié)點時的情況
}
//遍歷一遍鏈表來得到元素個數(shù)，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數(shù)，但如果頻繁的調(diào)用該接口會造成性能的下降
//此時我們應該在list類中將增加一個記錄元素個數(shù)的變量size
//如果有元素插入就增加，刪除就減少
size_t size() const //獲得元素個數(shù)
{
size_t size = 0;
const_iterator it = this->begin();
while(it!=this->end())
{
++it;
++size;
}
return size;
}
T& back()
{
assert(!this->empty());
return this->m_head->m_prev->m_val;
}
const T& back() const
{
assert(!this->empty());
return this->m_head->prev->m_val;
}
T& front()
{
assert(!this->empty());
return this->m_head->m_next->m_val;
}
const T& front() const
{
assert(!this->empty());
return this->m_head->m_next->m_val;
}
void push_front(const T& val) //頭插
{
node* newnode = new node(val);
node* next = this->m_head->m_next;
newnode->m_next = next;
this->m_head->m_next = newnode;
newnode->m_prev = this->m_head;
next->m_prev = newnode;
}
void push_back(const T& val) //尾插
{
node* tail = this->m_head->m_prev;
node* newnode = new node(val);
newnode->m_next = tail->m_next;
newnode->m_prev = tail;
tail->m_next = newnode;
this->m_head->m_prev = newnode;
}
//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
node* newnode = new node(val); //創(chuàng)建新結(jié)點
node* cur = pos.m_pnode; //記錄當前結(jié)點的指針
node* prev = cur->m_prev; //記錄當前結(jié)點的前一個結(jié)點的指針
newnode->m_next = cur;
newnode->m_prev = prev;
prev->m_next = newnode;
cur->m_prev = newnode;
return iterator(newnode); //返回一個用當前的插入的元素的結(jié)點構(gòu)建的匿名對象的迭代器
}
void insert(iterator pos, size_t n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
void insert(iterator pos, int n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(n > 0);
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
void insert(iterator pos, long n, const T& val) //插入n個val
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(n > 0);
while (n--)
{
node* newnode = new node(val);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
}
}
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last) //區(qū)間插入
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
while (first != last)
{
node* newnode = new node(*first);
node* cur = pos.m_pnode;
node* prev = cur->m_prev;
newnode->m_prev = prev;
prev->m_next = newnode;
newnode->m_next = cur;
cur->m_prev = newnode;
++first;
}
}
void pop_front() //頭刪
{
assert(!empty()); //斷言 如果list已經(jīng)為空，則刪除不了
node* delnode = this->m_head->m_next;
node* next = delnode->m_next;
this->m_head->m_next = next;
next->m_prev = this->m_head;
delnode->m_next = delnode->m_prev = nullptr;
delnode->m_val = T();
delete delnode;
}
void pop_back() //尾刪
{
assert(!empty()); //斷言 如果list已經(jīng)為空，則刪除不了
node* tail = this->m_head->m_prev;
node* prev = tail->m_prev;
this->m_head->m_prev = prev;
prev->m_next = this->m_head;
tail->m_next = tail->m_prev = nullptr;
tail->m_val = T();
delete tail;
}
//刪除指定位置的元素，返回下一個元素的迭代器，但要注意的是：
//如果刪除的最后一個元素，此時返回的是頭結(jié)點也就是end()位置的迭代器
iterator erase(iterator pos)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(pos != end()); //斷言 list內(nèi)元素為空及刪除頭結(jié)點的情況
node* next = pos.m_pnode->m_next;
node* prev = pos.m_pnode->m_prev;
prev->m_next = next;
next->m_prev = prev;
pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
pos.m_pnode->m_val = T();
delete pos.m_pnode;
return iterator(next);
}
iterator erase(iterator first, iterator last) //區(qū)間刪除
{
node* prev = first.m_pnode->m_prev;
node* next = last.m_pnode;
while (first != last)
{
node* cur = first.m_pnode;
++first;
cur->m_next = cur->m_prev = nullptr;
cur->m_val = T();
delete cur;
cur = nullptr;
}
prev->m_next = next;
next->m_prev = prev;
return iterator(next);
}
void clear() //清空元素，而不是把整個鏈表刪除掉
{
iterator it = this->begin();
while (it != this->end()) //復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
{
++it;
this->pop_front();
}
}
void swap(list<T>& obj)
{
node* temp = this->m_head;
this->m_head = obj.m_head;
obj.m_head = temp;
}
private:
node* m_head; //頭指針
};
}
到此這篇關于C++模擬實現(xiàn)list的文章就介紹到這了,更多相關C++list實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Visual Studio Code (vscode) 配置C、C++環(huán)境/編寫運行C、C++的教程詳解（Windows
這篇文章主要介紹了Visual Studio Code (vscode) 配置C、C++環(huán)境/編寫運行C、C++的教程詳解（Windows）【真正的小白版】,圖文詳解介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-03-03
Qt圖片繪圖類之QPixmap/QImage/QPicture詳解
這篇文章主要為大家詳細介紹了Qt圖片繪圖類中QPixmap、QImage和QPicture的使用方法，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2023-03-03
c語言的cps實現(xiàn)求fibonacci數(shù)列示例
這篇文章主要介紹了c語言的cps實現(xiàn)求fibonacci數(shù)列示例,需要的朋友可以參考下2014-03-03
用C++實現(xiàn),將一句話里的單詞進行倒置的方法詳解
本篇文章是對用C++實現(xiàn),將一句話里的單詞進行倒置的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
C語言實現(xiàn)輸入一顆二元查找樹并將該樹轉(zhuǎn)換為它的鏡像
這篇文章主要介紹了C語言實現(xiàn)輸入一顆二元查找樹并將該樹轉(zhuǎn)換為它的鏡像,是數(shù)據(jù)結(jié)構(gòu)中二元查找樹的一個比較經(jīng)典的算法,有不錯的借鑒價值,需要的朋友可以參考下2014-09-09
解析在main函數(shù)之前調(diào)用函數(shù)以及對設計的作用詳解
本篇文章是對在main函數(shù)之前調(diào)用函數(shù)以及對設計的作用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了如何使用MATLAB繪制散點密度圖(二維核密度)，文中的示例代碼講解詳細，對我們學習Matlab有一定幫助，需要的可以參考一下2022-02-02
這篇文章主要介紹了C語言編程中生成隨機數(shù)的入門教程,包括利用rand()函數(shù)來編寫隨機數(shù)生成器的示例,要的朋友可以參考下2015-12-12
這篇文章主要給大家介紹了關于利用C++如何實現(xiàn)一個阻塞隊列的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
這篇文章主要為大家詳細介紹了C++實現(xiàn)圖書管理系統(tǒng)最新版，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06