C++之list容器模擬實現(xiàn)方式
更新時間：2023年02月05日 14:03:17 作者：安河橋畔
這篇文章主要介紹了C++之list容器模擬實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
總述
list模擬實現(xiàn)主要包括四個類：節(jié)點類、迭代器類、反向迭代器類、list類。
list底層結(jié)構(gòu)：
因為list的底層空間不連續(xù)，所以迭代器不能使用原生態(tài)的指針，將節(jié)點類型的指針封裝成類，重載解引用及自增等常用操作。list可以保存多種數(shù)據(jù)類型，所以這些類都寫成類模板
一、節(jié)點類
list底層是帶頭結(jié)點的雙向循環(huán)鏈表，先實現(xiàn)節(jié)點類，給成類模板的形式，便于插入不同類型的數(shù)據(jù)。
template<class T>
struct ListNode
{
ListNode<T>* prev;
ListNode<T>* next;
T data;//要在鏈表中保存的數(shù)據(jù)類型
ListNode(const T& value = T())
:prev(nullptr)
, next(nullptr)
, data(value)
{ }
};
定義新節(jié)點的方法：
ListNode<變量類型>*變量名=new ListNode(value)；
二、迭代器類
迭代器類模板有三個參數(shù)
- T：迭代器指向的元素類型
- Ref：返回的引用類型
- Ptr：返回的指針類型
Ref和Ptr一般不寫成T&和T*。
成員變量
迭代器類的成員變量就是節(jié)點類型的指針
Node* _pNode;//成員變量，節(jié)點類型指針
構(gòu)造函數(shù)
編譯器默認的構(gòu)造函數(shù)是無參的，構(gòu)造函數(shù)需要給出
ListIterator(Node* pNode = nullptr)
:_pNode(pNode)
{}
*重載
返回節(jié)點中保存的數(shù)據(jù)
Ref operator*()
{
return _pNode->data;
}
->重載
返回節(jié)點中保存的數(shù)據(jù)的地址
Ptr operator->()
{
return &_pNode->data;
}
->的重載只對內(nèi)置類型有意義：
“++”
前置++
返回值是迭代器自身類型的引用，前面已經(jīng)將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;
}
三、反向迭代器類
反向迭代器可以對迭代器類進行復用
因為類外訪問靜態(tài)成員變量時也會使用類名::變量名的方式，所以對迭代器類中的Reference和Pointer進行重命名時要加上typename,明確告訴編譯器要重命名的是一個數(shù)據(jù)類型。否則編譯器會報錯：
成員變量
反向迭代器對迭代器類進行復用
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類
成員變量
list的成員變量只有一個head指針，指向鏈表的第一個節(jié)點
private: Node* head;
構(gòu)造相關(guān)
空對象
list()
{
CreatHead();
}
創(chuàng)造頭節(jié)點的方法：
//提供一個創(chuàng)造頭結(jié)點的方法
void CreatHead()
{
//調(diào)用節(jié)點類的構(gòu)造方法
head = new Node();
head->next = head;
head->prev = head;
}
0000000
new申請空間，令head指向這段空間，head的next和prev都指向自己。
n個T類型元素
調(diào)用push_back方法，創(chuàng)造頭節(jié)點后，不斷進行尾插直到元素個數(shù)等于n
list(int n, const T& value = T())
{
CreatHead();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
拷貝構(gòu)造
復用push_back
list(const list<T>& l)
{
CreatHead();
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}
迭代器構(gòu)造
將迭代器構(gòu)造方法寫成函數(shù)模板，可以傳入不同類型的迭代器來構(gòu)造list對象
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
CreatHead();
while (first != last)
{
push_back(*first);
first++;
}
}
賦值運算符重載
與拷貝構(gòu)造寫法相同
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
clear();//先清空當前對象中的節(jié)點
auto it = l.cbegin();
while (it != l.cend())
{
push_back(*it);
it++;
}
}
return *this;
}
析構(gòu)
清空當前對象，釋放頭節(jié)點空間，將頭節(jié)點置空
~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是傳遞給迭代器類對象構(gòu)造函數(shù)的參數(shù),調(diào)用iterator的構(gòu)造函數(shù)
return iterator(head->next);//構(gòu)造匿名對象返回
}
end
iterator end()
{
return iterator(head);
}
const類型迭代器
iterator和const_iterator 是兩個不同的類：
兩者使用的是相同的類模板，但是傳遞的參數(shù)不同，最終實例化的也是不同的類。
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
遍歷鏈表，統(tǒng)計節(jié)點個數(shù)
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
改變節(jié)點個數(shù)，若新的節(jié)點個數(shù)大于舊的，則調(diào)用push_back填充元素；若新的節(jié)點個數(shù)小于原來的調(diào)用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;
}
打印鏈表
定義一個打印鏈表的函數(shù)模板，檢驗方法。通過迭代器遍歷鏈表，打印每一個節(jié)點的數(shù)據(jù)。
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
任意位置的插入：申請新節(jié)點，連接新節(jié)點與鏈表，斷開舊的連接。
這里傳入的參數(shù)是一個迭代器類對象，不能直接進行操作，要對對象中封裝的_pNode指針進行操作。
返回值是新插入的節(jié)點的迭代器，所以要用申請的新節(jié)點的指針newnode構(gòu)造一個迭代器類對象返回，不能直接返回newnode
iterator insert(iterator Insertpos, const T& value)
{
Node* newnode = new Node(value);
Node* pos = Insertpos._pNode;//_pNode是節(jié)點類型的指針
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
//return newnode;
//?迭代器是封裝的Node*指針，此時不能再返回newnode
return iterator(newnode);//構(gòu)造匿名對象返回
}
?erase
任意位置的刪除：分別改變前后兩個節(jié)點的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);
}
區(qū)間刪除：復用單個節(jié)點刪除的方法，遍歷要刪除的區(qū)間。
要用接收erase的返回值，防止迭代器失效
iterator erase(iterator first, iterator last)
{
auto it = first;
while (it != last)
{
//it=erase(it);
//后置++會構(gòu)造臨時對象返回，不會導致迭代器失效
erase(it++);
}
return it;
}
clear&swap
- clear復用erase區(qū)間刪除的方法，從begin刪除到end位置；
- swap方法調(diào)用標準庫中的swap，交換兩個鏈表的頭節(jié)點。
void clear()
{
erase(begin(), end());
}
void swap(list<T>& l)
{
std::swap(head, l.head);
}
附：完整list類，含測試用例
#include<iostream>
#include<vector>
using namespace std;
namespace ZH
{
/
//節(jié)點類模板,
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ài)的指針，要進行封裝
//T：迭代器指向的元素類型
//Ref：給operator*使用，返回引用類型，不要寫成T&
//Ptr：返回值使用，不要寫成T*
template<class T,class Ref,class Ptr>
class ListIterator
{
public:
typedef ListNode<T> Node;//化簡節(jié)點類的名字
typedef Ref Reference;//在反向迭代器類中使用
typedef Ptr Pointer;
typedef ListIterator<T, Ref, Ptr> Self;//簡化迭代器類的名字
//構(gòu)造函數(shù)
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;//成員變量，節(jié)點類型指針
};
//反向迭代器類模板，對迭代器進行復用
template<class Iterator>
class ListReverseIterator
{
public:
//typedef Iterator::Reference Reference;
//typedef Iterator::Pointer Pointer;
typedef typename Iterator::Reference Reference;//typename指定Reference是Iterator中的數(shù)據(jù)類型
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:
///
//構(gòu)造
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++;
}
}
//迭代器區(qū)間構(gòu)造
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();//先清空當前對象中的節(jié)點
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是傳遞給迭代器類對象構(gòu)造函數(shù)的參數(shù),調(diào)用iterator的構(gòu)造函數(shù)
return iterator(head->next);//構(gòu)造匿名對象返回
}
iterator end()
{
return iterator(head);
}
//const類型迭代器
const_iterator cbegin()const
{
return const_iterator(head->next);
}
const_iterator cend()const
{
return const_iterator(head);
}
//反向迭代器
//反向迭代器的成員變量是一個迭代器類對象
//end()即為傳遞給反向迭代器類構(gòu)造函數(shù)的參數(shù)
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是節(jié)點類型的指針
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
//return newnode;
//?迭代器是封裝的Node*指針，此時不能再返回newnode
return iterator(newnode);//構(gòu)造匿名對象返回
}
//?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:
//提供一個創(chuàng)造頭結(jié)點的方法
void CreatHead()
{
//調(diào)用節(jié)點類的構(gòu)造方法
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->得到的是節(jié)點的地址
//本應是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);
//區(qū)間刪除
/*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;
}
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
再開發(fā)視頻編輯 SDK，SDK的回調(diào)接口設(shè)計成 C 風格，結(jié)構(gòu)中放著一些函數(shù)指針,既然對外接口是 C++，為什么不直接使用 C++ 的虛函數(shù)？這篇文章便對這一問題做個詳細介紹,需要的朋友可以參考一下2021-09-09
這篇文章主要給大家介紹了關(guān)于利用C語言如何實現(xiàn)一些簡單圖形的打印的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
解讀堆排序算法及用C++實現(xiàn)基于最大堆的堆排序示例
把待排序的數(shù)組構(gòu)造出最大堆是進行堆排序操作的基本方法,這里將帶大家來解讀堆排序算法及用C++實現(xiàn)基于最大堆的堆排序示例,首先從堆排序的概念開始:2016-06-06
這篇文章主要為大家詳細介紹了C++中單例模式的相關(guān)知識，并給出單例模式日志實現(xiàn)，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2023-04-04
C++與QML進行數(shù)據(jù)交互實現(xiàn)方式介紹
迫于無奈開始寫android的程序，以前使用QWidget的方式試過，雖然界面可以實現(xiàn)，但是最后調(diào)用攝像頭時，未能成功，再沒有繼續(xù)。這幾天開始使用qml進行嘗試，在使用的過程中，其中的一個難點，就是在qml與c++中數(shù)據(jù)的交互2022-09-09
這篇文章主要介紹了C語言實現(xiàn)散列表（哈希Hash表)實例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
C程序函數(shù)調(diào)用&系統(tǒng)調(diào)用
這篇文章主要介紹了C程序函數(shù)調(diào)用&系統(tǒng)調(diào)用,需要的朋友可以參考下2016-09-09
本文介紹了一個完整的INI文件類的實現(xiàn),包含讀取和寫入操作,通過IniFile.h頭文件和IniFile.cpp實現(xiàn)文件,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-10-10![C語言變長數(shù)組 struct中char data[0]的用法詳解](http://img.jbzj.com/images/xgimg/bcimg8.png)
C語言變長數(shù)組 struct中char data[0]的用法詳解
下面小編就為大家?guī)硪黄狢語言變長數(shù)組 struct中char data[0]的用法詳解。小編覺得挺不錯的現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
解析VC中創(chuàng)建DLL,導出全局變量,函數(shù)和類的深入分析
本篇文章是對VC中創(chuàng)建DLL,導出全局變量,函數(shù)和類進行了詳細的分析介紹，需要的朋友參考下2013-05-05