C++模擬實現(xiàn)list功能
更新時間：2021年08月11日 09:16:23 作者：可樂不解渴
list的底層是一個循環(huán)雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素，接下來通過本文給大家分享C++模擬實現(xiàn)list的示例代碼,需要的朋友可以參考下
努力的最大好處，就在于你可以選擇你想要的生活，而不是被迫隨遇而安。
list介紹
1、 list是可以在**常數(shù)范圍O(1)**內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代，但list容器不適合用來做排序。
2、list的底層是一個循環(huán)雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。
構造函數(shù)
在C++98中l(wèi)ist的構造函數(shù)加上拷貝構造函數(shù)為如下四個。下面我們就模擬實現(xiàn)這里的全部的構造函數(shù)。當然我們這里并沒有像標準庫一樣使用空間配置器來創(chuàng)建空間，使用的是new運算符，但原理都是創(chuàng)建一塊新的空間。
無參構造函數(shù)
這里我們模擬默認的構造函數(shù)，默認值為T()，其含義為：該類型的默認值int類型就為0，char類型為'\0',自定義類型會調用其構造函數(shù)來初始化這個匿名對象得到默認值。
list() //無參默認構造函數(shù)
{
this->m_head = new node(T());
this->m_head->m_next = this->m_head; //創(chuàng)建頭結點，并讓頭結點的頭尾相連形成循環(huán)結構
this->m_head->m_prev = this->m_head;
}
有參構造函數(shù)
list(size_t size, const T& val=T()) //n個元素構造函數(shù)
{
this->m_head = new node(T()); //創(chuàng)建頭結點，并讓頭結點的頭尾相連形成循環(huán)結構
this->m_head->m_next = this->m_head;
this->m_head->m_prev = this->m_head;
while (size--)
{
this->push_back(val);
}
}
注意：
1、該構造函數(shù)知道其需要用于存儲n個數(shù)據(jù)的空間，所以我們使用new運算符開辟好空間，后用push_back()函數(shù)來尾插入val值。
2、該構造函數(shù)還需要實現(xiàn)兩個重載函數(shù)，如果不實現(xiàn)其重載函數(shù)，會導致本來想調用n個元素構造函數(shù)時，編譯器會調用到我們下面要模擬實現(xiàn)的模板區(qū)間構造函數(shù)。
list(long size, const T& val = T()) //n個元素構造函數(shù)
{
assert(size > 0);
this->m_head = new node(T()); //創(chuàng)建頭結點，并讓頭結點的頭尾相連形成循環(huán)結構
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個元素構造函數(shù)
{
assert(size > 0);
this->m_head = new node(T()); //創(chuàng)建頭結點，并讓頭結點的頭尾相連形成循環(huán)結構
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ū)間構造函數(shù)相匹配。
ZJ::list<int>L(2,1); //不實現(xiàn)重載版本會調用到模板區(qū)間構造函數(shù)
并且因為構造函數(shù)2當中對參數(shù)first和last進行了解引用(*)（而int類型不能進行解引用操作）而報錯。
模板區(qū)間構造函數(shù)
最后就是我們上面一直說到的模板區(qū)間構造函數(shù)了，因為該迭代器區(qū)間可以是其他容器的迭代器區(qū)間，該函數(shù)接收到的迭代器的類型是不確定的，所以我們這里需要將該構造函數(shù)設計為一個函數(shù)模板，在函數(shù)體內將該迭代器區(qū)間的數(shù)據(jù)一個個尾插到容器當中即可。
template <class InputIterator>
list(InputIterator first, InputIterator last) //區(qū)間構造
{
this->m_head = new node(T()); //創(chuàng)建頭結點
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());
拷貝構造函數(shù)
拷貝構造的思想是我們是很容易想到的，就是遍歷一遍我們要拷貝的對象obj鏈表，并將obj每個元素的值給this對象的每一個對應的結點，并將其每個結點都鏈接起來。
list(const list<T>& obj) //拷貝構造函數(shù)
{
this->m_head = new node(T()); //創(chuàng)建頭結點，并讓頭結點的頭尾相連形成循環(huán)結構
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)建新結點并把值賦予給它
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調用拷貝構造函數(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語句時就會自動調用析構函數(shù)進行釋放內存，故不會造成內存的泄漏等問題。
析構函數(shù)
析構函數(shù)這里，我就有點偷懶啦，復用了我們下面要模擬實現(xiàn)的pop_front()函數(shù)，大致思路就是從頭到尾一個一個刪除結點，并把頭結點也刪除并至空。
~list() //析構函數(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的結果。
typedef list_iterator<T,T&,T*> iterator; //普通迭代器 typedef list_iterator<T,const T&,const T*> const_iterator; //常量迭代器
可能有人會疑惑，上面這兩個迭代器不都差不多嘛，只是名字不一樣，為什么不直接在類型上加const，而是在模板參數(shù)上指定加上const屬性呢？我們要知道由于const對象只能調用常函數(shù)，但是平時我們使用std::list時是不是可以支持 ++、-- 呢？如果是const對象，它只能調用常函數(shù)，一旦加上變成const函數(shù)，那我們的const迭代器就不能進行++、–、' * '等,而我們要達到的效果是可以進行++、–等，但僅僅是不能其元素的值而已。所以 我們這里封裝了一個模板指針。我們通過模板的參數(shù)不同來控制它的讀取操作。
迭代器構造函數(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)鏈表，我們的++，就是指向下一個結點
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)鏈表，我們的--就是得到它上一個結點的迭代器
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;
}
總結
到了這里可能會有人會問為什么我們不寫迭代器的拷貝構造函數(shù)和析構函數(shù)呢？
答：這是因為我們的迭代器是用來遍歷容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址，并且這些結點元素析構和拷貝并不歸我們管，結點應該歸我們的list管，所以編譯器默認提供的淺拷貝就已經(jīng)足夠了。
容量相關函數(shù)
empty()
功能：是用來獲取容器中是否為空。
返回值：bool。
bool empty() const //判空
{
return this->begin() == this->end(); //就是begin()與end()同時指向頭結點時的情況
}
size()
功能：是用來獲取元素的個數(shù)。
返回值：size_t(無符號整型)。
注意：但是在鏈表中這個接口并不常用。如果頻繁的調用該接口會造成性能的下降。
//遍歷一遍鏈表來得到元素個數(shù)，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數(shù)，但如果頻繁的調用該接口會造成性能的下降
//此時我們應該在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; //指向尾部結點
node* newnode = new node(val); //創(chuàng)建新結點
newnode->m_next = tail->m_next; //將新結點的m_next指向頭結點
newnode->m_prev = tail; //將新結點m_prev指向tail結點
tail->m_next = newnode; //并將原來的尾結點的m_next指向newnode
this->m_head->m_prev = newnode; //并將頭結點的m_prev指向新的尾
}
push_front()
- 功能：在頭部插入一個元素。
- 返回值：void（無返回值）。
void push_front(const T& val) //頭插
{
node* newnode = new node(val); //創(chuàng)建新結點
node* next = this->m_head->m_next; //指向第一個結點
newnode->m_next = next; //將創(chuàng)建的新結點newnode的m_next指向我們原來的第一個元素next
this->m_head->m_next = newnode; //在將我們的頭結點的m_next指向新創(chuàng)建的結點
newnode->m_prev = this->m_head; //在將新結點的m_prev指向頭結點
next->m_prev = newnode; //在將原先第一個結點元素的m_prev指向新創(chuàng)建的結點
}
pop_back()
- 功能：在尾部刪除一個元素。
- 返回值：void（無返回值）。
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; //將頭結點的m_prev指向新的尾prev
prev->m_next = this->m_head; //再將prev的m_next指向頭結點
tail->m_next = tail->m_prev = nullptr; //把要刪除的元素的成員至nullptr
tail->m_val = T(); //將要刪除的元素的值置為匿名對象的默認值
delete tail; //刪除尾結點
}
pop_front()
- 功能：在頭部刪除一個元素。
- 返回值：void（無返回值）。
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; //再將頭結點的m_next指向我們新的第一個結點
next->m_prev = this->m_head; //再將我們的新的第一個結點的m_prev指向頭結點
delnode->m_next = delnode->m_prev = nullptr; //把要刪除的元素的成員至nullptr
delnode->m_val = T(); //將要刪除的元素的值置為匿名對象的默認值
delete delnode; //刪除第一個結點
}
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)建新結點
node* cur = pos.m_pnode; //記錄當前結點的指針
node* prev = cur->m_prev; //記錄當前結點的前一個結點的指針
newnode->m_next = cur;
newnode->m_prev = prev;
prev->m_next = newnode;
cur->m_prev = newnode;
return iterator(newnode); //返回一個用當前的插入的元素的結點構建的匿名對象的迭代器
}
指定位置插入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)三種重載版本呢？這與上面的構造函數(shù)問題是相同類型的，都是與模板區(qū)間構造有關，這里就不多贅述了。
指定位置插入?yún)^(qū)間內的元素
- 功能：在指定位置插入?yún)^(qū)間內的元素。
- 返回值：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ū)間內的元素。如下圖所示：
刪除指定位置
- 功能：刪除指定位置的元素。
- 返回值：刪除指定位置的元素的下一個結點的迭代器。
//刪除指定位置的元素，返回下一個元素的迭代器，但要注意的是：
//如果刪除的最后一個元素，此時返回的是頭結點也就是end()位置的迭代器
iterator erase(iterator pos)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(pos != end()); //斷言 list內元素為空及刪除頭結點的情況
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ū)間內的元素
- 功能：刪除區(qū)間內的元素。
- 返回值：刪除區(qū)間內的元素的下一個結點的迭代器。也就是返回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 //結點
{
public:
list_node(T val=T()) //構造函數(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() //無參默認構造函數(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個元素構造函數(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個元素構造函數(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個元素構造函數(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ū)間構造
{
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) //拷貝構造函數(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() //析構函數(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()同時指向頭結點時的情況
}
//遍歷一遍鏈表來得到元素個數(shù)，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數(shù)，但如果頻繁的調用該接口會造成性能的下降
//此時我們應該在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)建新結點
node* cur = pos.m_pnode; //記錄當前結點的指針
node* prev = cur->m_prev; //記錄當前結點的前一個結點的指針
newnode->m_next = cur;
newnode->m_prev = prev;
prev->m_next = newnode;
cur->m_prev = newnode;
return iterator(newnode); //返回一個用當前的插入的元素的結點構建的匿名對象的迭代器
}
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;
}
//刪除指定位置的元素，返回下一個元素的迭代器，但要注意的是：
//如果刪除的最后一個元素，此時返回的是頭結點也就是end()位置的迭代器
iterator erase(iterator pos)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
assert(pos != end()); //斷言 list內元素為空及刪除頭結點的情況
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)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結構之迷宮求解問題，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
在很多工作中,我們需要計算數(shù)據(jù)或者文件的散列值,例如登錄或下載文件,而在?Qt?中,負責這項工作的類為?QCryptographicHash,本文給大家介紹了在C++?Qt中實現(xiàn)異步散列器的代碼示例,需要的朋友可以參考下2024-09-09
這篇文章主要為大家詳細介紹了C++如何使用代碼對回收站里的文件進行操作，譬如文件的刪除與恢復等，文中的示例代碼講解詳細，具有一定的學習價值，感興趣的小伙伴快跟隨小編一起學習學習吧2023-06-06
這篇文章主要為大家詳細介紹了C語言的預處理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
本篇文章是對最長公共子字符串的使用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本篇文章是對jaxb xjc編碼的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本篇文章是對冒泡排序的三種實現(xiàn)方法進行了詳細的介紹，需要的朋友可以過來參考下。希望對大家有所幫助2013-10-10
這篇文章主要介紹了用C語言求解一元二次方程的簡單實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
解決pip?install?dlib報錯C++11?is?required?to?use?dlib
這篇文章主要介紹了在使用pip?install?dlib安裝dlib的時候報錯C++11?is?required?to?use?dlib的解決方法，需要的的小伙伴可以參考一下，希望對你有所幫助2022-02-02
這篇文章主要給大家講解輪轉數(shù)組的問題，一個問題不局限于一種解法，希望你看了本文的解決方法以后可以舉一反三自己編寫，這樣你的技術水平會有質的提高2022-04-04