C++?list模擬實現(xiàn)過程
更新時間：2025年09月09日 14:51:05 作者：Filex;
list是基于雙向循環(huán)鏈表的順序容器,支持O(1)插入刪除,迭代器分類明確,insert不失效而erase導(dǎo)致當(dāng)前迭代器失效,與vector對比,list空間利用率低但靈活,適合頻繁增刪操作,通過迭代器封裝實現(xiàn)統(tǒng)一訪問接口
一、list的介紹
列表是一種順序容器，它允許在序列中的任何位置執(zhí)行常量時間插入和刪除操作，并允許在兩個方向上進行迭代。
它的底層是一個帶頭雙向循環(huán)鏈表，我們直接來看一看整體框架：
// List的節(jié)點類
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、隨機訪問迭代器：能+±-，也能+和-。例如vector和string。
迭代器是內(nèi)嵌類型（內(nèi)部類或定義在類里）
3、list迭代器的模擬實現(xiàn)
1.list迭代器的引入
對于vector和string類而言，物理空間是連續(xù)的，原生的指針就是迭代器了（不一定哦，只是可能，版本可能不同），解引用就是數(shù)據(jù)了。
但是對于這里的list而言，空間是不連續(xù)的，我們知道，迭代器有兩個特征：
- 解引用
- ++ /–
此時如果解引用是拿不到數(shù)據(jù)的（空間不連續(xù)），更不用說++指向下一個結(jié)點了。所以，對于list的迭代器，原生指針已經(jīng)不符合我們的需求了，我們需要去進行特殊處理：進行類的封裝。
我們可以通過類的封裝以及運算符重載支持，這樣就可以實現(xiàn)像內(nèi)置類型一樣的運算符。
2.普通迭代器
//用類封裝迭代器
template <class T>
struct __list_iterator
{
typedef list_node<T> node;
//用節(jié)點的指針進行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
T& operator*()
{
return _pnode->_data;
}
__list_iterator<T>& operator++()//返回值不要寫成node* operator++()，因為迭代器++返回迭代器
{
//return _pnode->_next;
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
bool operator!=(const __list_iterator<T>& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
注意：對于迭代器的拷貝構(gòu)造和賦值重載我們并不需要自己去手動實現(xiàn)，編譯器默認(rèn)生成的就是淺拷貝，而我們需要的就是淺拷貝，這也說明了，并不是說如果有指針就需要我們?nèi)崿F(xiàn)深拷貝。另外，迭代器通過結(jié)構(gòu)體指針訪問修改鏈表，所以，對于迭代器我們并不需要構(gòu)造函數(shù)，結(jié)點的釋放由鏈表管理。
3.const迭代器
const迭代器的錯誤寫法：
typedef __list_iterator<T> iterator; const list<T>::iterator it=lt.begin();
因為typedef后，const修飾的是迭代器it，只能調(diào)用operator*(),調(diào)不了operator++()。
- 正確寫法：想實現(xiàn)const迭代器，，需要再寫一個const版本迭代器的類。
//用類封裝const迭代器
template <class T>
struct __list_const_iterator
{
typedef list_node<T> node;
//用節(jié)點的指針進行構(gòu)造
__list_const_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
const T& operator*()const
{
return _pnode->_data;
}
__list_const_iterator<T>& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器
{
//return _pnode->_next;//返回類型錯誤的
_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;//封裝一個節(jié)點的指針
};
typedef __list_const_iterator<T> const_iterator;
如果是這樣子去實現(xiàn)的話，我們就會發(fā)現(xiàn)，這兩個迭代器的實現(xiàn)并沒有多大的區(qū)別，唯一的區(qū)別就在于operator*的不同。const迭代器和普通迭代器的唯一區(qū)別就是普通迭代器返回T&，可讀可寫，const迭代器返回const T&,可讀不可寫，上面的代碼存在很大的問題：代碼冗余，所以我們應(yīng)該去解決這個問題：我們可以參考源碼的實現(xiàn)：類模板參數(shù)解決這個問題，這也是迭代器的強大之處
//用類封裝普通/const迭代器
template <class T,class Ref>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref> Self;
//用節(jié)點的指針進行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
Ref operator*()
{
return _pnode->_data;
}
Self& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
{
//return _pnode->_next;//返回類型錯誤的
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const Self& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
4、迭代器operator->的重載
迭代器的用法就是模擬指針的行為，如果現(xiàn)在有一個指向結(jié)構(gòu)的指針，那么就需要用到->來解引用。
//*的重載：返回節(jié)點的數(shù)據(jù)
Ref operator*()
{
return _pnode->_data;
}
//->的重載：返回數(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、迭代器價值
1、封裝底層實現(xiàn)，不暴露底層實現(xiàn)的細節(jié)；
2、多種容器提供統(tǒng)一的訪問方式，降低使用成本；
C語言沒有運算符重載和引用等語法，是實現(xiàn)不了迭代器的。
三、增刪查改
1、insert和erase
insert：在pos位置上一個插入，返回插入位置的迭代器，對于list的insert迭代器不會失效，vector失效是因為擴容導(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é)點不可刪除，返回值是刪除位置的下一個，對于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進行尾插，但是要注意要加上&，范圍for是*it賦值給給e，又是一個拷貝，e是T類型對象，依次取得容器中的數(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)
對于list，有單獨的clear()接口，list的析構(gòu)可以直接復(fù)用clear()，同時還需要我們?nèi)メ尫诺纛^結(jié)點：
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
類名和類型的區(qū)別
- 普通類：類名等于類型
- 類模板：類名不等價于類型，例如list類模板類名是list,類型list等。
所以我們平常寫函數(shù)形參和返回值時，總會帶上形參和返回值的類型：
// 賦值運算符重載
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
五、list和vector的對比
1.vector
vector的優(yōu)點（結(jié)構(gòu)牛）：
- 1、支持下標(biāo)的隨機訪問；
- 2、尾插尾刪效率高（當(dāng)然擴容的那一次尾插會較慢）；
- 3、CPU高速緩存命中高（數(shù)據(jù)從緩存加載至CPU中，會加載連續(xù)的一段數(shù)據(jù)，vector因為結(jié)構(gòu)連續(xù)，高速緩存命中高）。
vector的缺點：
- 1、非尾插尾刪效率低；
- 2、擴容有消耗，并存在一定的空間浪費。
vector迭代器失效問題：
- insert/erase均失效。（如果string的insert和erase形參是迭代器，那么也會失效，但是大部分接口是下標(biāo)傳參，不考慮失效問題，只有幾個接口是迭代器傳參，需要注意迭代器失效問題）
2、list
list的優(yōu)點：
- 1、按需申請釋放，無需擴容；
- 2、任意位置插入刪除時間O(1)；（這里說的是插入刪除，不要加上查找的時間）
list的缺點：
- 1、不支持下標(biāo)的隨機訪問；
- 2、CPU高速緩存命中率低；
- 3、每一個節(jié)點除了存儲數(shù)據(jù)外，還需要額外存儲兩個指針。
| vector | list | |
|---|---|---|
| 底 層 結(jié) 構(gòu) | 動態(tài)順序表，一段連續(xù)空間 | 帶頭結(jié)點的雙向循環(huán)鏈表 |
| 隨 機 訪 問 | 支持隨機訪問，訪問某個元素效率O(1) | 不支持隨機訪問，訪問某個元素效率O(N) |
| 插 入 和 刪 除 | 任意位置插入和刪除效率低，需要搬移元素，時間復(fù)雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導(dǎo)致效率更低 | 任意位置插入和刪除效率高，不需要搬移元素，時間復(fù)雜度為O(1) |
| 空 間 利 用 率 | 底層為連續(xù)空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高 | 底層節(jié)點動態(tài)開辟，小節(jié)點容易造成內(nèi)存碎片，空間利用率低，緩存利用率低 |
| 迭 代 器 | 原生態(tài)指針 | 對原生態(tài)指針(節(jié)點指針)進行封裝 |
| 迭 代 器 失 效 | 在插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導(dǎo)致重新擴容，致使原來迭代器失效，刪除時，當(dāng)前迭代器需要重新賦值否則會失效 | 插入元素不會導(dǎo)致迭代器失效，刪除元素時，只會導(dǎo)致當(dāng)前迭代器失效，其他迭代器不受影響 |
| 使 用 場 景 | 需要高效存儲，支持隨機訪問，不關(guān)心插入刪除效率 | 大量插入和刪除操作，不關(guān)心隨機訪問 |
六、模擬實現(xiàn)list整體代碼
namespace fx
{
// List的節(jié)點類
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é)點
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é)點，返回該節(jié)點的下一個位置
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é)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)電話簿項目，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
C++標(biāo)準(zhǔn)庫中的<iostream>頭文件提供了標(biāo)準(zhǔn)輸入輸出功能,本文就來介紹最常用的接口分類及使用,具有一定的參考價值,感興趣可以了解一下2025-10-10
VS2019開發(fā)簡單的C/C++動態(tài)鏈接庫并進行調(diào)用的實現(xiàn)
這篇文章主要介紹了VS2019開發(fā)簡單的C/C++動態(tài)鏈接庫并進行調(diào)用的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
本文主要介紹了QT應(yīng)用程序cout輸出中文亂碼解決方法,文中通過圖文的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-01-01
這篇文章主要為大家詳細介紹了QT實現(xiàn)多文件拖拽獲取路徑的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
C++?關(guān)聯(lián)式容器map?與?set?的原理與實踐操作
本文將詳細介紹關(guān)聯(lián)式容器中最常用的map和set,包括它們的底層實現(xiàn)、核心特性、使用方法及實際應(yīng)用,本文結(jié)合實例代碼給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2025-12-12
VC外部符號錯誤_main,_WinMain@16,__beginthreadex解決方法
這篇文章主要介紹了VC外部符號錯誤_main,_WinMain@16,__beginthreadex解決方法,實例分析了比較典型的錯誤及對應(yīng)的解決方法,需要的朋友可以參考下2015-05-05
C++基于CreateToolhelp32Snapshot獲取系統(tǒng)進程實例
這篇文章主要介紹了C++基于CreateToolhelp32Snapshot獲取系統(tǒng)進程實例,是Windows應(yīng)用程序設(shè)計中非常實用的技巧,需要的朋友可以參考下2014-10-10
在任何程序的開發(fā)中，對于文件的操作都是繞不開的一個知識點，因為總是要用到存儲讀取的功能，今天我們來詳細了解C語言中是怎么操作文件的2021-11-11
快速了解C語言靜態(tài)關(guān)鍵字static的作用
這篇文章主要介紹了C語言中靜態(tài)關(guān)鍵字static的作用，對大家學(xué)習(xí)C語言非常有幫助，有需求的小伙伴可以參考下2020-05-05