C++數據結構之list詳解
前言
list相較於vector來說會顯得復雜,它的好處是在任意位置插入,刪除都是一個O(1)的時間復雜度。
一、list的節點
template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; };
這個是在stl3.0版本下的list的節點的定義,節點裡面有一個前指針,一個後指針,有一個數據data。這裡隻能知道他是一個雙向鏈表
,我們可以再稍微看一下list關於它的構造函數
。
class list --> list() { empty_initialize(); void empty_initialize() { node = get_node(); node->next = node; node->prev = node; }
再看一下它的list(),可以看出他調用的empty_initialize(),是創建瞭一個頭結點,並且是一個循環的結構。
綜上:list的總體結構是一個帶頭循環雙向鏈表
二、list的迭代器
迭代器通常是怎麼使用的,看一下下面這段代碼。
int main() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); l.push_back(5); l.push_back(6); list<int>::iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; it++; } cout << endl; return 0; }
- 我們從list< int >當中定義一個iterator對象,然後讓他去訪問我們的節點
- 並且他所支持的操作有++,解引用,當然還有 –等等
stl3.0當中的迭代器實現:
template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } reference operator*() const { return (*node).data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; }
大傢感興趣可以先看看上面的,我們先用一個簡述版的來帶大傢簡要實現一下
template<class T> class __list_node { public: __list_node(const T& val = T())//用一個全缺省比較好 :_next(nullptr) ,_pre(nullptr) ,node(val) {} public: __list_node<T>* _next; __list_node<T>* _pre; T node; }; template<class T> class __list_itertaor//這裡是迭代器 { public: typedef __list_node<T> Node; __list_itertaor(Node* node) { _node = node; } bool operator!=(const __list_itertaor<T>& it) { return _node != it._node; } __list_itertaor<T>& operator++() { _node = _node->_next; return *this; } T& operator*() { return _node->node; } private: Node* _node; };
這裡的實現是不完整的,但是很適合說明問題。通過我們去重載opertaor++,和重載opertaor*,可以讓我們像指針一樣去訪問一個節點,讓我們可以跟vector和string一樣用同樣的接口就能實現對數據的訪問,這是非常厲害的一個技術。
註意點:
- 我們通過對節點的操作,重載瞭operator++等接口實現瞭對一個節點的訪問,訪問的時候實際上也就是創建迭代器對象,對我們的數據進行訪問,所以我們封裝的時候是將節點的指針進行封裝。
- list相比vector,正因為他們的底層結構不相同,list的迭代器在插入操作和接合操作(splice)
都不會造成迭代器失效
,隻有刪除的時候,隻有那個被刪除元素的迭代器失效
,而不影響後面的,而vector就統統失效瞭。
模板參數為什麼是三個
2.1 const 迭代器
有這樣一種情況,我們需要const對象去遍歷,假如我們有個函數叫做print_list(const list< int >& lt)
;
傳參: 其中傳參中const是因為不會對對象進行修改,加引用是因為不用深拷貝,提高效率。
功能: 這個函數就是去打印鏈表裡面的內容的。但是按照我們上面的實現,會出現什麼問題呢。
這很正常,在const迭代器就去生成const迭代器對象,在vector,string這些迭代器就是原生指針的時候我們隻需要typedef const T* const_iterator
,那如果我們在我們生成的list也做類似的操作,來看看結果。
結果我們發現,好像沒多大問題,但是我們嘗試修改const迭代器裡面的內容時,卻發現能修改成功。const迭代器怎麼能修改裡面的數據呢?這就有問題瞭!!!說明我們的有一個巨大的隱患在裡面。
2.2 修改方法
最簡單的方法當然就是再寫多一個迭代器,把__list_iterator換成__list_const_iterator 之類的,但是我們認真觀察的話,實際上這兩個類很多東西是重復的,隻有在operator*,operator->時所需要的返回值,我們需要找到一種方法去讓const對象的返回值也是const對象
,答案就是添加多兩個個模板參數。
以下以添加一個模板參數為例,實現一個Ref operator*();
template<class T> class __list_node { public: __list_node(const T& val = T())//用一個全缺省比較好 :_next(nullptr) ,_pre(nullptr) ,node(val) {} public: __list_node<T>* _next; __list_node<T>* _pre; T node; }; template<class T,class Ref> class __list_itertaor { public: typedef __list_node<T> Node; __list_itertaor(Node* node) { _node = node; } bool operator!=(const __list_itertaor<T,Ref>& it) { return _node != it._node; } __list_itertaor<T,Ref>& operator++() { _node = _node->_next; return *this; } Ref operator*()//返回Ref,返回值就有區別啦 { return _node->node; } private: Node* _node; }; template<class T> class list { typedef __list_node<T> Node; public: typedef __list_itertaor<T,T&> iterator; typedef __list_itertaor<T, const T&> const_iterator;//修改 iterator begin() { return iterator(_node->_next); } iterator end() { return iterator(_node); } const_iterator begin()const { return const_iterator(_node->_next); } const_iterator end()const { return const_iterator(_node); } list() { _node = new Node; _node->_next = _node; _node->_pre = _node; } void push_back(const T& val) { Node* newnode = new Node(val); Node* tail = _node->_pre; tail->_next = newnode; newnode->_pre = tail; newnode->_next = _node; _node->_pre = newnode; } private: Node* _node; };
一圖瞭解:也就是我們的測試端test函數中定義list< int >::const_iterator cit= l.begin();
的時候迭代器對象就會識別到定義的const迭代器,它的第二個模板參數放的就是const T&,這樣子我們operator*()返回的時候隻需要返回第二個模板參數就可以瞭
。
同理,我們要用到的接口operator->當中也會有const對象和普通對象調用的情況。我們這裡把實現的代碼放出來,有需要的自取。
–》碼雲鏈接《–
二、美中不足
list上面說的仿佛都是優點
任意位置的O(1)時間的插入刪除,迭代器失效的問題變少瞭。但他又有哪些不足呢
- 不支持隨機訪問
- 排序的效率慢,庫中的sort用的是歸並排序–>快排需要三數取中,對於鏈表來說實現出來效率也低,所以當鏈表的元素需要進行排序的時候,我們通常也都會拷貝到vector當中,再用vector當中的排序。
- 同理鏈表的逆置效率也不高!
三、迭代器的分類
迭代器從功能角度來看的話分為:const迭代器/普通迭代器 + 正反向。
從容器底層結構角度分為:單向,雙向,隨機。
- 單向: 單鏈表迭代器(forward_list)/哈希表迭代器;這些隻支持單向++;
- 雙向: 雙鏈表迭代器/map迭代器;這些支持的++/- -操作;
- 隨機迭代器: string/vector/deque;這些是支持++/- -/+/-操作的,類似原生指針一般。
我們來看一下部分函數的,比如sort當中的模板參數寫成RandomAccessIterator,就是想要明示使用者他這裡需要的是一個隨機的迭代器,在它的底層會調用到迭代器的+操作,所以這個時候如果你傳的是一個雙向或者單向的迭代器就不行瞭!!
//sort的函數聲明 template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
比如說reverse函數聲明,它的模板參數是BidirectionalIterator,也就是需要一個支持雙向的迭代器,這個時候其實我們就可以傳隨機迭代器和雙向迭代器
,從上面的迭代器支持的操作可以看到,隨機迭代器是支持雙向迭代器的所有操作的
。
同理,如果是一個需要單向迭代器的地方,我們就可以傳一個雙向,隨機,單向迭代器瞭!!
std::reverse template <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last);
從stl3.0當中的stl_iterator.h,我們可以看出當中的繼承關系。這個我們之後再講。
註意:difference_type為兩個迭代器之間的距離。類型ptrdiff_t為無符號整形。
3.x std::find的一個報錯
當我們實現瞭自己的數據結構,如list,我們如果用庫裡的std:find查找我們實現的數據結構當中的數據會報錯。博主的測試版本為vs2013,在其他版本可能不做檢查,不會報錯。
void test_list() { list<int> l; l.push_back(5); list<int>::iterator it = std::find(l.begin(), l.end(), 5); }
報錯:這裡的報錯說的是iterator_category不在我們的迭代器當中,這個是對我們迭代器類型的一個檢查。
stl_list.h當中為迭代器添加瞭如下聲明來解決這個問題。
解決方案: 我們可以用stl3.0版本下stl_list.h當中的迭代器的聲明。也可以用release版本下,都是可以跑過的。
typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef ptrdiff_t difference_type;
總結
list的講解就到這裡啦,看到這裡不妨一鍵三連。
到此這篇關於C++數據結構之list詳解的文章就介紹到這瞭,更多相關C++ list 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!