C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)
一、list的介紹以及使用
1.1 list的介紹
1、list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器,并且該容器可以前后雙向迭代(所謂的常熟范圍內(nèi),就是時(shí)間復(fù)雜度為O(1))
2. list的底層是雙向鏈表結(jié)構(gòu),雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中,在節(jié)點(diǎn)中通過(guò)指針指向其前一個(gè)元素和后一個(gè)元素。
3. list與forward_list非常相似:最主要的不同在于forward_list是單鏈表,只能朝前迭代,已讓其更簡(jiǎn)單高效。
4. 與其他的序列式容器相比(array,vector,deque),list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
5. 與其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問(wèn),比如:要訪問(wèn)list的第6個(gè)元素,必須從已知的位置(比如頭部或者尾部)迭代到該位置,在這段位置上迭代需要線性的時(shí)間開(kāi)銷(xiāo);list還需要一些額外的空間,以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這可能是一個(gè)重要的因素)
這一段關(guān)于list的特性,需要能夠與vector對(duì)比理解。
1.2 list的使用
1.2.1 list的構(gòu)造
構(gòu)造函數(shù)( (constructor)) | 接口說(shuō)明 |
list() | 構(gòu)造空的list |
list (size_type n, const value_type& val = value_type()) | 構(gòu)造的list中包含n個(gè)值為val的元素 |
list (const list& x) | 拷貝構(gòu)造函數(shù) |
list (InputIterator first, InputIterator last) | 用[first, last)區(qū)間中的元素構(gòu)造list |
#include <iostream> #include <list> using namespace std; int main() { std::list<int> l1; // 構(gòu)造空的l1 std::list<int> l2(4, 100); // l2中放4個(gè)值為100的元素 std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左閉右開(kāi)的區(qū)間構(gòu)造l3 std::list<int> l4(l3); // 用l3拷貝構(gòu)造l4 // 以數(shù)組為迭代器區(qū)間構(gòu)造l5 int array[] = { 16,2,77,29 }; std::list<int> l5(array, array + sizeof(array) / sizeof(int)); // 用迭代器方式打印l5中的元素 for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++) std::cout << *it << " "; std::cout << endl; // C++11范圍for的方式遍歷 for (auto& e : l5) { std::cout << e << " "; } std::cout << endl; return 0; }
1.2.2 list iterator的使用
函數(shù)聲明 | 接口說(shuō)明 |
begin + end | 返回第一個(gè)元素的迭代器+返回最后一個(gè)元素下一個(gè)位置的迭代器 |
rbegin + rend | 返回第一個(gè)元素的reverse_iterator,即end位置,返回最后一個(gè)元素下一個(gè)位置的reverse_iterator,即begin位置 |
注意:
1、begin與end為正向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向后移動(dòng)
2、rbegin(end)與rend(begin)為反向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向前移動(dòng)
#include <iostream> #include <list> using namespace std; void print_list(const list<int>& l) { // 注意這里調(diào)用的是list的 begin() const,返回list的const_iterator對(duì)象 for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) { cout << *it << " "; // *it = 10; 編譯不通過(guò) } cout << endl; } int main() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array + sizeof(array) / sizeof(array[0])); // 使用正向迭代器正向list中的元素 for (list<int>::iterator it = l.begin(); it != l.end(); ++it) { cout << *it << " "; } cout << endl; // 使用反向迭代器逆向打印list中的元素 for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it) { cout << *it << " "; } cout << endl; return 0; }
1.2.3 list capacity
函數(shù)聲明 | 接口說(shuō)明 |
empty | 檢測(cè)list是否為空,是返回true,否則返回false |
size | 返回list中有效節(jié)點(diǎn)的個(gè)數(shù) |
1.2.4 list element access
函數(shù)聲明 | 接口說(shuō)明 |
front | 返回list的第一個(gè)節(jié)點(diǎn)中值的引用 |
back | 返回list的最后一個(gè)節(jié)點(diǎn)中值的引用 |
1.2.5 list modifiers
函數(shù)聲明 | 接口說(shuō)明 |
push_front | 在list首元素前插入值為val的元素 |
pop_front | 刪除list中第一個(gè)元素 |
push_back | 在list尾部插入值為val的元素 |
pop_back | 刪除list中最后一個(gè)元素 |
insert | 在list position 位置中插入值為val的元素 |
erase | 刪除list position位置的元素 |
swap | 交換兩個(gè)list中的元素 |
clear | 清空l(shuí)ist中的有效元素 |
這里就不用代碼的形式展示了
1.2.6 list的迭代器失效
前面說(shuō)過(guò),此處大家可將迭代器暫時(shí)理解成類(lèi)似于指針,迭代器失效即迭代器所指向的節(jié)點(diǎn)的無(wú)效,即該節(jié)點(diǎn)被刪除了。因?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ì)受到影響
#include <iostream> #include <list> using namespace std; void TestListIterator1() { 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é)點(diǎn)已被刪除,因此it無(wú)效,在下一次使用it時(shí),必須先給其賦值 l.erase(it); ++it; } } // 改正 void TestListIterator() { 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的模擬實(shí)現(xiàn)
2.1 模擬實(shí)現(xiàn)list
這是本章的重中之重。
#include <iostream> #include <assert.h> using std::cout; using std::endl; namespace zjx { // List的節(jié)點(diǎn)類(lèi) template<class T> struct ListNode { ListNode(const T& val = T()) :_pPre(nullptr), _pNext(nullptr), _val(val) { } ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; }; //List的迭代器類(lèi) template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr) { _pNode = pNode; } //ListIterator(const Self& l); Ref operator*() { return _pNode->_val; } Ptr operator->() { return &_pNode->_val; } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } 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; } public: PNode _pNode; }; //list類(lèi) 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)造 list() { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } //構(gòu)造函數(shù) list(int n, const T& value = T()) { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; for (int i = 0; i < n; i++) { push_back(value); } } template <class Iterator> list(Iterator first, Iterator last) { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; while (first != last) { push_back(*first); first++; } } //拷貝構(gòu)造函數(shù) list(const list<T>& l) { //用迭代器先構(gòu)造出來(lái)一個(gè) list tmp(l.begin(), l.end()); _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; std::swap(_pHead, tmp._pHead); } list<T>& operator=(list<T> l) { std::swap(_pHead, l._pHead); return *this; } ~list() { clear(); delete _pHead; _pHead = nullptr; } //List Iterator iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead->_pNext); } const_iterator end() const { return const_iterator(_pHead); } // List Capacity size_t size()const//這個(gè)函數(shù)右邊的const是用來(lái)限定this指針的。原本的this指針,不可以改變指向,可以改變所知的內(nèi)容。 //但若要對(duì)所指向的內(nèi)容加以限定的話,那就在函數(shù)的右邊加上const,表示此函數(shù)的隱藏的參數(shù),也就是this指針,被加以const限定。 { size_t count = 0; const_iterator cur = begin(); while (cur != end()) { count++; cur++; } return count; } //list為空返回1,否則返回0 bool empty()const { return size() == 0; } // List Access T& front() { return begin()._pNode->_val; } const T& front()const { return begin()._pNode->_val; } T& back() { return _pHead->_pPre->_val; } const T& back()const { return _pHead->_pPre->_val; } // List Modify //void push_back(const T& val) //{ // insert(begin(), val); //} void push_back(const T& val) { Node* tail = _pHead->_pPre; Node* newnode = new Node(val); tail->_pNext = newnode; newnode->_pPre = tail; newnode->_pNext = _pHead; _pHead->_pPre = newnode; } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); } 在pos位置前插入值為val的節(jié)點(diǎn) iterator insert(iterator pos, const T& val) { PNode next = pos._pNode; PNode prev = next->_pPre; PNode newnode = new Node(val); newnode->_pNext = next; newnode->_pPre = prev; prev->_pNext = newnode; next->_pPre = newnode; return iterator(newnode); } 刪除pos位置的節(jié)點(diǎn),返回該節(jié)點(diǎn)的下一個(gè)位置 iterator erase(iterator pos) { assert(pos != end()); PNode next = pos._pNode->_pNext; PNode prev = pos._pNode->_pPre; delete pos._pNode; prev->_pNext = next; next->_pPre = prev; return iterator(next); } void clear() { iterator cur = begin(); while (cur != end()) { erase(cur++); } _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } //void swap(list<T>& l); private: void CreateHead() { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } PNode _pHead; }; }; class Date { private: int _year; int _month; int _day; public: Date(int year = 0, int month = 0, int day = 0) :_year(year), _month(month), _day(day) { } void print() { std::cout << _year << " " << _month << " " << _day << std::endl; } }; int main() { using namespace zjx; list<Date> it; it.push_back(Date(2022, 5, 16)); it.push_back(Date(2022, 5, 17)); it.push_back(Date(2022, 5, 18)); it.push_back(Date(2022, 5, 19)); it.push_back(Date(2022, 5, 20)); for (auto e : it) { e.print(); } cout << endl; list<int> a1(5, 2); for (auto e : a1) { cout << e << " "; } cout << endl; list<Date> a2(it); for (auto e : a2) { e.print(); } cout << endl; int arr[] = { 1,2,3,4,5,6,7,8,9 }; list<int> a3(arr, arr + 9); for (auto e : a3) { cout << e << " "; } cout << endl; a1 = a3; for (auto e : a1) { cout << e << " "; } cout << endl; cout << "a3的元素的個(gè)數(shù) = " << a3.size() << endl; list<int> a4; cout << a4.empty() << endl; const auto ans1 = a3.front(); auto ans2 = a3.back(); cout << "ans1 = " << ans1 << " " << "ans2 = " << ans2 << endl; a3.push_front(30); a3.pop_back(); a3.pop_front(); a3.pop_front(); for (auto e : a3) { cout << e << " "; } cout << endl; return 0; }
函數(shù)右邊的const是用來(lái)限定this指針的。原本的this指針,不可以改變指向,可以改變所知的內(nèi)容。
但若要對(duì)所指向的內(nèi)容加以限定的話,那就在函數(shù)的右邊加上const,表示此函數(shù)的隱藏的參數(shù),也就是this指針,被加以const限定。
vector缺陷:
連續(xù)的物理空間,是優(yōu)勢(shì),也是劣勢(shì)。優(yōu)勢(shì):支持高效隨機(jī)訪問(wèn)。
劣勢(shì):
1、空間不夠要增容,增容代價(jià)比較大。
2、可能存在一定空間浪費(fèi)。按需申請(qǐng),會(huì)導(dǎo)致頻繁增容,所以一般都會(huì)2倍左右擴(kuò)容。
3、頭部或者中部插入刪除需要挪動(dòng)數(shù)據(jù),效率低下list很好的解決vector的以上問(wèn)題:
1、按需申請(qǐng)釋放空間。
2、list任意位置支持O(1)插入刪除。
const對(duì)象會(huì)自動(dòng)找到const修飾的函數(shù)
總結(jié)
到此這篇關(guān)于C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ list講解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解,并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合的合并及查詢(xún)問(wèn)題,并查集的思想是用一個(gè)數(shù)組表示了整片森林,需要的朋友可以參考下2023-08-08C++實(shí)現(xiàn)LeetCode(312.打氣球游戲)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(312.打氣球游戲),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)
這篇文章主要介紹了C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn),文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-08-08C語(yǔ)言編程動(dòng)態(tài)內(nèi)存分配常見(jiàn)錯(cuò)誤全面分析
這篇文章主要介紹了C語(yǔ)言編程中動(dòng)態(tài)內(nèi)存分配的常見(jiàn)錯(cuò)誤全面分析講解,同樣遇到過(guò)C語(yǔ)言動(dòng)態(tài)內(nèi)存分配各種問(wèn)題的同學(xué)可以借鑒參考下,希望能夠有所幫助2021-10-10C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語(yǔ)言中單鏈表的常用操作,感興趣的可以學(xué)習(xí)一下2022-07-07