溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“C++之list容器模擬怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++之list容器模擬怎么實現”文章吧。
list模擬實現主要包括四個類：節點類、迭代器類、反向迭代器類、list類。
list底層結構：
因為list的底層空間不連續，所以迭代器不能使用原生態的指針，將節點類型的指針封裝成類，重載解引用及自增等常用操作。list可以保存多種數據類型，所以這些類都寫成類模板
list底層是帶頭結點的雙向循環鏈表，先實現節點類，給成類模板的形式，便于插入不同類型的數據。
template<class T>
struct ListNode
{
ListNode<T>* prev;
ListNode<T>* next;
T data;//要在鏈表中保存的數據類型
ListNode(const T& value = T())
:prev(nullptr)
, next(nullptr)
, data(value)
{ }
};定義新節點的方法：
ListNode<變量類型>*變量名=new ListNode(value)；
迭代器類模板有三個參數
T：迭代器指向的元素類型
Ref：返回的引用類型
Ptr：返回的指針類型
Ref和Ptr一般不寫成T&和T*。
迭代器類的成員變量就是節點類型的指針
Node* _pNode;//成員變量，節點類型指針
編譯器默認的構造函數是無參的，構造函數需要給出
ListIterator(Node* pNode = nullptr)
:_pNode(pNode)
{}返回節點中保存的數據
Ref operator*()
{
return _pNode->data;
}返回節點中保存的數據的地址
Ptr operator->()
{
return &_pNode->data;
}->的重載只對內置類型有意義：
前置++
返回值是迭代器自身類型的引用，前面已經將ListIterator<T, Ref, Ptr>重命名位Self，表示迭代器自身的類型。
Self& operator++()
{
_pNode = _pNode->next;
return *this;
}后置++
定義臨時變量，返回自增前的值
Self operator++(int)
{
Self temp(*this);
_pNode = _pNode->next;
return temp;
}“–”
與++原理相同
Self& operator--()
{
_pNode = _pNode->prev;
return (*this);
}
Self operator--(int)
{
Self temp(*this);
_pNode = _pNode->prev;
return temp;
}比較兩個迭代器中封裝的指針
bool operator!=(const Self& it)
{
return _pNode != it._pNode;
}
bool operator==(const Self& it)
{
return _pNode == it._pNode;
}反向迭代器可以對迭代器類進行復用
因為類外訪問靜態成員變量時也會使用類名::變量名的方式，所以對迭代器類中的Reference和Pointer進行重命名時要加上typename,明確告訴編譯器要重命名的是一個數據類型。否則編譯器會報錯：
反向迭代器對迭代器類進行復用
private: Iterator _it;//正向迭代器
反向迭代器的解引用要做特殊處理，返回的是對迭代器–的值
Reference operator*()
{
//*做特殊處理，先--,再解引用返回
auto temp = _it;
--temp;
return *temp;
}復用*的重載，返回value的地址
Pointer operator->()
{
return &(operator*());
}反向迭代器的++即為正向迭代器的–
Self operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self temp(*this);
--_it;
return *this;
}反向迭代器的–用正向迭代器的++替代
Self operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}比較反向迭代器類中保存的正向迭代器，復用正向迭代器中的比較方法
bool operator==(const Self& rit)
{
return _it == rit;
}
bool operator!=(const Self& rit)
{
return _it == rit._it;
}
list的成員變量只有一個head指針，指向鏈表的第一個節點
private: Node* head;
空對象
list()
{
CreatHead();
}創造頭節點的方法：
//提供一個創造頭結點的方法
void CreatHead()
{
//調用節點類的構造方法
head = new Node();
head->next = head;
head->prev = head;
}0000000
new申請空間，令head指向這段空間，head的next和prev都指向自己。
n個T類型元素
調用push_back方法，創造頭節點后，不斷進行尾插直到元素個數等于n
list(int n, const T& value = T())
{
CreatHead();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}拷貝構造
復用push_back
list(const list<T>& l)
{
CreatHead();
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}迭代器構造
將迭代器構造方法寫成函數模板，可以傳入不同類型的迭代器來構造list對象
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
CreatHead();
while (first != last)
{
push_back(*first);
first++;
}
}賦值運算符重載
與拷貝構造寫法相同
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
clear();//先清空當前對象中的節點
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}
return *this;
}析構
清空當前對象，釋放頭節點空間，將頭節點置空
~list()
{
clear();
delete head;
head = nullptr;
}正向迭代器
begin
此處的iterator是對ListIterator<T, T&, T*>的重命名，這里會返回一個ListIterator<T, T&, T*>類對象
iterator begin()
{
//iterator it(head->next);
//return it;
//head->next是傳遞給迭代器類對象構造函數的參數,調用iterator的構造函數
return iterator(head->next);//構造匿名對象返回
}end
iterator end()
{
return iterator(head);
}const類型迭代器
iterator和const_iterator 是兩個不同的類：
兩者使用的是相同的類模板，但是傳遞的參數不同，最終實例化的也是不同的類。
cbegin&cend
const_iterator cbegin()const
{
return const_iterator(head->next);
}
const_iterator cend()const
{
return const_iterator(head);
}rbegin&rend
返回正向迭代器的end和begin
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}crbegin&crend
復用正向迭代器的cend和cbegin
const_reverse_iteraotr crbegin()const
{
return const_reverse_iteraotr(cend());
}
const_reverse_iteraotr crend()const
{
return const_reverse_iteraotr(cbegin());
}size
遍歷鏈表，統計節點個數
size_t size()
{
auto it = cbegin();
size_t count = 0;
while (it != cend())
{
++count;
++it;
}
return count;
}empty
如果head->next是head本身則表明鏈表為空
bool empty()
{
return head->next == head;
}resize
改變節點個數，若新的節點個數大于舊的，則調用push_back填充元素；若新的節點個數小于原來的調用pop_back尾刪
front
復用迭代器解引用的方法，返回begin()位置元素
T& front()
{
return *begin();
}
const T& front()const
{
return *cbegin();
}back
back表示最后一個元素，但是end()指向的是最后一個元素的下一個位置，需要定義臨時變量，不能直接對end()進行- -。
T& back()
{
auto it = end();
//return --end()//錯誤寫法
it--;
return *it;
}
const T& back()const
{
auto it = end();
it--;
return *it;
}定義一個打印鏈表的函數模板，檢驗方法。通過迭代器遍歷鏈表，打印每一個節點的數據。
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.cbegin();
while (it != l.cend())
{
cout << *it << " ";
++it;
}
cout << endl;
}尾插與尾刪
push_back
復用insert方法在end位置插入
void push_back(const T& value)
{
insert(end(), value);
}pop_back
先判斷鏈表是否為空，復用erase方法在end的前一個位置進行插入
void pop_back()
{
if (empty())
{
return;
}
auto it = end();
it--;
erase(it);
}復用insert與erase方法，在begin()位置進行插入或刪除
void push_front(const T& value = T())
{
insert(begin(), value);
}
void pop_front()
{
erase(begin());
}?insert
任意位置的插入：申請新節點，連接新節點與鏈表，斷開舊的連接。
這里傳入的參數是一個迭代器類對象，不能直接進行操作，要對對象中封裝的_pNode指針進行操作。
返回值是新插入的節點的迭代器，所以要用申請的新節點的指針newnode構造一個迭代器類對象返回，不能直接返回newnode
iterator insert(iterator Insertpos, const T& value)
{
Node* newnode = new Node(value);
Node* pos = Insertpos._pNode;//_pNode是節點類型的指針
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
//return newnode;
//?迭代器是封裝的Node*指針，此時不能再返回newnode
return iterator(newnode);//構造匿名對象返回
}?erase
任意位置的刪除：分別改變前后兩個節點的next和prev指針的指向即可
iterator erase(iterator Erasepos)
{
Node* pos = Erasepos._pNode;
Node* ret = pos->next;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
delete pos;
return iterator(ret);
}區間刪除：復用單個節點刪除的方法，遍歷要刪除的區間。
要用接收erase的返回值，防止迭代器失效
iterator erase(iterator first, iterator last)
{
auto it = first;
while (it != last)
{
//it=erase(it);
//后置++會構造臨時對象返回，不會導致迭代器失效
erase(it++);
}
return it;
}clear&swap
clear復用erase區間刪除的方法，從begin刪除到end位置；
swap方法調用標準庫中的swap，交換兩個鏈表的頭節點。
void clear()
{
erase(begin(), end());
}
void swap(list<T>& l)
{
std::swap(head, l.head);
}#include<iostream>
#include<vector>
using namespace std;
namespace ZH
{
/
//節點類模板,
template<class T>
struct ListNode
{
ListNode<T>* prev;
ListNode<T>* next;
T data;
ListNode(const T& value = T())
:prev(nullptr)
, next(nullptr)
, data(value)
{ }
};
/
//迭代器類模板
//list的迭代器不能使用原生態的指針，要進行封裝
//T：迭代器指向的元素類型
//Ref：給operator*使用，返回引用類型，不要寫成T&
//Ptr：返回值使用，不要寫成T*
template<class T,class Ref,class Ptr>
class ListIterator
{
public:
typedef ListNode<T> Node;//化簡節點類的名字
typedef Ref Reference;//在反向迭代器類中使用
typedef Ptr Pointer;
typedef ListIterator<T, Ref, Ptr> Self;//簡化迭代器類的名字
//構造函數
ListIterator(Node* pNode=nullptr)
:_pNode(pNode)
{}
//重載部分需要使用的運算符即可：*、->、++、--、==
Ref operator*()
{
return _pNode->data;
}
//T為自定義類型時有意義,
Ptr operator->()
{
return &_pNode->data;
}
//前置++，返回值是迭代器自身類型的引用
Self& operator++()
{
_pNode = _pNode->next;
return *this;
}
//后置
Self operator++(int)
{
Self temp(*this);
_pNode = _pNode->next;
return temp;
}
Self& operator--()
{
_pNode = _pNode->prev;
return (*this);
}
Self operator--(int)
{
Self temp(*this);
_pNode = _pNode ->prev;
return temp;
}
//迭代器能進行比較
bool operator!=(const Self& it)
{
return _pNode != it._pNode;
}
bool operator==(const Self& it)
{
return _pNode == it._pNode;
}
Node* _pNode;//成員變量，節點類型指針
};
//反向迭代器類模板，對迭代器進行復用
template<class Iterator>
class ListReverseIterator
{
public:
//typedef Iterator::Reference Reference;
//typedef Iterator::Pointer Pointer;
typedef typename Iterator::Reference Reference;//typename指定Reference是Iterator中的數據類型
typedef typename Iterator::Pointer Pointer;
typedef ListReverseIterator<Iterator> Self;
ListReverseIterator(Iterator it)
: _it(it)
{ }
Reference operator*()
{
//*做特殊處理，先--,再解引用返回
auto temp = _it;
--temp;
return *temp;
}
Pointer operator->()
{
return &(operator*());
}
Self operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self temp(*this);
--_it;
return *this;
}
Self operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
bool operator==(const Self& rit)
{
return _it == rit;
}
bool operator!=(const Self& rit)
{
return _it == rit._it;
}
private:
Iterator _it;//正向迭代器
};
template<class T>
class list
{
typedef ListNode<T> Node;
//typedef Node* iterator;//不能使用Node*作迭代器
//迭代器
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator< T, const T&, const T*> const_iterator;
typedef ListReverseIterator<iterator> reverse_iterator;
typedef ListReverseIterator<const_iterator> const_reverse_iteraotr;
public:
///
//構造
list()
{
CreatHead();
}
list(int n, const T& value=T())
{
CreatHead();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
list(const list<T>& l)
{
CreatHead();
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}
//迭代器區間構造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
CreatHead();
while (first != last)
{
push_back(*first);
first++;
}
}
//賦值運算符重載
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
clear();//先清空當前對象中的節點
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}
return *this;
}
~list()
{
clear();
delete head;
head = nullptr;
}
public:
//迭代器
iterator begin()
{
//iterator it(head->next);
//return it;
//iterator是對ListIterator<T, T&, T*>的重命名
//這里會返回一個ListIterator<T, T&, T*>類對象
//head->next是傳遞給迭代器類對象構造函數的參數,調用iterator的構造函數
return iterator(head->next);//構造匿名對象返回
}
iterator end()
{
return iterator(head);
}
//const類型迭代器
const_iterator cbegin()const
{
return const_iterator(head->next);
}
const_iterator cend()const
{
return const_iterator(head);
}
//反向迭代器
//反向迭代器的成員變量是一個迭代器類對象
//end()即為傳遞給反向迭代器類構造函數的參數
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//反向const類型迭代器
const_reverse_iteraotr crbegin()const
{
return const_reverse_iteraotr(cend());
}
const_reverse_iteraotr crend()const
{
return const_reverse_iteraotr(cbegin());
}
/
//容量
size_t size()
{
auto it = cbegin();
size_t count = 0;
while (it != cend())
{
++count;
++it;
}
return count;
}
bool empty()
{
return head->next == head;
}
void resize(int newsize,const T& value=T())
{
size_t oldsize = size();
if (newsize > oldsize)
{
while (oldsize++<newsize)
{
push_back(value);
}
}
if (newsize < oldsize)
{
while (oldsize-- < newsize)
{
pop_back();
}
}
}
///
//元素訪問
T& front()
{
return *begin();
}
const T& front()const
{
return *cbegin();
}
T& back()
{
auto it = end();
it--;
return *it;
}
const T& back()const
{
auto it = end();
it--;
return *it;
}
/
//元素修改
void push_back(const T& value)
{
insert(end(), value);
}
void pop_back()
{
if (empty())
{
return;
}
auto it = end();
it--;
erase(it);
}
void push_front(const T& value = T())
{
//Node* pos = head->next;
/*Node* newnode = new Node(value);
newnode->next = head->next;
newnode->prev = head;
head->next->prev = newnode;
head->next = newnode;*/
//復用insert
insert(begin(), value);
}
void pop_front()
{
erase(begin());
}
//?insert
// iterator是ListIterator<T, T&, T*>
iterator insert(iterator Insertpos, const T& value)
{
Node* newnode = new Node(value);
Node* pos = Insertpos._pNode;//_pNode是節點類型的指針
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
//return newnode;
//?迭代器是封裝的Node*指針，此時不能再返回newnode
return iterator(newnode);//構造匿名對象返回
}
//?erase
iterator erase(iterator Erasepos)
{
Node* pos = Erasepos._pNode;
Node* ret = pos->next;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
delete pos;
return iterator(ret);
}
iterator erase(iterator first, iterator last)
{
auto it = first;
while (it != last)
{
//it=erase(it);
erase(it++);
}
return it;
}
void clear()
{
erase(begin(), end());
}
void swap(list<T>& l)
{
std::swap(head, l.head);
}
private:
//提供一個創造頭結點的方法
void CreatHead()
{
//調用節點類的構造方法
head = new Node();
head->next = head;
head->prev = head;
}
private:
Node* head;
};
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.cbegin();
while (it != l.cend())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
void Test1()
{
ZH::list<int> l1;
ZH::list<int> l2(3, 1);
PrintList(l2);
ZH::list<int> l3(l2.begin(), l2.end());
PrintList(l3);
vector<int> v{ 0,1,2,3,4 };
ZH::list<int> l4(v.begin(), v.end());
PrintList(l4);
}
void Test2()
{
vector<int> v{ 1,2,3,4 };
ZH::list<int> L1(v.begin(), v.end());
L1.push_back(5);
L1.push_back(6);
L1.push_front(0);
PrintList(L1);
L1.pop_back();
L1.pop_front();
PrintList(L1);
L1.erase(--L1.end());
PrintList(L1);
}
void Test3()
{
ZH::list<int> L1;
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
L1.push_front(0);
PrintList(L1);
L1.resize(6, 5);
PrintList(L1);
}
struct A
{
int a;
int b;
int c;
};
void Test4()
{
A aa{ 1,2,3 };
A bb{ 4,5,6 };
A cc{ 7,8,9 };
ZH::list<A> L;
L.push_back(aa);
L.push_back(bb);
L.push_back(cc);
auto it = L.begin();
while (it != L.end())
{
//?it->得到的是節點的地址
//本應是it->->a，編譯器做了特殊處理
cout << it->a << " ";
it++;
}
cout << endl;
}
void Test5()
{
ZH::list<int> L1;
L1.push_back(0);
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
PrintList(L1);
cout << L1.back() << endl;
cout << L1.front() << endl;
cout << L1.size() << endl;
L1.clear();
cout << L1.size() << endl;
}
void Test6()
{
ZH::list<int> L1;
L1.push_back(0);
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
PrintList(L1);
//區間刪除
/*L1.erase(L1.begin(), L1.end());
PrintList(L1);*/
ZH::list<int> L2;
L2.push_back(1);
L2.push_back(2);
L2.push_back(3);
L2.push_back(4);
L2.push_back(5);
PrintList(L2);
L1.swap(L2);
PrintList(L1);
PrintList(L2);
}
int main()
{
Test6();
system("pause");
return 0;
}以上就是關于“C++之list容器模擬怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
