C++?list模擬實(shí)現(xiàn)過程
一、list的介紹
列表是一種順序容器,它允許在序列中的任何位置執(zhí)行常量時(shí)間插入和刪除操作,并允許在兩個(gè)方向上進(jìn)行迭代。
它的底層是一個(gè)帶頭雙向循環(huán)鏈表,我們直接來看一看整體框架:
// List的節(jié)點(diǎn)類
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_val(val)
,_pPre(nullptr)
,_pNext(nullptr)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
template<class T>
class list
{
typedef list_node<T> node;
public:
//迭代器
typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;
//構(gòu)造
list()
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;
size_t _size;
};
二、迭代器
1、list的迭代器失效問題
- insert,迭代器不失效。
- earse失效。
2、迭代器的功能分類
1、單向迭代器:只能++,不能–。例如單鏈表,哈希表;
2、雙向迭代器:既能++也能–。例如雙向鏈表;
3、隨機(jī)訪問迭代器:能+±-,也能+和-。例如vector和string。
迭代器是內(nèi)嵌類型(內(nèi)部類或定義在類里)
3、list迭代器的模擬實(shí)現(xiàn)
1.list迭代器的引入
對(duì)于vector和string類而言,物理空間是連續(xù)的,原生的指針就是迭代器了(不一定哦,只是可能,版本可能不同),解引用就是數(shù)據(jù)了。
但是對(duì)于這里的list而言,空間是不連續(xù)的,我們知道,迭代器有兩個(gè)特征:
- 解引用
- ++ /–
此時(shí)如果解引用是拿不到數(shù)據(jù)的(空間不連續(xù)),更不用說++指向下一個(gè)結(jié)點(diǎn)了。所以,對(duì)于list的迭代器,原生指針已經(jīng)不符合我們的需求了,我們需要去進(jìn)行特殊處理:進(jìn)行類的封裝。
我們可以通過類的封裝以及運(yùn)算符重載支持,這樣就可以實(shí)現(xiàn)像內(nèi)置類型一樣的運(yùn)算符。
2.普通迭代器
//用類封裝迭代器
template <class T>
struct __list_iterator
{
typedef list_node<T> node;
//用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運(yùn)算符的重載
T& operator*()
{
return _pnode->_data;
}
__list_iterator<T>& operator++()//返回值不要寫成node* operator++(),因?yàn)榈?+返回迭代器
{
//return _pnode->_next;
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
bool operator!=(const __list_iterator<T>& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};
注意:對(duì)于迭代器的拷貝構(gòu)造和賦值重載我們并不需要自己去手動(dòng)實(shí)現(xiàn),編譯器默認(rèn)生成的就是淺拷貝,而我們需要的就是淺拷貝,這也說明了,并不是說如果有指針就需要我們?nèi)?shí)現(xiàn)深拷貝。另外,迭代器通過結(jié)構(gòu)體指針訪問修改鏈表,所以,對(duì)于迭代器我們并不需要構(gòu)造函數(shù),結(jié)點(diǎn)的釋放由鏈表管理。
3.const迭代器
const迭代器的錯(cuò)誤寫法:
typedef __list_iterator<T> iterator; const list<T>::iterator it=lt.begin();
因?yàn)閠ypedef后,const修飾的是迭代器it,只能調(diào)用operator*(),調(diào)不了operator++()。
- 正確寫法:想實(shí)現(xiàn)const迭代器,,需要再寫一個(gè)const版本迭代器的類。
//用類封裝const迭代器
template <class T>
struct __list_const_iterator
{
typedef list_node<T> node;
//用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
__list_const_iterator(node* p)
:_pnode(p)
{}
//迭代器運(yùn)算符的重載
const T& operator*()const
{
return _pnode->_data;
}
__list_const_iterator<T>& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器
{
//return _pnode->_next;//返回類型錯(cuò)誤的
_pnode = _pnode->_next;
return *this;//返回的是迭代器
}
__list_const_iterator<T>& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const __list_const_iterator<T>& it)const
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};
typedef __list_const_iterator<T> const_iterator;
如果是這樣子去實(shí)現(xiàn)的話,我們就會(huì)發(fā)現(xiàn),這兩個(gè)迭代器的實(shí)現(xiàn)并沒有多大的區(qū)別,唯一的區(qū)別就在于operator*的不同。const迭代器和普通迭代器的唯一區(qū)別就是普通迭代器返回T&,可讀可寫,const迭代器返回const T&,可讀不可寫,上面的代碼存在很大的問題:代碼冗余,所以我們應(yīng)該去解決這個(gè)問題:我們可以參考源碼的實(shí)現(xiàn):類模板參數(shù)解決這個(gè)問題,這也是迭代器的強(qiáng)大之處
//用類封裝普通/const迭代器
template <class T,class Ref>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref> Self;
//用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運(yùn)算符的重載
Ref operator*()
{
return _pnode->_data;
}
Self& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì)
{
//return _pnode->_next;//返回類型錯(cuò)誤的
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const Self& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
4、迭代器operator->的重載
迭代器的用法就是模擬指針的行為,如果現(xiàn)在有一個(gè)指向結(jié)構(gòu)的指針,那么就需要用到->來解引用。
//*的重載:返回節(jié)點(diǎn)的數(shù)據(jù)
Ref operator*()
{
return _pnode->_data;
}
//->的重載:返回?cái)?shù)據(jù)的指針
T* operator->()
{
return &_pnode->_data;
}
但是operator->使用T*做返回值類型,這樣無論是普通迭代器和const迭代器都能修改,所以operator->的返回值類型應(yīng)該改為泛型:
template <class T, class Ref,class Ptr>
Ptr operator->()
{
return &_pnode->_data;
}
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
5、迭代器價(jià)值
1、封裝底層實(shí)現(xiàn),不暴露底層實(shí)現(xiàn)的細(xì)節(jié);
2、多種容器提供統(tǒng)一的訪問方式,降低使用成本;
C語(yǔ)言沒有運(yùn)算符重載和引用等語(yǔ)法,是實(shí)現(xiàn)不了迭代器的。
三、增刪查改
1、insert和erase
insert:在pos位置上一個(gè)插入,返回插入位置的迭代器,對(duì)于list的insert迭代器不會(huì)失效,vector失效是因?yàn)閿U(kuò)容導(dǎo)致pos位置造成野指針問題。
iterator insert(iterator pos,const T& x)
{
node* newnode = new node(x);
node* cur = pos._pnode;
node* prev = cur->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
erase:這里的帶頭(哨兵位)頭結(jié)點(diǎn)不可刪除,返回值是刪除位置的下一個(gè),對(duì)于list的erase迭代器是失效的
iterator erase(iterator pos)
{
assert(pos != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
return iterator(next);
}
2、push_back和push_front
void push_back(const T& x)
{
/*node* newnode = new node(x);
node* tail = _head->_prev;
newnode->_prev = tail;
tial->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
3、pop_back和pop_front
尾刪和頭刪,復(fù)用erase即可
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
四、list的構(gòu)造函數(shù)
1、構(gòu)造
默認(rèn)構(gòu)造:
list()
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
我們可以用empty_initialize()來封裝初始化,方便復(fù)用,不用每次都寫:
void empty_initialize()
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
迭代器區(qū)間構(gòu)造:
//迭代器區(qū)間構(gòu)造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_initialize();
while (first != last)
{
push_back(*first);
++first;
}
}
拷貝構(gòu)造:
傳統(tǒng)寫法
list(const list<T>& lt)
{
empty_initialize();
for (const auto& e : lt)
{
push_back(e);
}
}
用范圍for進(jìn)行尾插,但是要注意要加上&,范圍for是*it賦值給給e,又是一個(gè)拷貝,e是T類型對(duì)象,依次取得容器中的數(shù)據(jù),T如果是string類型,不斷拷貝,push_back之后又銷毀。
現(xiàn)代寫法
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list(const list<T>& lt)
{
empty_initialize();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
2、賦值重載
傳統(tǒng)寫法
list<T>& operator=(list<T>& lt)
{
if (this != <)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}
現(xiàn)代寫法
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
3、析構(gòu)
對(duì)于list,有單獨(dú)的clear()接口,list的析構(gòu)可以直接復(fù)用clear(),同時(shí)還需要我們?nèi)メ尫诺纛^結(jié)點(diǎn):
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
類名和類型的區(qū)別
- 普通類:類名等于類型
- 類模板:類名不等價(jià)于類型,例如list類模板類名是list,類型list等。
所以我們平常寫函數(shù)形參和返回值時(shí),總會(huì)帶上形參和返回值的類型:
// 賦值運(yùn)算符重載
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
五、list和vector的對(duì)比
1.vector
vector的優(yōu)點(diǎn)(結(jié)構(gòu)牛):
- 1、支持下標(biāo)的隨機(jī)訪問;
- 2、尾插尾刪效率高(當(dāng)然擴(kuò)容的那一次尾插會(huì)較慢);
- 3、CPU高速緩存命中高(數(shù)據(jù)從緩存加載至CPU中,會(huì)加載連續(xù)的一段數(shù)據(jù),vector因?yàn)榻Y(jié)構(gòu)連續(xù),高速緩存命中高)。
vector的缺點(diǎn):
- 1、非尾插尾刪效率低;
- 2、擴(kuò)容有消耗,并存在一定的空間浪費(fèi)。
vector迭代器失效問題:
- insert/erase均失效。(如果string的insert和erase形參是迭代器,那么也會(huì)失效,但是大部分接口是下標(biāo)傳參,不考慮失效問題,只有幾個(gè)接口是迭代器傳參,需要注意迭代器失效問題)
2、list
list的優(yōu)點(diǎn):
- 1、按需申請(qǐng)釋放,無需擴(kuò)容;
- 2、任意位置插入刪除時(shí)間O(1);(這里說的是插入刪除,不要加上查找的時(shí)間)
list的缺點(diǎn):
- 1、不支持下標(biāo)的隨機(jī)訪問;
- 2、CPU高速緩存命中率低;
- 3、每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外,還需要額外存儲(chǔ)兩個(gè)指針。
| vector | list | |
|---|---|---|
| 底 層 結(jié) 構(gòu) | 動(dòng)態(tài)順序表,一段連續(xù)空間 | 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 |
| 隨 機(jī) 訪 問 | 支持隨機(jī)訪問,訪問某個(gè)元素效率O(1) | 不支持隨機(jī)訪問,訪問某個(gè)元素效率O(N) |
| 插 入 和 刪 除 | 任意位置插入和刪除效率低,需要搬移元素,時(shí)間復(fù)雜度為O(N),插入時(shí)有可能需要增容,增容:開辟新空間,拷貝元素,釋放舊空間,導(dǎo)致效率更低 | 任意位置插入和刪除效率高,不需要搬移元素,時(shí)間復(fù)雜度為O(1) |
| 空 間 利 用 率 | 底層為連續(xù)空間,不容易造成內(nèi)存碎片,空間利用率高,緩存利用率高 | 底層節(jié)點(diǎn)動(dòng)態(tài)開辟,小節(jié)點(diǎn)容易造成內(nèi)存碎片,空間利用率低,緩存利用率低 |
| 迭 代 器 | 原生態(tài)指針 | 對(duì)原生態(tài)指針(節(jié)點(diǎn)指針)進(jìn)行封裝 |
| 迭 代 器 失 效 | 在插入元素時(shí),要給所有的迭代器重新賦值,因?yàn)椴迦朐赜锌赡軙?huì)導(dǎo)致重新擴(kuò)容,致使原來迭代器失效,刪除時(shí),當(dāng)前迭代器需要重新賦值否則會(huì)失效 | 插入元素不會(huì)導(dǎo)致迭代器失效,刪除元素時(shí),只會(huì)導(dǎo)致當(dāng)前迭代器失效,其他迭代器不受影響 |
| 使 用 場(chǎng) 景 | 需要高效存儲(chǔ),支持隨機(jī)訪問,不關(guān)心插入刪除效率 | 大量插入和刪除操作,不關(guān)心隨機(jī)訪問 |
六、模擬實(shí)現(xiàn)list整體代碼
namespace fx
{
// List的節(jié)點(diǎn)類
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_val(val)
,_pPre(nullptr)
,_pNext(nullptr)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器類
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
:_pNode(pNode)
{}
ListIterator(const Self& l)
{
_pNode = l._pNode;
}
Ref operator*()
{
return _pNode->_val
}
Ptr operator->()
{
}
Self& operator++()
{
return _pNode->_pNext;
}
Self operator++(int)
{
Self tmp(*this);
_pNode = _pNode->_pNext;
return tmp;
}
Self& operator--()
{
return _pNode->_pPre;
}
Self& operator--(int)
{
Self tmp(*this);
_pNode = _pNode->_pPre;
return tmp;
}
bool operator!=(const Self& l)
{
return _pNode != l._pNode;
}
bool operator==(const Self& l)
{
return _pNode == l._pNode;
}
private:
PNode _pNode;
};
//list類
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
public:
///////////////////////////////////////////////////////////////
// List的構(gòu)造
void CreateHead()
{
Node* _pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size = 0;
}
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
wihle(first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)
{
CreateHead();
for (auto& e : lt)
{
push_back(e);
}
}
list<T>& operator=(const list<T> l)
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
///////////////////////////////////////////////////////////////
// List Iterator
iterator begin()
{
return _pHead->_pNext;
}
iterator end()
{
return _pHead;
}
const_iterator begin()
{
return _head->_next;
}
const_iterator end()
{
return _pHead;
}
///////////////////////////////////////////////////////////////
// List Capacity
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}
////////////////////////////////////////////////////////////
// List Access
T& front()
{
return *begin();
}
const T& front()const
{
return *begin();
}
T& back()
{
return _head->_prev->_val;
}
const T& back()const
{
return _head->_prev->_val;
}
////////////////////////////////////////////////////////////
// List Modify
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
// 在pos位置前插入值為val的節(jié)點(diǎn)
iterator insert(iterator pos, const T& val)
{
Node* newnode = new Node;
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
}
// 刪除pos位置的節(jié)點(diǎn),返回該節(jié)點(diǎn)的下一個(gè)位置
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& l)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
private:
PNode _pHead;
size_t _size;
};
};
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
C++開發(fā)protobuf動(dòng)態(tài)解析工具
這篇文章主要為大家介紹了C++開發(fā)protobuf動(dòng)態(tài)解析工具實(shí)現(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01
Qt中QtWebEngine加載本地網(wǎng)頁(yè)跨域問題的總結(jié)
本文主要介紹了Qt中QtWebEngine加載本地網(wǎng)頁(yè)跨域問題的總結(jié),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
C語(yǔ)言多功能動(dòng)態(tài)通訊錄實(shí)現(xiàn)示例
這篇文章主要為大家介紹了C語(yǔ)言多功能動(dòng)態(tài)通訊錄實(shí)現(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01
c 調(diào)用python出現(xiàn)異常的原因分析
本篇文章是對(duì)使用c語(yǔ)言調(diào)用python出現(xiàn)異常的原因進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05

