溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“C++怎么實現list功能”，在日常操作中，相信很多人在C++怎么實現list功能問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++怎么實現list功能”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
?list介紹
?構造函數
???無參構造函數
?有參構造函數
?模板區間構造函數
?拷貝構造函數
?賦值運算符重載
?析構函數
?迭代器
?迭代器構造函數
?迭代器關系運算符重載
?迭代器++ --運算符重載
?迭代器 * 運算符重載
?迭代器 -> 運算符重載
???總結
?容量相關函數
???empty()
?size()
?元素訪問相關函數
?back()
?front()
?修改相關函數
?push_back()
???push_front()
?pop_back()
???pop_front()
?insert()
?erase()
?clear()
?swap()
?完整代碼如下
努力的最大好處，就在于你可以選擇你想要的生活，而不是被迫隨遇而安。
1、 list是可以在**常數范圍O(1)**內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代，但list容器不適合用來做排序。
2、list的底層是一個循環雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。
在C++98中list的構造函數加上拷貝構造函數為如下四個。下面我們就模擬實現這里的全部的構造函數。當然我們這里并沒有像標準庫一樣使用空間配置器來創建空間，使用的是new運算符，但原理都是創建一塊新的空間。
這里我們模擬默認的構造函數，默認值為T()，其含義為：該類型的默認值int類型就為0，char類型為'\0',自定義類型會調用其構造函數來初始化這個匿名對象得到默認值。
list() //無參默認構造函數
{
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個元素構造函數
{
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);
}
}注意：
1、該構造函數知道其需要用于存儲n個數據的空間，所以我們使用new運算符開辟好空間，后用push_back()函數來尾插入val值。2、該構造函數還需要實現兩個重載函數，如果不實現其重載函數，會導致本來想調用n個元素構造函數時，編譯器會調用到我們下面要模擬實現的模板區間構造函數。
list(long size, const T& val = T()) //n個元素構造函數
{
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個元素構造函數
{
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);
}
}可以看到，這兩個重載函數與之不同的就是其參數size的類型不同，但這卻是必要的，否則當我們使用以下代碼時，編譯器會優先與模板區間構造函數相匹配。
ZJ::list<int>L(2,1); //不實現重載版本會調用到模板區間構造函數
并且因為構造函數2當中對參數first和last進行了解引用(*)（而int類型不能進行解引用操作）而報錯。
最后就是我們上面一直說到的模板區間構造函數了，因為該迭代器區間可以是其他容器的迭代器區間，該函數接收到的迭代器的類型是不確定的，所以我們這里需要將該構造函數設計為一個函數模板，在函數體內將該迭代器區間的數據一個個尾插到容器當中即可。
template <class InputIterator>
list(InputIterator first, InputIterator last) //區間構造
{
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;
}
}注意：
1、該區間必須是前閉后開[obj.begin()，obj.end());
拷貝構造的思想是我們是很容易想到的，就是遍歷一遍我們要拷貝的對象obj鏈表，并將obj每個元素的值給this對象的每一個對應的結點，并將其每個結點都鏈接起來。
list(const list<T>& obj) //拷貝構造函數
{
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;
}
}根據我們之前的博客的往歷，這里我們采用現代寫法，及用obj調用拷貝構造函數創建一個臨時對象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語句時就會自動調用析構函數進行釋放內存，故不會造成內存的泄漏等問題。析構函數這里，我就有點偷懶啦，復用了我們下面要模擬實現的pop_front()函數，大致思路就是從頭到尾一個一個刪除結點，并把頭結點也刪除并至空。
~list() //析構函數
{
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);
}上面我們模擬實現了我們的迭代器，并且有普通迭代器和const迭代器。但是我們還要了解迭代器的原理是上面，在之前我們的博客中我們說過并不是每個迭代器都是原生指針，其中我們的list就是封裝了一個指針變量來達到實現iterator的結果。
typedef list_iterator<T,T&,T*> iterator; //普通迭代器 typedef list_iterator<T,const T&,const T*> const_iterator; //常量迭代器
可能有人會疑惑，上面這兩個迭代器不都差不多嘛，只是名字不一樣，為什么不直接在類型上加const，而是在模板參數上指定加上const屬性呢？我們要知道由于const對象只能調用常函數，但是平時我們使用std::list時是不是可以支持 ++、-- 呢？如果是const對象，它只能調用常函數，一旦加上變成const函數，那我們的const迭代器就不能進行++、–、' * '等,而我們要達到的效果是可以進行++、–等，但僅僅是不能其元素的值而已。所以 我們這里封裝了一個模板指針。我們通過模板的參數不同來控制它的讀取操作。
就是將一個指針傳過來，并賦給我們的成員變量m_pnode。
list_iterator(node* pnode)
:m_pnode(pnode)
{}因為我們要實現迭代器的相關遍歷操作例如下面的代碼：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占位符來占位，不然會發生錯誤。
myself& operator++() //重載前置++
{
//由于我們的list是雙向循環鏈表，我們的++，就是指向下一個結點
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是雙向循環鏈表，我們的--就是得到它上一個結點的迭代器
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;
}到了這里可能會有人會問為什么我們不寫迭代器的拷貝構造函數和析構函數呢？
答：這是因為我們的迭代器是用來遍歷容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址，并且這些結點元素析構和拷貝并不歸我們管，結點應該歸我們的list管，所以編譯器默認提供的淺拷貝就已經足夠了。
功能：是用來獲取容器中是否為空。返回值：bool。
bool empty() const //判空
{
return this->begin() == this->end(); //就是begin()與end()同時指向頭結點時的情況
}功能：是用來獲取元素的個數。返回值：size_t(無符號整型)。注意：但是在鏈表中這個接口并不常用。如果頻繁的調用該接口會造成性能的下降。
//遍歷一遍鏈表來得到元素個數，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數，但如果頻繁的調用該接口會造成性能的下降
//此時我們應該在list類中將增加一個記錄元素個數的變量size
//如果有元素插入就增加，刪除就減少
size_t size() const //獲得元素個數
{
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（無返回值）。
void push_back(const T& val) //尾插
{
node* tail = this->m_head->m_prev; //指向尾部結點
node* newnode = new node(val); //創建新結點
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指向新的尾
}功能：在頭部插入一個元素。返回值：void（無返回值）。
void push_front(const T& val) //頭插
{
node* newnode = new node(val); //創建新結點
node* next = this->m_head->m_next; //指向第一個結點
newnode->m_next = next; //將創建的新結點newnode的m_next指向我們原來的第一個元素next
this->m_head->m_next = newnode; //在將我們的頭結點的m_next指向新創建的結點
newnode->m_prev = this->m_head; //在將新結點的m_prev指向頭結點
next->m_prev = newnode; //在將原先第一個結點元素的m_prev指向新創建的結點
}功能：在尾部刪除一個元素。返回值：void（無返回值）。
void pop_back() //尾刪
{
assert(!empty()); //斷言 如果list已經為空，則刪除不了
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; //刪除尾結點
}功能：在頭部刪除一個元素。返回值：void（無返回值）。
void pop_front() //頭刪
{
assert(!empty()); //斷言 如果list已經為空，則刪除不了
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; //刪除第一個結點
}在c++98中我們的insert()函數有如下三種版本：
下面我們就將其模擬實現：
指定位置插入一個元素
功能：在指定位置插入一個元素。返回值：插入的元素的位置的迭代器。
//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
assert(pos.m_pnode != nullptr); //斷言 迭代器是否為空指針錯誤
node* newnode = new node(val); //創建新結點
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在指定位置插入為什么要實現三種重載版本呢？這與上面的構造函數問題是相同類型的，都是與模板區間構造有關，這里就不多贅述了。
指定位置插入區間內的元素
功能：在指定位置插入區間內的元素。返回值：void(無返回值)。注意：1、該區間必須是前閉后開;
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last) //區間插入
{
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;
}
}在C++98中erase()有兩種版本，一個是刪除指定位置，另一個是刪除區間內的元素。如下圖所示：
刪除指定位置
功能：刪除指定位置的元素。返回值：刪除指定位置的元素的下一個結點的迭代器。
//刪除指定位置的元素，返回下一個元素的迭代器，但要注意的是：
//如果刪除的最后一個元素，此時返回的是頭結點也就是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);
}刪除區間內的元素
功能：刪除區間內的元素。返回值：刪除區間內的元素的下一個結點的迭代器。也就是返回last迭代器這個位置。注意： 1、該區間必須是前閉后開;
iterator erase(iterator first, iterator last) //區間刪除
{
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);
}功能：用于清空我們list中的所有元素的值，但不是要把list對象也刪除。返回值：void（無返回值）。
void clear() //清空元素，而不是把整個鏈表刪除掉
{
iterator it = this->begin();
while (it != this->end())
//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
{
++it;
this->pop_front();
}
}功能：swap顧名思義就是交換的意思，這里我們將這個swap作為我們的成員函數，用來交換兩個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()) //構造函數
: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() //無參默認構造函數
{
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個元素構造函數
{
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個元素構造函數
{
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個元素構造函數
{
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) //區間構造
{
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) //拷貝構造函數
{
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() //析構函數
{
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()同時指向頭結點時的情況
}
//遍歷一遍鏈表來得到元素個數，為什么使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數，但如果頻繁的調用該接口會造成性能的下降
//此時我們應該在list類中將增加一個記錄元素個數的變量size
//如果有元素插入就增加，刪除就減少
size_t size() const //獲得元素個數
{
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); //創建新結點
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) //區間插入
{
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已經為空，則刪除不了
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已經為空，則刪除不了
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) //區間刪除
{
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++怎么實現list功能”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
