C++中的list與forward_list介紹與使用
更新時(shí)間：2025年08月12日 10:40:32 作者：linux kernel
本文大家介紹C++中l(wèi)ist和forward_list的底層結(jié)構(gòu)（雙向/單向鏈表）、迭代器失效機(jī)制及與vector的對(duì)比,重點(diǎn)分析其插入刪除效率、空間利用率和適用場(chǎng)景,感興趣的朋友跟隨小編一起看看吧
1、list的介紹及使用
template < class T, class Alloc = allocator<T> > class list;
list的底層是帶頭雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向其前一個(gè)元素和后一個(gè)元素。list與forward_list非常相似，最主要的不同在于forward_list是無(wú)頭單向鏈表。
與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問(wèn)，比如：要訪問(wèn)list的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間開(kāi)銷；此外list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類型較小元素的大list來(lái)說(shuō)這可能是一個(gè)重要的因素）。
1.1、構(gòu)造及賦值重載
explicit list (const allocator_type& alloc = allocator_type()); // 默認(rèn)構(gòu)造 explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()); // 構(gòu)造n個(gè)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; // 元素個(gè)數(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、訪問(wèn)
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()); // 改變?cè)氐膫€(gè)數(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(); // 排序，默認(rèn)是升序 template <class Compare> void sort (Compare comp); // 關(guān)于仿函數(shù)，后面再說(shuō) 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、迭代器失效
前面說(shuō)過(guò)，迭代器失效即迭代器所指向的節(jié)點(diǎn)的無(wú)效。因?yàn)閘ist的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會(huì)導(dǎo)致list的迭代器失效的，只有在刪除時(shí)才會(huì)失效，并且失效的只是指向被刪除節(jié)點(diǎn)的迭代器，其他迭代器不會(huì)受到影響。例如：
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é)點(diǎn)已被刪除，因此it無(wú)效，在下一次使用it時(shí)，必須先給其賦值
lt.erase(it);
++it;
}
return 0;
}當(dāng)運(yùn)行到++it時(shí)就會(huì)報(bào)錯(cuò)。 改為如下即可：
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的模擬實(shí)現(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ù)都沒(méi)有寫，默認(rèn)的就夠用的了。
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)是無(wú)頭單向鏈表。
4.1、構(gòu)造及賦值重載
//默認(rèn)構(gòu)造
explicit forward_list (const allocator_type& alloc = allocator_type());
//構(gòu)造n個(gè)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; // 返回容器第一個(gè)元素之前的位置 const_iterator before_begin() const noexcept; iterator begin() noexcept; // 返回第一個(gè)元素的位置 const_iterator begin() const noexcept; iterator end() noexcept; // 返回最后一個(gè)元素之后的位置 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、訪問(wèn)
reference front(); // 返回第一個(gè)元素 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); // 增大元素個(gè)數(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(); // 排序，默認(rèn)為升序 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)于反向迭代器，會(huì)在模板進(jìn)階部分進(jìn)行模擬實(shí)現(xiàn)。
5.2、按性質(zhì)分類
迭代器按性質(zhì)（由容器的底層實(shí)現(xiàn)決定的）分類可以分為單向迭代器、雙向迭代器以及隨機(jī)迭代器。
單向迭代器：只支持++，不支持--，例如：forward_list（單鏈表）。
雙向迭代器：支持++，也支持--，例如：list（雙向鏈表）
隨機(jī)迭代器：支持++，也支持--，還支持+以及-，例如：vector（順序表）、string（順序表）以及deque（后面講）。
例如：算法庫(kù)中有一個(gè)sort模板函數(shù)，用來(lái)進(jìn)行排序
template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
但是該模板函數(shù)不能用來(lái)對(duì)list以及forward_list進(jìn)行排序，因?yàn)樵撃０搴瘮?shù)要求的是傳隨機(jī)迭代器，這也就是為什么，明明算法庫(kù)中有sort模板函數(shù)，但是forward_list以及l(fā)ist中也實(shí)現(xiàn)了sort函數(shù)的原因。
6、list與vector的對(duì)比
| vector | list | |
| 底層結(jié)構(gòu) | 動(dòng)態(tài)順序表，一段連續(xù)空間 | 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 |
| 隨機(jī)訪問(wèn) | 支持隨機(jī)訪問(wèn)，訪問(wèn)某個(gè)元素效率O(1) | 不支持隨機(jī)訪問(wèn)，訪問(wèn)某個(gè)元素效率為O(N) |
| 插入和刪除 | 任意位置插入和刪除效率低，需要搬移元素，時(shí)間復(fù)雜度為O(N)，插入時(shí)有可能需要增容，增容會(huì)開(kāi)辟新空間、拷貝元素以及釋放舊空間，導(dǎo)致效率更低 | 任意位置插入和刪除效率高，不需要搬移元素，時(shí)間復(fù)雜度為 O(1) |
| 空間利用率 | 底層為連續(xù)空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高。 | 底層節(jié)點(diǎn)動(dòng)態(tài)開(kāi)辟，節(jié)點(diǎn)容易造成內(nèi)存碎片，空間利用率低， 緩存利用率低。 |
| 迭代器 | 原生態(tài)指針 | 對(duì)原生態(tài)指針進(jìn)行封裝 |
| 迭代器失效 | 在插入元素后，要給迭代器重新賦值，因?yàn)椴迦朐赜锌赡軙?huì)導(dǎo)致重新擴(kuò)容，致使原來(lái)迭代器失效。刪除后，迭代器需要重新賦值否則會(huì)失效。 | 插入元素不會(huì)導(dǎo)致迭代器失效， 刪除元素時(shí)，只會(huì)導(dǎo)致當(dāng)前迭代器失效，其他迭代器不受影響。 |
| 使用場(chǎng)景 | 需要高效存儲(chǔ)，隨機(jī)訪問(wèn)，不關(guān)心插入刪除效率。 | 大量插入和刪除操作，不關(guān)心隨機(jī)訪問(wèn)。 |
到此這篇關(guān)于C++中的list與forward_list介紹與使用的文章就介紹到這了,更多相關(guān)C++ list與forward_list內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
以下是對(duì)C++中的對(duì)象指針進(jìn)行了詳細(xì)的總結(jié)介紹，需要的朋友可以過(guò)來(lái)參考下，希望對(duì)大家有所幫助2013-10-10
這篇文章主要為大家介紹了C語(yǔ)言中Static關(guān)鍵字，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01
C語(yǔ)言中的函數(shù)指針基礎(chǔ)學(xué)習(xí)教程
這篇文章主要介紹了C語(yǔ)言中的函數(shù)指針基礎(chǔ)學(xué)習(xí)教程,包括函數(shù)指針作為參數(shù)來(lái)傳遞等重要知識(shí),需要的朋友可以參考下2016-04-04
Python 提供了 C++ 庫(kù)，使得開(kāi)發(fā)者能很方便地從 C++ 程序中調(diào)用 Python 模塊。接下來(lái)通過(guò)本文給大家介紹 C++ 調(diào)用 Python 模塊的相關(guān)知識(shí)，需要的朋友參考下吧2016-03-03
這篇文章主要介紹了VC程序設(shè)計(jì)小技巧20例,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了C++常用字符串分割方法實(shí)例匯總,包括了strtok函數(shù)、STL、Boost等常用的各類字符串分割方法,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
盡管函數(shù)式宏定義和普通函數(shù)相比有很多缺點(diǎn)，但只要小心使用還是會(huì)顯著提高代碼的執(zhí)行效率，畢竟省去了分配和釋放棧幀、傳參、傳返回值等一系列工作，因此那些簡(jiǎn)短并且被頻繁調(diào)用的函數(shù)經(jīng)常用函數(shù)式宏定義來(lái)代替實(shí)現(xiàn)2013-10-10
本文主要介紹了C++從文件中提取英文單詞的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中指針的加減運(yùn)算的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C語(yǔ)言具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序
這篇文章主要介紹了C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序,同時(shí)也包括編寫類的示例展示C++面向?qū)ο蟮奶匦?需要的朋友可以參考下2015-09-09