C++中的list與forward_list介紹與使用
更新時間：2025年08月12日 10:40:32 作者：linux kernel
本文大家介紹C++中l(wèi)ist和forward_list的底層結(jié)構(gòu)（雙向/單向鏈表）、迭代器失效機制及與vector的對比,重點分析其插入刪除效率、空間利用率和適用場景,感興趣的朋友跟隨小編一起看看吧
1、list的介紹及使用
template < class T, class Alloc = allocator<T> > class list;
list的底層是帶頭雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。list與forward_list非常相似，最主要的不同在于forward_list是無頭單向鏈表。
與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；此外list還需要一些額外的空間，以保存每個節(jié)點的相關(guān)聯(lián)信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素）。
1.1、構(gòu)造及賦值重載
explicit list (const allocator_type& alloc = allocator_type()); // 默認構(gòu)造 explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()); // 構(gòu)造n個val值 template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()); // 迭代器區(qū)間構(gòu)造 list (const list& x); // 拷貝構(gòu)造 list& operator= (const list& x); // 賦值重載
1.2、迭代器
iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; reverse_iterator rbegin(); reverse_iterator rend(); const_reverse_iterator rbegin() const; const_reverse_iterator rend() const;
例如：
int main()
{
list<int> lt1;
list<int> lt2(10, 2);
list<int> lt3(lt2.begin(), lt2.end());
list<int> lt4(lt3);
lt1 = lt4;
list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end())
{
cout << *it1 << ' ';
++it1;
}
cout << endl;
for (auto e : lt4)
{
cout << e << ' ';
}
cout << endl;
return 0;
}1.3、空間
bool empty() const; // 判斷是否為空 size_type size() const; // 元素個數(shù)
例如：
int main()
{
list<int> lt1;
list<int> lt2(10, 2);
cout << lt1.empty() << endl;
cout << lt2.empty() << endl;
cout << lt1.size() << endl;
cout << lt2.size() << endl;
return 0;
}1.4、訪問
reference front(); // 起始元素 const_reference front() const; reference back(); // 末尾元素 const_reference back() const;
例如：
int main()
{
list<int> lt1(10, 2);
lt1.front()++;
lt1.back()--;
cout << lt1.front() << endl;
cout << lt1.back() << endl;
return 0;
}1.5、修改
void push_front (const value_type& val); // 頭插 void pop_front(); // 頭刪 void push_back (const value_type& val); // 尾插 void pop_back(); // 尾刪 iterator insert (iterator position, const value_type& val); // 插入 iterator erase (iterator position); // 刪除 void swap (list& x); // 交換 void resize (size_type n, value_type val = value_type()); // 改變元素的個數(shù) void clear(); // 清空
例如：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(5);
lt.push_front(6);
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
lt.resize(10, 9);
lt.insert(lt.begin(), 7);
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
list<int> lt2(lt);
lt.clear();
for (auto e : lt2)
{
cout << e << ' ';
}
cout << endl;
lt.swap(lt2);
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
lt.pop_front();
lt.pop_back();
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
return 0;
}1.6、操作
void sort(); // 排序，默認是升序 template <class Compare> void sort (Compare comp); // 關(guān)于仿函數(shù)，后面再說 void reverse(); // 逆置
例如：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(5);
lt.push_front(6);
lt.reverse();
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << ' ';
++it;
}
cout << endl;
list<int> lt2(lt);
lt.sort();
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
greater<int> gt;
lt2.sort(gt);
for (auto e : lt2)
{
cout << e << ' ';
}
cout << endl;
return 0;
}2、迭代器失效
前面說過，迭代器失效即迭代器所指向的節(jié)點的無效。因為list的底層結(jié)構(gòu)為帶頭結(jié)點的雙向循環(huán)鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節(jié)點的迭代器，其他迭代器不會受到影響。例如：
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
auto it = lt.begin();
while (it != lt.end())
{
// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點已被刪除，因此it無效，在下一次使用it時，必須先給其賦值
lt.erase(it);
++it;
}
return 0;
}當運行到++it時就會報錯。 改為如下即可：
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
auto it = lt.begin();
while (it != lt.end())
{
lt.erase(it++);
//或者也可以寫成：
//it = lt.erase(it);
}
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
return 0;
}3、list的模擬實現(xiàn)
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};
// ///////////////////////////////////////////////////////////
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T,Ref,Ptr> self;//這里的拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)都沒有寫，默認的就夠用的了。
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
// /////////////////////////////////////////
template<class T>
class List
{
public:
typedef list_node<T> Node;
// 正向迭代器
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T,const T&,const T*> const_iterator;
// //////////////////////////////////////////////////////
iterator begin()
{
return _head->_next;//這里也可以寫為:iterator(_head->_next);
}
iterator end()
{
return _head;//這里也可以寫為:iterator(_head);
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
// ///////////////////////////////////////////////////////////
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
List()
{
empty_init();
}
List(const List<T>& lt)
{
empty_init();
const_iterator it = lt.begin();
while (it != lt.end())
{
push_back(*it);
++it;
}
//像下面這樣寫也是可以的
/*for (auto e : lt)
{
push_back(e);
}*/
}
/*List<T>& operator=(const List<T>& lt) // 傳統(tǒng)寫法
{
if (this != <)
{
clear();
for (auto e : lt)
{
push_back(e);
}
}
return *this;
}*/
void swap(List<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
List<T>& operator=(List<T> lt) // 現(xiàn)代寫法
{
swap(lt);
return *this;
}
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
--_size;
return iterator(next);
}
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* end = _head->_prev;
end->_next = newnode;
newnode->_prev = end;
newnode->_next = _head;
_head->_prev = newnode;
_size++;
}
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;
};4、forward_list介紹與使用
template < class T, class Alloc = allocator<T> > class forward_list;
forward_list的底層結(jié)構(gòu)是無頭單向鏈表。
4.1、構(gòu)造及賦值重載
//默認構(gòu)造
explicit forward_list (const allocator_type& alloc = allocator_type());
//構(gòu)造n個val
explicit forward_list (size_type n, const value_type& val,
const allocator_type& alloc = allocator_type());
//用迭代區(qū)間構(gòu)造
template <class InputIterator>
forward_list (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
//拷貝構(gòu)造
forward_list (const forward_list& fwdlst);
//賦值重載
forward_list& operator= (const forward_list& fwdlst);4.2、迭代器
iterator before_begin() noexcept; // 返回容器第一個元素之前的位置 const_iterator before_begin() const noexcept; iterator begin() noexcept; // 返回第一個元素的位置 const_iterator begin() const noexcept; iterator end() noexcept; // 返回最后一個元素之后的位置 const_iterator end() const noexcept;
例如：
int main()
{
forward_list<int> f1;
forward_list<int> f2(5, 3);
forward_list<int> f3(f2.begin(), f2.end());
forward_list<int> f4(f3);
f1 = f4;
forward_list<int>::iterator it1 = f2.begin();
while (it1 != f2.end())
{
cout << *it1 << ' ';
++it1;
}
cout << endl;
for (auto& e : f3)
{
cout << ++e << ' ';
}
cout << endl;
return 0;
}4.3、容量
bool empty() const noexcept; // 判斷是否為空
4.4、訪問
reference front(); // 返回第一個元素 const_reference front() const;
4.5、修改
void push_front (const value_type& val); //頭插 void pop_front(); // 頭刪 iterator insert_after ( const_iterator position, const value_type& val ); // 之后插入 iterator erase_after (const_iterator position); // 之后刪除 void swap (forward_list& fwdlst); // 交換 void resize (size_type n); // 增大元素個數(shù) void resize (size_type n, const value_type& val); void clear() noexcept; // 清空
例如：
int main()
{
forward_list<int> f1;
f1.push_front(1);
f1.push_front(2);
f1.push_front(3);
f1.push_front(4);
f1.push_front(5);
cout << f1.empty() << endl;
cout << f1.front() << endl;
f1.insert_after(f1.before_begin(), 6);
forward_list<int>::iterator it1 = f1.begin();
while (it1 != f1.end())
{
cout << *it1 << ' ';
++it1;
}
cout << endl;
forward_list<int> f2;
f2.resize(10, 5);
f1.swap(f2);
f2.clear();
for (auto e : f1)
{
cout << e << ' ';
}
cout << endl;
return 0;
}4.6、操作
void sort(); // 排序，默認為升序 template <class Compare> void sort (Compare comp); void reverse() noexcept; // 逆置
例如：
int main()
{
forward_list<int> f1;
f1.push_front(5);
f1.push_front(4);
f1.push_front(3);
f1.push_front(5);
f1.push_front(2);
f1.sort();
for (auto e : f1)
{
cout << e << ' ';
}
cout << endl;
f1.reverse();
for (auto e : f1)
{
cout << e << ' ';
}
cout << endl;
return 0;
}5、迭代器的分類
5.1、按功能分類
迭代器按功能分類可以分為正向迭代器和反向迭代器。關(guān)于反向迭代器，會在模板進階部分進行模擬實現(xiàn)。
5.2、按性質(zhì)分類
迭代器按性質(zhì)（由容器的底層實現(xiàn)決定的）分類可以分為單向迭代器、雙向迭代器以及隨機迭代器。
單向迭代器：只支持++，不支持--，例如：forward_list（單鏈表）。
雙向迭代器：支持++，也支持--，例如：list（雙向鏈表）
隨機迭代器：支持++，也支持--，還支持+以及-，例如：vector（順序表）、string（順序表）以及deque（后面講）。
例如：算法庫中有一個sort模板函數(shù)，用來進行排序
template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
但是該模板函數(shù)不能用來對list以及forward_list進行排序，因為該模板函數(shù)要求的是傳隨機迭代器，這也就是為什么，明明算法庫中有sort模板函數(shù)，但是forward_list以及l(fā)ist中也實現(xiàn)了sort函數(shù)的原因。
6、list與vector的對比
| 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)指針進行封裝 |
| 迭代器失效 | 在插入元素后，要給迭代器重新賦值，因為插入元素有可能會導致重新擴容，致使原來迭代器失效。刪除后，迭代器需要重新賦值否則會失效。 | 插入元素不會導致迭代器失效， 刪除元素時，只會導致當前迭代器失效，其他迭代器不受影響。 |
| 使用場景 | 需要高效存儲，隨機訪問，不關(guān)心插入刪除效率。 | 大量插入和刪除操作，不關(guān)心隨機訪問。 |
到此這篇關(guān)于C++中的list與forward_list介紹與使用的文章就介紹到這了,更多相關(guān)C++ list與forward_list內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C++中sort函數(shù)的基礎(chǔ)入門使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C++具有一定的參考學習價值，需要的朋友們下面來一起看看吧2021-08-08
C++通過 Py_Initialize實現(xiàn)對Python的嵌入調(diào)用
在現(xiàn)代軟件開發(fā)中,性能（C++）與靈活性（Python）的結(jié)合是許多大型項目的首選方案,本文將帶你走進 Python C API 的世界,重點介紹如何通過 Py_Initialize 實現(xiàn) C++ 對 Python 的嵌入調(diào)用,希望對大家有所幫助2025-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單彈跳小球，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細介紹了C語言簡單實現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了c++中的std::move函數(shù),在探討c++11中的Move函數(shù)前，先介紹兩個概念（左值和右值），對c++?std::move函數(shù)相關(guān)知識感興趣的朋友一起看看吧2022-07-07
這篇文章主要為大家介紹了C語言中雙指針算法的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
C++數(shù)據(jù)結(jié)構(gòu)二叉搜索樹的實現(xiàn)應用與分析
從這篇博客開始，我就要和大家介紹有關(guān)二叉搜索樹的知識，它還衍生出了兩棵樹——AVL樹和紅黑樹，在后面兩篇博客我都會介紹。今天先從二叉搜索樹開始引入2022-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)隨機發(fā)撲克牌，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
此處對于全局與局部做一些簡要的介紹，包括全局變量與局部變量，靜態(tài)全局變量與靜態(tài)局部變量，全局函數(shù)與靜態(tài)函數(shù)，作者實屬初學，文中若有理解不當之處，還請朋友們不吝指正2021-11-11
這篇文章主要介紹了Linux編程實現(xiàn)制作文件的ed2k鏈的相關(guān)資料,需要的朋友可以參考下2015-03-03