C++之list的使用與模擬實現(xiàn)過程
更新時間：2025年10月09日 10:47:09 作者：小蘇兮
本文簡述C++?list容器,其基于雙向循環(huán)鏈表,支持高效插入刪除,迭代器失效僅影響被刪除節(jié)點,模擬實現(xiàn)時通過封裝節(jié)點和迭代器,對比list與vector的特性差異,如隨機訪問、空間利用率及適用場景
一、list的介紹與使用
我們對于list的學習和前面string與vector類似，先看官方文檔：【list的文檔介紹】：
可見，list也是一個類模板。
list的底層其實是一個帶有頭結(jié)點的雙向循環(huán)鏈表：
在有了前面string與vector的基礎(chǔ)，我們這里對于list的學習就直接采用文檔來學習，不在一一列舉了。
示例：
#include<list>
#include<vector>
using namespace std;
int main()
{
list<int> l1; //不初始化
list<int> l2(5, 10);//用5個10來初始化
list<int> l3(l2); //拷貝構(gòu)造
vector<int> v = { 1,2,3,4,5,6 };
list<int> l4(v.begin(), v.end());//用迭代器區(qū)間來初始化
return 0;
}
調(diào)試：
用法與前面的容器基本相同，我們就不過多闡述了，這里主要對迭代器的分類說明一下，拓展：
迭代器分類
在list這里，我們就要對迭代器的分類有一定了解了，
- 按功能分類：
這個我們都好理解，但是，今天，我們按性質(zhì)分。
- 按性質(zhì)分類：
可見，list為雙向迭代器，vector為隨機迭代器，那有什么區(qū)別呢，為什么會有這樣的分類？
迭代器按性質(zhì)分有以下：
幾者的關(guān)系為繼承。先行了解就行。
它們之間的區(qū)別為：
有區(qū)別的原因就在于其底層的實現(xiàn)不同，還會導致它們適用的算法不同：
在 C++ 標準庫的容器中，沒有"純 Input 迭代器"。至少都是 Forward 迭代器，后續(xù)隨著對容器的學習會了解。
與vector相同， list的迭代器失效問題我們需要注意。
list的迭代器失效
前面說過，我們可將迭代器暫時理解成類似于指針，迭代器失效即迭代器所指向的節(jié)點的無效，即該節(jié)點被刪除了。
因為list的底層結(jié)構(gòu)為帶頭結(jié)點的雙向循環(huán)鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節(jié)點的迭代器，其他迭代器不會受到影響。
void Test1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點已被刪除，因此it無效，在下一次使用it時，必須先給其賦值
l.erase(it);
++it;
}
}
// 改正
void Test()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}
對于list的使用，我們就到此為止，因為與string與vector相似，所以我們就簡單的演示就沒有做。
我們重點來進行l(wèi)ist的模擬實現(xiàn)。
二、list的模擬實現(xiàn)
list的底層：
首先我們先來對結(jié)點進行封裝：
//節(jié)點
template<class T>
struct list_node
{
T _data;
list_node* _next;
list_node* _prev;
list_node(T data = T())
{
_data = data;
_next = _prev = this;
}
};
這里我們要說一個點：
答案是：int() = 0
解釋：對于用戶自定義的類，如果定義了默認構(gòu)造函數(shù)，調(diào)用 MyClass() 會初始化對象。對于基本類型，int() 可以看作是這種模式的一種延伸，將其初始化為一個合理的“空”狀態(tài)。這樣就會使得自定義類型與內(nèi)置類型共用同一個模版了。
由于list的迭代器不再是原生指針，所以我們對list的迭代器進行封裝，那么對于iterator與const_iterator我們豈不是要封裝兩次嗎，但是，我們可以這樣做，設置三個模板參數(shù)（結(jié)合最下面list的主框架實現(xiàn)來看）
//迭代器
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node = nullptr)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
//前置
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置
Self& operator++(int)
{
_node = _node->_next;
return _node->prev;
}
Self& operator--(int)
{
_node = _node->_prev;
return _node->_next;
}
bool operator!=(const Self& it)const
{
return _node != it._node;
}
bool operator==(const Self& it)const
{
return _node == it._node;
}
};
list主框架
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
// List的構(gòu)造
void init_head()
{
_head = new Node;
}
list()
{
init_head();
}
list(int n, const T& value = T())
{
init_head();
while (n--)
{
push_back(value);
}
}
template <class Iterator>
list(Iterator first, Iterator last)
{
init_head();
while (first != last)
{
push_back(*first);
++first;
}
}
list(list<T>& ls)
:_head(new Node)
{
for (auto i : ls)
{
push_back(i);
}
}
//賦值重載
/*list<T>& operator=(list<T>& ls)
{
for (iterator it = begin();it!=end();)
{
it = erase(it);
}
for (auto i : ls)
{
push_back(i);
}
return *this;
}*/
list<T>& operator=(list<T> ls)
{
swap(ls);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
// List Iterator
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
//return iterator(_head);
return const_iterator(_head);
}
// List Capacity
size_t size()const
{
size_t cnt = 0;
for (auto i : *this)
{
++cnt;
}
return cnt;
}
bool empty()const
{
return _head->_next == _head;
}
// List Access
T& front()
{
return _head->_next->_data;
}
const T& front()const
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& back()const
{
return _head->_prev->_data;
}
// List Modify
void push_back(T data)
{
/*Node* cur = new Node(data);
cur->_next = _head;
cur->_prev = _head->_prev;
_head->_prev = cur;
cur->_prev->_next = cur;*/
insert(end(), data);
}
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(val);
newnode->_next = pos._node;
newnode->_prev = pos._node->_prev;
newnode->_next->_prev = newnode;
newnode->_prev->_next = newnode;
return newnode;
}
// 刪除pos位置的節(jié)點，返回該節(jié)點的下一個位置
iterator erase(iterator pos)
{
//assert(end());
pos._node->_prev->_next = pos._node->_next;
pos._node->_next->_prev = pos._node->_prev;
iterator it = pos._node->_next;
delete pos._node;
return it;
}
void clear()
{
for (iterator it = begin(); it != end();)
{
it = erase(it);
}
}
void swap(list<T>& ls)
{
std::swap(this->_head, ls._head);
}
private:
Node* _head;
};
iterator解釋：
在三個模版參數(shù)的作用下，就會使得iterator與const_iterator共用同一個模版的情況下實現(xiàn)。當然，也可以寫成兩個模版，效果是一樣的。
還需注意：
- 模板只有在被使用時才會實例化。
- 單純的typedef聲明只是創(chuàng)建了一個類型別名，并不會觸發(fā)實例化。
我們這里只是實現(xiàn)正向迭代器，反向迭代器簡單說明一下：
反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的實現(xiàn)可以借助正向迭代器，即：反向迭代器內(nèi)部可以包含一個正向迭代器，對正向迭代器的接口進行包裝即可。
三、list與vector的比較
vector 與 list 都是 STL 中非常重要的序列式容器，由于兩個容器的底層結(jié)構(gòu)不同，導致其特性以及應用場景不同，其主要不同如下：
| 特性 | vector | list |
|---|---|---|
| 底層結(jié)構(gòu) | 動態(tài)順序表，一段連續(xù)空間 | 帶頭結(jié)點的雙向循環(huán)鏈表 |
| 隨機訪問 | 支持隨機訪問，訪問某個元素效率 O(1) | 不支持隨機訪問，訪問某個元素效率 O(N) |
| 插入和刪除 | 任意位置插入和刪除效率低，需要搬移元素，時間復雜度為 O(N)，插入時有可能需要增容，導致效率更低 | 任意位置插入和刪除效率高，不需要搬移元素，時間復雜度為 O(1) |
| 空間利用率 | 底層為連續(xù)空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高 | 底層節(jié)點動態(tài)開辟，小節(jié)點容易造成內(nèi)存碎片，空間利用率低，緩存利用率低 |
| 迭代器 | 原生態(tài)指針 | 對原生態(tài)指針(節(jié)點指針)進行封裝 |
| 迭代器失效 | 插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導致重新擴容，致使原來迭代器失效；刪除操作會使指向被刪除元素及之后所有元素的迭代器失效。需要重新賦值 | 插入元素不會導致迭代器失效，刪除元素時，只會導致當前迭代器失效，其他迭代器不受影響 |
| 使用場景 | 需要高效存儲，支持隨機訪問，不關(guān)心插入刪除效率 | 大量插入和刪除操作，不關(guān)心隨機訪問 |
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C++11中的stoi & stod用法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要為大家詳細介紹了Opencv LBPH人臉識別算法的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
關(guān)于C++對象繼承中的內(nèi)存布局示例詳解
這篇文章主要給大家介紹了關(guān)于C++對象繼承中內(nèi)存布局的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面跟著小編來一起學習學習吧。2017-08-08
本文主要介紹了如何使用OpenCV C++對視頻中的人流量進行統(tǒng)計。文中的示例代碼講解詳細，對我們學習OpenCV有一定的幫助，需要的可以了解一下2022-01-01
遞推算法需要用戶知道答案和問題之間的邏輯關(guān)系。在許多數(shù)學問題中，都有明確的計算公式可以遵循，因此可以采用遞推算法來實現(xiàn)2013-10-10
這篇文章主要為大家詳細介紹了C++核心編程之內(nèi)存分區(qū)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
在程序設計中,時間管理是一個核心概念,它不僅關(guān)系到程序的效率和性能,而且直接影響用戶體驗,C++作為一門高效的編程語言,提供了std::chrono庫,用于精確地處理和計算時間,下面就跟隨小編一起學習一下std::chrono庫的使用吧2023-12-12
這篇文章主要為大家詳細介紹了C++中類的轉(zhuǎn)換函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
在圖像處理中,我們經(jīng)常根據(jù)需要截取圖像中某一區(qū)域做處理,下面這篇文章主要給大家介紹了關(guān)于C++?OpenCV裁剪圖片時發(fā)生報錯的解決方式,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2022-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)小學生考試系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03