C++ list容器基本邏輯結(jié)構(gòu)和實(shí)現(xiàn)原理
C++初級(jí)語法
list 類模板
STL容器中以 帶頭雙向循環(huán)鏈表 為核心的類模板- 類模板：
template<class T,class Alloc=allocator<T>> class list;- 這里
class T，表示用戶可以用 任意類型 去通過類模板形成 想要的list<[具體類型]>類代碼 - 這里
class Alloc=allocator<T>，表示用戶可以根據(jù) 任意類型 去通過類模板 形成想要的 空間配置器，這里的空間配置器是提高申請(qǐng)類對(duì)象所需內(nèi)存效率的->用戶無需考慮該知識(shí)點(diǎn)
- 這里
list<[具體類型]>對(duì)象 本質(zhì)是以帶頭雙向循環(huán)鏈表為核心數(shù)據(jù)結(jié)構(gòu) 的類對(duì)象，對(duì)應(yīng)list<[具體類型]>對(duì)象 對(duì)應(yīng)的頭節(jié)點(diǎn)無任何意義，用戶無法 刪除、修改和控制 頭節(jié)點(diǎn)- 因此為了了解
list對(duì)應(yīng)的核心數(shù)據(jù)結(jié)構(gòu)，我們需要了解list對(duì)象 和對(duì)應(yīng)的ListNode節(jié)點(diǎn)對(duì)象 進(jìn)行熟知此數(shù)據(jù)結(jié)構(gòu)
- 因此為了了解
- 類模板：
- 使用
list類模板 需包含<list>頭文件list是類模板名，list<[具體類型]>是具體類名
std::list<[具體類型]> [標(biāo)識(shí)符]，對(duì)應(yīng)標(biāo)識(shí)符下對(duì)象的底層邏輯
_head指向鏈表的ListNode頭節(jié)點(diǎn)，用戶通過list對(duì)象去控制整個(gè)鏈表的每個(gè)非頭節(jié)點(diǎn)的ListNode節(jié)點(diǎn)_size記錄當(dāng)前鏈表對(duì)象非頭節(jié)點(diǎn)的個(gè)數(shù)
std::ListNode<[具體類型]> [標(biāo)識(shí)符]，對(duì)應(yīng)標(biāo)識(shí)符下對(duì)象的底層邏輯，用戶所有核心操作和使用的都是ListNode節(jié)點(diǎn)對(duì)象 的地址來操控ListNode節(jié)點(diǎn)對(duì)象
本質(zhì)是list<[具體類型]>這個(gè)鏈表對(duì)象 的ListNode<[具體類型]>節(jié)點(diǎn)對(duì)象_next指向的節(jié)點(diǎn)為tail節(jié)點(diǎn)時(shí)，_next指向_head所指向的節(jié)點(diǎn)，不為tail節(jié)點(diǎn)時(shí)，則指向當(dāng)前節(jié)點(diǎn)的下一個(gè)ListNode節(jié)點(diǎn)
//模擬list<int>邏輯圖
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
//模擬list<string>邏輯圖
__________________________
|list<int> |
|ListNode<string>* _head; |
|__________________|_______|
|
_________________________________________V____________________________
|ListNode<string>illicit string() |
| _________________ | ____
|ListNode<string>* _next; ListNode<string>* _prev;|string | | |'\0'|
| | | |char* _str;------|-|--->|____|
| | | |size_t _size; | | :0
| | | |size_t _capacity;| | :1
| | | |_________________| |
|_____________________|__________________________|_____________________|
| ^ ^ |
______________________V_|______________________|_V_____________________
|ListNode<string> | | _________________ | _________
|ListNode<string>* _next; ListNode<string>* _prev;|string | | |'\0'| |
| |char* _str;------|-|--->|____|____|
| |size_t _size; | | :0
| |size_t _capacity;| | :1
| |_________________| |
|______________________________________________________________________|list<[具體類型]>對(duì)應(yīng)的迭代器對(duì)象不會(huì)因?yàn)閿U(kuò)容而出現(xiàn)迭代器失效問題
list<[具體類型]>對(duì)應(yīng)類模板 提供的構(gòu)造
explict list(const allocator_type& alloc=allocator_type());，list<[具體類型]>的默認(rèn)構(gòu)造，底層會(huì)開辟ListNode節(jié)點(diǎn)對(duì)象空間 作為當(dāng)前list<[具體類型]>對(duì)象的頭節(jié)點(diǎn)
ListNode()
std::list<int> l;
_____________________ ：l
|list<int> |
|ListNode<int>* _head;|
|________________|____|
| ____
| | |
_________________________________V______|____V________
|ListNode<int>illicit | int()|
|ListNode<int>* _next; ListNode<int>* _prev; int data;|
|________________|_____________________________________|
| ^
|____|
explict list(size_type n,const value_type& val=value_type(),const allocator_type& alloc=allocator_type())，通過n和val值去初始化當(dāng)前list<[具體類型]>對(duì)象
std::list<int> l(2,3);
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
list(InputIterator first,InputIterator last,const allocator_type& alloc=allocator_type())，通過指定迭代器區(qū)間的連續(xù)數(shù)據(jù)去初始化當(dāng)前鏈表對(duì)象(區(qū)間一般為鏈表對(duì)象的鏈表區(qū)間)
template<class InputIterator>。
list(const list& x)，深拷貝
list<[具體類型]>對(duì)應(yīng)類模板 的 迭代器相關(guān)函數(shù)
iterator begin();，返回值對(duì)象 為指向 當(dāng)前list對(duì)象對(duì)應(yīng)頭節(jié)點(diǎn) 的iterator類型 迭代器對(duì)象const_iterator cbegin() const;，返回值對(duì)象 為指向 當(dāng)前list對(duì)象對(duì)應(yīng)頭節(jié)點(diǎn) 的const_iterator類型 迭代器對(duì)象iterator end();，返回值對(duì)象 為指向 當(dāng)前list對(duì)象_head._next對(duì)應(yīng)的節(jié)點(diǎn) 的iterator類型 迭代器對(duì)象const_iterator cend() const;，返回值對(duì)象 為指向 當(dāng)前list對(duì)象對(duì)應(yīng)頭節(jié)點(diǎn) 的const_iterator類型 迭代器對(duì)象
list<[具體類型]>對(duì)應(yīng)類模板 的容量相關(guān)的成員函數(shù)
bool empty() const;，當(dāng)list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象中非頭節(jié)點(diǎn)個(gè)數(shù)為0則返回值為真，反之返回值為假.size_type size() const;，返回值為list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象中 非頭節(jié)點(diǎn) 個(gè)數(shù).
本質(zhì)就是返回對(duì)象為當(dāng)前鏈表對(duì)象._size
list<[具體類型]>對(duì)應(yīng)類模板提供的 節(jié)點(diǎn)數(shù)據(jù)操作 的成員函數(shù)
void assign (InputIterator first, InputIterator last);.
template <class InputIterator>，
void assign (size_type n, const value_type& val);，void insert (iterator position, const value_type& val);，在position._node和position._node._prev中間插入一個(gè)包含val值的ListNode<[指定類型]>的節(jié)點(diǎn)對(duì)象.void insert (iterator position, size_type n, const value_type& val);，在position._node和position._node._prev中間插入n個(gè)包含val值的ListNode<[指定類型]>的節(jié)點(diǎn)對(duì)象.void insert (iterator position, InputIterator first, InputIterator last);，，在position._node和position._node._prev中間插入迭代器區(qū)間內(nèi)所包含的所有ListNode<[指定類型]>節(jié)點(diǎn)對(duì)象.
template <class InputIterator>。
void push_back (const value_type& val);，在list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象.end()指向的節(jié)點(diǎn) 前插入一個(gè)指定val值的ListNode<[指定類型]>節(jié)點(diǎn)void push_front (const value_type& val);，在list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象.begin()指向的節(jié)點(diǎn) 前插入一個(gè)指定val值的ListNode<[指定類型]>節(jié)點(diǎn)void pop_front();，刪除list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象.begin()指向的節(jié)點(diǎn).void pop_back()，刪除list<[具體類型]>對(duì)應(yīng)當(dāng)前鏈表對(duì)象.end()指向的節(jié)點(diǎn) 前對(duì)應(yīng)的節(jié)點(diǎn).void resize (size_type n, value_type val = value_type());，調(diào)整_head對(duì)應(yīng)鏈表已用節(jié)點(diǎn)的個(gè)數(shù)，更新完后滿足_size=n.
當(dāng)_size<n可采用指定數(shù)據(jù)val來生成n-_size個(gè)節(jié)點(diǎn)
當(dāng)n<_size則直接刪除多余的_size-n個(gè)節(jié)點(diǎn)即可
iterator erase (iterator position);，新建局部對(duì)象next=position._next，然后刪除position._node指向的節(jié)點(diǎn)對(duì)象，返回值對(duì)象為next.iterator erase (iterator first, iterator last);，新建局部對(duì)象next=last._next，然后刪除迭代器區(qū)間所有的節(jié)點(diǎn)對(duì)象，返回值對(duì)象為next.void clear();，delete 釋放掉所有非頭節(jié)點(diǎn)空間.list<T>& operator=(list<T> lt)，賦值重載(深拷貝)
list<[具體類型]>對(duì)應(yīng)類模板提供的 鏈表節(jié)點(diǎn)操作 的成員函數(shù)
void splice (iterator position, list& x);，把 x 對(duì)象對(duì)應(yīng)的所有非頭節(jié)點(diǎn) 轉(zhuǎn)移到指定迭代器對(duì)應(yīng)空間 的位置之前，此時(shí) x 對(duì)象變成空鏈表.
注意x對(duì)象不可以是當(dāng)前鏈表對(duì)象
list<int> l1(2,3);
list<int> l2(1,5);
_____________________:l1 _____________________:l2
|list<int> | |list<int> |
|ListNode<int>* _head;| |ListNode<int>* _head;|
|size_t _size; | |:2 |size_t _size; | |:1
|________________|____| |________________|____|
_______________ | _________________ _______________ | _________________
| ___________V_________________________V__|_____________ | | ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | | | |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | | | ^ |
| _______________V________________________|_____________ | | _______________V________________________|_____________ |
| |ListNode<int> | 3 | | | |ListNode<int> | 5 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | |____________________| ^________________|
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
l1.splice(l1.end(),l2);
_____________________:l1 _____________________:l2
|list<int> | |list<int> |
|ListNode<int>* _head;| |ListNode<int>* _head;|
|size_t _size; |:3 |size_t _size; |:0
|________________|____| |________________|____|
_______________ | _________________ _______________ | _________________
| ___________V_________________________V__|_____________ | | ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | | | |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | |___________________| ^_________________|
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|_______________________|______________| |
| ________________V_______________________|______________ |
| |ListNode<int> | 5 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
void splice (iterator position, list& x, iterator i);，
注意x對(duì)象不可以是當(dāng)前鏈表對(duì)象
void splice (iterator position, list& x, iterator first, iterator last);，
注意x對(duì)象不可以是當(dāng)前鏈表對(duì)象
void remove (const value_type& val);，根據(jù)提供的值找到并刪除值.
list<int> l1;
l1.push_back(1);
l1.push_back(2);
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 1 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 2 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
l1.remove(2)
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 1 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
|____________________| ^________________|void remove_if (Predicate pred);.
template <class Predicate>，
void unique();，對(duì)應(yīng)對(duì)象對(duì)應(yīng)的鏈表必須有序才能執(zhí)行此去重.
list<int> l1(2,3);
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
l1.unique();
_____________________
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |：2
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
|____________________| ^________________|void unique (BinaryPredicate binary_pred);
template <class BinaryPredicate>。
void merge (list& x);，x鏈表對(duì)象和當(dāng)前鏈表對(duì)象的鏈表必須都是升序或者降序才可以被合并，合并后x對(duì)象的鏈表變?yōu)榭真湵?
注意x對(duì)象不可以是當(dāng)前鏈表對(duì)象
list<int> l1(2,3);
list<int> l2(1,5);
_____________________:l1 _____________________:l2
|list<int> | |list<int> |
|ListNode<int>* _head;| |ListNode<int>* _head;|
|size_t _size; | |:2 |size_t _size; | |:2
|________________|____| |________________|____|
_______________ | _________________ _______________ | _________________
| ___________V_________________________V__|_____________ | | ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | | | |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | | | ^ |
| _______________V________________________|_____________ | | _______________V________________________|_____________ |
| |ListNode<int> | 1 | | | |ListNode<int> | 2 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | | | ^ |
| ________________V_______________________|______________ | | ________________V_______________________|______________ |
| |ListNode<int> | 3 | | | |ListNode<int> | 4 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | | | |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| | | |________________|______________________________________| |
|____________________| ^________________| |____________________| ^________________|
l1.merge(l2);
_____________________:l1 _____________________:l2
|list<int> | |list<int> |
|ListNode<int>* _head;| |ListNode<int>* _head;|
|size_t _size; |:4 |size_t _size; | |:0
|________________|____| |________________|____|
_______________ | _________________ _______________ | _________________
| ___________V_________________________V__|_____________ | | ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | | | |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | | |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| | | |________________|_____________________________________| |
| | ^ | |___________________| ^_________________|
| _______________V________________________|_____________ |
| |ListNode<int> | 1 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 2 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 4 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
void merge (list& x, Compare comp);，將鏈表 x 中的所有節(jié)點(diǎn)合并到當(dāng)前鏈表中，合并后的鏈表保持升序排列，鏈表對(duì)象x變?yōu)榭真湵怼?/p>
template <class Compare>。
注意x對(duì)象不可以是當(dāng)前鏈表對(duì)象
void sort();，排序(默認(rèn)升序).
數(shù)據(jù)量大時(shí)，排序效率比較低
void sort (Compare comp);，按指定升降序?qū)Ξ?dāng)前鏈表對(duì)象的鏈表節(jié)點(diǎn)進(jìn)行排序
template <class Compare>，
底層為歸并排序，數(shù)據(jù)量大時(shí)，排序效率比較低，相比于vector中元素的排序，list是3倍慢
void reverse();，逆置.
_____________________:l1
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |:4
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 1 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 2 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
| _______________V________________________|_____________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 4 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
l1.reverse();
_____________________:l1
|list<int> |
|ListNode<int>* _head;|
|size_t _size; |:4
|________________|____|
_______________ | _________________
| ___________V_________________________V__|_____________ |
| |ListNode<int>illicit | int() | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| _______________V________________________|_____________ |
| |ListNode<int> | 4 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 3 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
| _______________V________________________|_____________ |
| |ListNode<int> | 2 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| |
| |________________|_____________________________________| |
| | ^ |
| ________________V_______________________|______________ |
| |ListNode<int> | 1 | |
| |ListNode<int>* _next; ListNode<int>* _prev; int data; | |
| |________________|______________________________________| |
|____________________| ^________________|
仿函數(shù)
list<[具體類型]>對(duì)象的迭代器
G++下list<[具體類型]>的 迭代器設(shè)計(jì) 本質(zhì)就是封裝了指針的類模板，不同于順序表為核心的STL容器的迭代器本質(zhì)就是原生指針- 類模板：
template<class T,class Ref,class Ptr> class ListIterator;- 這里
T是list<[具體類型]>中的具體類型 - 這里
Ref是list<[具體類型]>中的具體類型& - 這里
Ptr是list<[具體類型]>中的具體類型*
- 這里
- 這里迭代器之所以是封裝，是因?yàn)橐\(yùn)算符重載
++運(yùn)算符，鏈表中節(jié)點(diǎn)指針 直接指針++是 無法在鏈表每一個(gè) 節(jié)點(diǎn)對(duì)象 進(jìn)行跳轉(zhuǎn)的，只有數(shù)組可以直接指針++，鏈表就需要運(yùn)算符重載++讓其滿足再鏈表每一個(gè)節(jié)點(diǎn)跳轉(zhuǎn)的動(dòng)作
- 類模板：
迭代器類模板生成迭代器邏輯
list<[具體類型]>::iterator和list<[具體類型]>::const_iterator本質(zhì)是基于一個(gè)ListIterator類模板所生成的兩個(gè)不同的類list<[具體類型]>::iterator，本質(zhì)是ListIterator<[具體類型],[具體類型]&,[具體類型]*>，list為了讓迭代器統(tǒng)一命名就在list內(nèi)部進(jìn)行typedef ListIterator<T,T&,T*> iterator重命名list<[具體類型]>::const_iterator，本質(zhì)是ListIterator<[具體類型],const [具體類型]&,const [具體類型]*>，list為了讓迭代器統(tǒng)一命名就在list內(nèi)部進(jìn)行typedef ListIterator<T,T&,T*> const_iterator重命名
：類模板 ：類
_______________________________________ ____________________________________：list<[具體類型]>::iterator
|ListIterator<T,Ref,Self> | |ListIterator<T,T&,T*> |
|ListNode<T> _node; | |ListNode<T> _node; |
|ListIterator<T,Ref,Self> operator++(); |-----Ref=T&; Self=T*;-->|ListIterator<T,T&,T*> operator++(); |
|ListIterator<T,Ref,Self> operator--(); | |ListIterator<T,T&,T*> operator--(); |
|T& operator*(); | |T& operator*(); |
|_______________________________________| |____________________________________|
|
Ref=const T&
Self=const T*
|
| ：類
_____V_________________________________：list<[具體類型]>::const_iterator
|ListIterator<T,const T&,const T*> |
|ListNode<T> _node; |
|ListIterator<T,Ref,Self> operator++(); |
|ListIterator<T,Ref,Self> operator--(); |
|T& operator*(); |
|_______________________________________|
list<[具體類型]>對(duì)象的非 const 迭代器
std::list<int> sl(1,3);
_____________________
|list<int> |
|ListNode<int>* _head;|
|________________|____|
| _________________________________________ :sl.end()
_____________________________________V________________ |ListIterator<int> |
|ListNode<int>illicit int() |<-----|-ListNode<int>* _node |
|ListNode<int>* _next; ListNode<int>* _prev; int data;| |ListIterator<int,int&,int*> operator++();|
|________________|_________________________|___________| |ListIterator<int,int&,int*> operator--();|
| ^ ^ | |int& operator*(); |
| | | | |_________________________________________|
________________V_|_____________________|_V___________ _________________________________________ :sl.begin()
|ListNode<int> | | 3 | |ListIterator<int> |
|ListNode<int>* _next; ListNode<int>* _prev; int data;|<-----|-ListNode<int>* _node |
|______________________________________________________| |ListIterator<int,int&,int*> operator++();|
|ListIterator<int,int&,int*> operator--();|
|int& operator*(); |
|_________________________________________|
list<[具體類型]>對(duì)象的 const 迭代器
const [類型] [標(biāo)識(shí)符]，因?yàn)閇標(biāo)識(shí)符]被const保護(hù)，因此只要通過該[標(biāo)識(shí)符] 合法得到的地址或者成員變量的標(biāo)識(shí)符，這個(gè)地址和成員變量的標(biāo)識(shí)符就天然的就被const修飾list<[具體類型]>::const_iterator就是list<[具體類型]>的const迭代器，這里list<[具體類型]>::const_iterator本質(zhì)就是ListConstIterator<[具體類型]>
這里
list<[具體類型]>::const_iterator不是const ListIterator<[具體類型]>，是因?yàn)?code>const ListIterator<[具體類型]>其const修飾的是_node這個(gè)成員變量標(biāo)識(shí)符，而我們要const修飾*_node這個(gè)標(biāo)識(shí)符，因此我們需要新的迭代器類 讓其內(nèi)部是const修飾的是*_node這個(gè)標(biāo)識(shí)符才可以
const std::list<int> sl(1,3);
_____________________________________________________________
|const sl _____________________ |
| |list<int> | |
| |ListNode<int>* _head;| |
| |________________|____| |
|-----------------------------------------|-------------------| _____________________________________________________ :sl.cend()
|code read-only protected | | |code protected the pointed resource |
| _____________________________________V________________ | |ListIterator<int,const int&,const int*> |
| |ListNode<int>illicit int() |<-|---|-ListNode<int>* _node |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | |ListIterator<int,const int&,const int*> operator++();|
| |________________|_________________________|___________| | |ListIterator<int,const int&,const int*> operator--();|
| | ^ ^ | | |const int& operator*(); |
| | | | | | |_____________________________________________________|
| ________________V_|_____________________|_V___________ | _____________________________________________________ :sl.cbegin()
| |ListNode<int> | | 3 | | |code protected the pointed resource |
| |ListNode<int>* _next; ListNode<int>* _prev; int data;| | |ListIterator<int,const int&,const int*> |
| | ^ |<-|---|-ListNode<int>* _node |
| |____________________________________________________|_| | |ListIterator<int,const int&,const int*> operator++();|
| | | |ListIterator<int,const int&,const int*> operator--();|
| | | |const int& operator*(); |
| | | |const int* operator->(); |
|________________________________________________________|____| |________________|____________________________________|
|_________________________|
ListIterator& operator++()，前置++當(dāng)前迭代器進(jìn)行更新，迭代器去指向的當(dāng)前節(jié)點(diǎn) 的下一個(gè)節(jié)點(diǎn)，返回值對(duì)象 為當(dāng)前更新好的迭代器對(duì)象ListIterator operator++(int)，創(chuàng)建局部迭代器對(duì)象tmp=當(dāng)前迭代器對(duì)象，然后當(dāng)前迭代器進(jìn)行更新，迭代器去指向的當(dāng)前節(jié)點(diǎn) 的下一個(gè)節(jié)點(diǎn)，返回值對(duì)象 為tmp.ListIterator& operator--()，前置--當(dāng)前迭代器對(duì)象進(jìn)行更新，迭代器去指向的當(dāng)前節(jié)點(diǎn) 的上一個(gè)節(jié)點(diǎn)，返回值對(duì)象 為當(dāng)前更新好的迭代器對(duì)象ListIterator operator--(int)，創(chuàng)建局部迭代器對(duì)象tmp=當(dāng)前迭代器對(duì)象，然后當(dāng)前迭代器進(jìn)行更新，迭代器去指向的當(dāng)前節(jié)點(diǎn) 的上一個(gè)節(jié)點(diǎn)，返回值對(duì)象 為tmp.T& operator*()，返回值對(duì)象 為當(dāng)前迭代器對(duì)象 所指向節(jié)點(diǎn)的data變量.bool operator==(const ListIterator& it)，當(dāng)前迭代器對(duì)象指向的節(jié)點(diǎn)是否和it指向的節(jié)點(diǎn)是同一個(gè)，是返回真，反之返回假bool operator!=(const ListIterator& it)，當(dāng)前迭代器對(duì)象指向的節(jié)點(diǎn)是否和it指向的節(jié)點(diǎn)是同一個(gè)，是返回假，反之返回真T* operator->()，返回值為 當(dāng)前迭代器的成員變量所指向的節(jié)點(diǎn) 的 特定成員變量的地址
std::list<int> sl(2,3);
_____________________
|list<int> |
|ListNode<int>* _head;|
|________________|____|
|
_____________________________________V________________
|ListNode<int>illicit int() |
|ListNode<int>* _next; ListNode<int>* _prev; int data;|
|________________|_________________________|___________|
| ^ ^ |
| | | |
________________V_|_____________________|_V___________ ____________________________________________ :sl.begin()
|ListNode<int> | | 3 | |ListIterator<int> |
|ListNode<int>* _next; ListNode<int>* _prev; int data;|<-----|-ListNode* _node |
| ^ | | |
|___________________________________________________|__| |ListIterator<int,int&,int*> operator--(); |
| |int& operator*(); |
| |ListIterator<int,int&,int*> operator++(); |
| |int* operator->(); |
| |__________|_________________________________|
|____________________|
到此這篇關(guān)于C++ list容器基本邏輯結(jié)構(gòu)詳解的文章就介紹到這了,更多相關(guān)C++ list容器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
VisualStudio2019解決scanf函數(shù)報(bào)錯(cuò)問題
在 Visual Studio 2019 編輯代碼時(shí),前期剛剛接觸到VS編譯器時(shí)存在的困惑,當(dāng)用scanf()函數(shù),進(jìn)行輸入時(shí),在運(yùn)行的時(shí)候編譯器會(huì)出現(xiàn)警告報(bào)錯(cuò),本文就來介紹一下解決方法2023-08-08
C++指針數(shù)組、數(shù)組指針、數(shù)組名及二維數(shù)組技巧匯總
這篇文章主要介紹了C++指針數(shù)組、數(shù)組指針、數(shù)組名及二維數(shù)組技巧匯總,對(duì)于深入理解C++數(shù)組與指針來說非常重要,需要的朋友可以參考下2014-08-08
在本篇文章里小編給大家整理的是關(guān)于c++從函數(shù)返回?cái)?shù)組的方法代碼，有興趣的朋友們可以學(xué)習(xí)參考下。2020-02-02
這篇文章主要介紹了c語言如何輸入帶\n和空格的字符串問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2025-07-07
vc++實(shí)現(xiàn)的tcp socket客戶端和服務(wù)端示例
這篇文章主要介紹了vc++實(shí)現(xiàn)的tcp socket客戶端和服務(wù)端示例,需要的朋友可以參考下2014-03-03
C++超詳細(xì)講解函數(shù)參數(shù)的默認(rèn)值
在C++中，定義函數(shù)時(shí)可以給形參指定一個(gè)默認(rèn)的值，這樣調(diào)用函數(shù)時(shí)如果沒有給這個(gè)形參賦值（沒有對(duì)應(yīng)的實(shí)參），那么就使用這個(gè)默認(rèn)的值。也就是說，調(diào)用函數(shù)時(shí)可以省略有默認(rèn)值的參數(shù)2022-05-05
QtObject 類型是一個(gè)非可視元素,僅包含objectName屬性,如果需要一個(gè)非常輕量級(jí)的類型來包含一組自定義屬性,那么創(chuàng)建一個(gè)QtObject,本文給大家介紹qml中QtObject類型的使用,感興趣的朋友一起看看吧2024-01-01
以下是對(duì)CFile與CStdioFile的文件讀寫使用方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-09-09
C++ float轉(zhuǎn)std::string 小數(shù)位數(shù)控制問題
這篇文章主要介紹了C++ float轉(zhuǎn)std::string 小數(shù)位數(shù)控制問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
使用Libmicrohttpd搭建內(nèi)嵌(本地)服務(wù)器的方法
下面小編就為大家?guī)硪黄褂肔ibmicrohttpd搭建內(nèi)嵌(本地)服務(wù)器的方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08