国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【C++】list詳解

wanghui / 3288人閱讀

摘要:結(jié)果我們發(fā)現(xiàn),好像沒(méi)多大問(wèn)題,但是我們嘗試修改迭代器里面的內(nèi)容時(shí),卻發(fā)現(xiàn)能修改成功。注意為兩個(gè)迭代器之間的距離。報(bào)錯(cuò)這里的報(bào)錯(cuò)說(shuō)的是不在我們的迭代器當(dāng)中,這個(gè)是對(duì)我們迭代器類型的一個(gè)檢查。當(dāng)中為迭代器添加了如下聲明來(lái)解決這個(gè)問(wèn)題。


前言

list相較于vector來(lái)說(shuō)會(huì)顯得復(fù)雜,它的好處是在任意位置插入,刪除都是一個(gè)O(1)的時(shí)間復(fù)雜度。


一、list的節(jié)點(diǎn)

</>復(fù)制代碼

  1. template <class T>struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data;};

這個(gè)是在stl3.0版本下的list的節(jié)點(diǎn)的定義,節(jié)點(diǎn)里面有一個(gè)前指針,一個(gè)后指針,有一個(gè)數(shù)據(jù)data。這里只能知道他是一個(gè)雙向鏈表,我們可以再稍微看一下list關(guān)于它的構(gòu)造函數(shù)

</>復(fù)制代碼

  1. class list --> list() { empty_initialize(); void empty_initialize() { node = get_node(); node->next = node; node->prev = node; }

再看一下它的list(),可以看出他調(diào)用的empty_initialize(),是創(chuàng)建了一個(gè)頭結(jié)點(diǎn),并且是一個(gè)循環(huán)的結(jié)構(gòu)。

綜上:list的總體結(jié)構(gòu)是一個(gè)帶頭循環(huán)雙向鏈表



二、list的迭代器

迭代器通常是怎么使用的,看一下下面這段代碼。

</>復(fù)制代碼

  1. int main(){
  2. list<int> l;
  3. l.push_back(1);
  4. l.push_back(2);
  5. l.push_back(3);
  6. l.push_back(4);
  7. l.push_back(5);
  8. l.push_back(6);
  9. list<int>::iterator it = l.begin();
  10. while (it != l.end())
  11. {
  12. cout << *it << " ";
  13. it++;
  14. }
  15. cout << endl;
  16. return 0;}
  • 我們從list< int >當(dāng)中定義一個(gè)iterator對(duì)象,然后讓他去訪問(wèn)我們的節(jié)點(diǎn)
  • 并且他所支持的操作有++,解引用,當(dāng)然還有 --等等

stl3.0當(dāng)中的迭代器實(shí)現(xiàn):

</>復(fù)制代碼

  1. 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; }

大家感興趣可以先看看上面的,我們先用一個(gè)簡(jiǎn)述版的來(lái)帶大家簡(jiǎn)要實(shí)現(xiàn)一下

</>復(fù)制代碼

  1. template<class T>
  2. class __list_node
  3. {
  4. public:
  5. __list_node(const T& val = T())//用一個(gè)全缺省比較好
  6. :_next(nullptr)
  7. ,_pre(nullptr)
  8. ,node(val)
  9. {}
  10. public:
  11. __list_node<T>* _next;
  12. __list_node<T>* _pre;
  13. T node;
  14. };
  15. template<class T>
  16. class __list_itertaor//這里是迭代器
  17. {
  18. public:
  19. typedef __list_node<T> Node;
  20. __list_itertaor(Node* node)
  21. {
  22. _node = node;
  23. }
  24. bool operator!=(const __list_itertaor<T>& it)
  25. {
  26. return _node != it._node;
  27. }
  28. __list_itertaor<T>& operator++()
  29. {
  30. _node = _node->_next;
  31. return *this;
  32. }
  33. T& operator*()
  34. {
  35. return _node->node;
  36. }
  37. private:
  38. Node* _node;
  39. };

這里的實(shí)現(xiàn)是不完整的,但是很適合說(shuō)明問(wèn)題。通過(guò)我們?nèi)ブ剌dopertaor++,和重載opertaor*,可以讓我們像指針一樣去訪問(wèn)一個(gè)節(jié)點(diǎn),讓我們可以跟vector和string一樣用同樣的接口就能實(shí)現(xiàn)對(duì)數(shù)據(jù)的訪問(wèn),這是非常厲害的一個(gè)技術(shù)。

注意點(diǎn):

  • 我們通過(guò)對(duì)節(jié)點(diǎn)的操作,重載了operator++等接口實(shí)現(xiàn)了對(duì)一個(gè)節(jié)點(diǎn)的訪問(wèn),訪問(wèn)的時(shí)候?qū)嶋H上也就是創(chuàng)建迭代器對(duì)象,對(duì)我們的數(shù)據(jù)進(jìn)行訪問(wèn),所以我們封裝的時(shí)候是將節(jié)點(diǎn)的指針進(jìn)行封裝。
  • list相比vector,正因?yàn)樗麄兊牡讓咏Y(jié)構(gòu)不相同,list的迭代器在插入操作和接合操作(splice)都不會(huì)造成迭代器失效,只有刪除的時(shí)候,只有那個(gè)被刪除元素的迭代器失效,而不影響后面的,而vector就統(tǒng)統(tǒng)失效了。

2.1、模板參數(shù)為什么是三個(gè)

2.2 const 迭代器

有這樣一種情況,我們需要const對(duì)象去遍歷,假如我們有個(gè)函數(shù)叫做print_list(const list< int >& lt);
傳參: 其中傳參中const是因?yàn)椴粫?huì)對(duì)對(duì)象進(jìn)行修改,加引用是因?yàn)椴挥蒙羁截悾岣咝省?br /> 功能: 這個(gè)函數(shù)就是去打印鏈表里面的內(nèi)容的。但是按照我們上面的實(shí)現(xiàn),會(huì)出現(xiàn)什么問(wèn)題呢。

這很正常,在const迭代器就去生成const迭代器對(duì)象,在vector,string這些迭代器就是原生指針的時(shí)候我們只需要typedef const T* const_iterator,那如果我們?cè)谖覀兩傻膌ist也做類似的操作,來(lái)看看結(jié)果。

結(jié)果我們發(fā)現(xiàn),好像沒(méi)多大問(wèn)題,但是我們嘗試修改const迭代器里面的內(nèi)容時(shí),卻發(fā)現(xiàn)能修改成功。const迭代器怎么能修改里面的數(shù)據(jù)呢?這就有問(wèn)題了!!!說(shuō)明我們的有一個(gè)巨大的隱患在里面。

2.3 修改方法

最簡(jiǎn)單的方法當(dāng)然就是再寫(xiě)多一個(gè)迭代器,把__list_iterator換成__list_const_iterator 之類的,但是我們認(rèn)真觀察的話,實(shí)際上這兩個(gè)類很多東西是重復(fù)的,只有在operator*,operator->時(shí)所需要的返回值,我們需要找到一種方法去讓const對(duì)象的返回值也是const對(duì)象,答案就是添加多兩個(gè)個(gè)模板參數(shù)。
以下以添加一個(gè)模板參數(shù)為例,實(shí)現(xiàn)一個(gè)Ref operator*();

</>復(fù)制代碼

  1. template<class T>
  2. class __list_node
  3. {
  4. public:
  5. __list_node(const T& val = T())//用一個(gè)全缺省比較好
  6. :_next(nullptr)
  7. ,_pre(nullptr)
  8. ,node(val)
  9. {}
  10. public:
  11. __list_node<T>* _next;
  12. __list_node<T>* _pre;
  13. T node;
  14. };
  15. template<class T,class Ref>
  16. class __list_itertaor
  17. {
  18. public:
  19. typedef __list_node<T> Node;
  20. __list_itertaor(Node* node)
  21. {
  22. _node = node;
  23. }
  24. bool operator!=(const __list_itertaor<T,Ref>& it)
  25. {
  26. return _node != it._node;
  27. }
  28. __list_itertaor<T,Ref>& operator++()
  29. {
  30. _node = _node->_next;
  31. return *this;
  32. }
  33. Ref operator*()//返回Ref,返回值就有區(qū)別啦
  34. {
  35. return _node->node;
  36. }
  37. private:
  38. Node* _node;
  39. };
  40. template<class T>
  41. class list
  42. {
  43. typedef __list_node<T> Node;
  44. public:
  45. typedef __list_itertaor<T,T&> iterator;
  46. typedef __list_itertaor<T, const T&> const_iterator;//修改
  47. iterator begin()
  48. {
  49. return iterator(_node->_next);
  50. }
  51. iterator end()
  52. {
  53. return iterator(_node);
  54. }
  55. const_iterator begin()const
  56. {
  57. return const_iterator(_node->_next);
  58. }
  59. const_iterator end()const
  60. {
  61. return const_iterator(_node);
  62. }
  63. list()
  64. {
  65. _node = new Node;
  66. _node->_next = _node;
  67. _node->_pre = _node;
  68. }
  69. void push_back(const T& val)
  70. {
  71. Node* newnode = new Node(val);
  72. Node* tail = _node->_pre;
  73. tail->_next = newnode;
  74. newnode->_pre = tail;
  75. newnode->_next = _node;
  76. _node->_pre = newnode;
  77. }
  78. private:
  79. Node* _node;
  80. };

一圖了解:也就是我們的測(cè)試端test函數(shù)中定義list< int >::const_iterator cit= l.begin();的時(shí)候迭代器對(duì)象就會(huì)識(shí)別到定義的const迭代器,它的第二個(gè)模板參數(shù)放的就是const T&,這樣子我們operator*()返回的時(shí)候只需要返回第二個(gè)模板參數(shù)就可以了

同理,我們要用到的接口operator->當(dāng)中也會(huì)有const對(duì)象和普通對(duì)象調(diào)用的情況。我們這里把實(shí)現(xiàn)的代碼放出來(lái),有需要的自取。

–》碼云鏈接《–



二、美中不足

list上面說(shuō)的仿佛都是優(yōu)點(diǎn)

任意位置的O(1)時(shí)間的插入刪除,迭代器失效的問(wèn)題變少了。但他又有哪些不足呢

  • 不支持隨機(jī)訪問(wèn)
  • 排序的效率慢,庫(kù)中的sort用的是歸并排序–>快排需要三數(shù)取中,對(duì)于鏈表來(lái)說(shuō)實(shí)現(xiàn)出來(lái)效率也低,所以當(dāng)鏈表的元素需要進(jìn)行排序的時(shí)候,我們通常也都會(huì)拷貝到vector當(dāng)中,再用vector當(dāng)中的排序。
  • 同理鏈表的逆置效率也不高!


三、迭代器的分類

迭代器從功能角度來(lái)看的話分為:const迭代器/普通迭代器 + 正反向。

從容器底層結(jié)構(gòu)角度分為:單向,雙向,隨機(jī)。

  • 單向: 單鏈表迭代器(forward_list)/哈希表迭代器;這些只支持單向++;
  • 雙向: 雙鏈表迭代器/map迭代器;這些支持的++/- -操作;
  • 隨機(jī)迭代器: string/vector/deque;這些是支持++/- -/+/-操作的,類似原生指針一般。

我們來(lái)看一下部分函數(shù)的,比如sort當(dāng)中的模板參數(shù)寫(xiě)成RandomAccessIterator,就是想要明示使用者他這里需要的是一個(gè)隨機(jī)的迭代器,在它的底層會(huì)調(diào)用到迭代器的+操作,所以這個(gè)時(shí)候如果你傳的是一個(gè)雙向或者單向的迭代器就不行了!!

</>復(fù)制代碼

  1. //sort的函數(shù)聲明template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);custom (2)
  2. template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

比如說(shuō)reverse函數(shù)聲明,它的模板參數(shù)是BidirectionalIterator,也就是需要一個(gè)支持雙向的迭代器,這個(gè)時(shí)候其實(shí)我們就可以傳隨機(jī)迭代器和雙向迭代器,從上面的迭代器支持的操作可以看到,隨機(jī)迭代器是支持雙向迭代器的所有操作的
同理,如果是一個(gè)需要單向迭代器的地方,我們就可以傳一個(gè)雙向,隨機(jī),單向迭代器了!!

</>復(fù)制代碼

  1. std::reversetemplate <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last);

從stl3.0當(dāng)中的stl_iterator.h,我們可以看出當(dāng)中的繼承關(guān)系。這個(gè)我們之后再講。

注意:difference_type為兩個(gè)迭代器之間的距離。類型ptrdiff_t為無(wú)符號(hào)整形。



3.x std::find的一個(gè)報(bào)錯(cuò)

當(dāng)我們實(shí)現(xiàn)了自己的數(shù)據(jù)結(jié)構(gòu),如list,我們?nèi)绻脦?kù)里的std:find查找我們實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)當(dāng)中的數(shù)據(jù)會(huì)報(bào)錯(cuò)。博主的測(cè)試版本為vs2013,在其他版本可能不做檢查,不會(huì)報(bào)錯(cuò)。

</>復(fù)制代碼

  1. void test_list()
  2. {
  3. list<int> l;
  4. l.push_back(5);
  5. list<int>::iterator it = std::find(l.begin(), l.end(), 5);
  6. }

報(bào)錯(cuò):這里的報(bào)錯(cuò)說(shuō)的是iterator_category不在我們的迭代器當(dāng)中,這個(gè)是對(duì)我們迭代器類型的一個(gè)檢查。



stl_list.h當(dāng)中為迭代器添加了如下聲明來(lái)解決這個(gè)問(wèn)題。

解決方案: 我們可以用stl3.0版本下stl_list.h當(dāng)中的迭代器的聲明。也可以用release版本下,都是可以跑過(guò)的。

</>復(fù)制代碼

  1. typedef bidirectional_iterator_tag iterator_category;
  2. typedef T value_type;
  3. typedef Ptr pointer;
  4. typedef Ref reference;
  5. typedef ptrdiff_t difference_type;



總結(jié)

list的講解就到這里啦,看到這里不妨一鍵三連。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/124088.html

相關(guān)文章

  • 聊聊Java的泛型及實(shí)現(xiàn)

    摘要:靜態(tài)變量是被泛型類的所有實(shí)例所共享的。所以引用能完成泛型類型的檢查。對(duì)于這個(gè)類型系統(tǒng),有如下的一些規(guī)則相同類型參數(shù)的泛型類的關(guān)系取決于泛型類自身的繼承體系結(jié)構(gòu)。事實(shí)上,泛型類擴(kuò)展都不合法。 前言 和C++以模板來(lái)實(shí)現(xiàn)靜多態(tài)不同,Java基于運(yùn)行時(shí)支持選擇了泛型,兩者的實(shí)現(xiàn)原理大相庭徑。C++可以支持基本類型作為模板參數(shù),Java卻只能接受類作為泛型參數(shù);Java可以在泛型類的方法中取得...

    lewif 評(píng)論0 收藏0
  • C++IO流詳解

    摘要:在使用時(shí)候必須要包含頭文件并引入標(biāo)準(zhǔn)命名空間。在該頭文件下,標(biāo)準(zhǔn)庫(kù)三個(gè)類進(jìn)行流的輸入進(jìn)行流的輸出進(jìn)行流的輸入輸出將結(jié)構(gòu)體的內(nèi)容轉(zhuǎn)換成字符串字符串的內(nèi)容輸出到結(jié)構(gòu)體當(dāng)中注意實(shí)際是在其底層維護(hù)了一個(gè)類型的對(duì)象用來(lái)保存結(jié)果。 ...

    trilever 評(píng)論0 收藏0
  • [零基礎(chǔ)學(xué)python]大話題小函數(shù)(1)

    摘要:開(kāi)篇就要提到一個(gè)大的話題編程范型。例如,在面向?qū)ο缶幊讨校绦騿T認(rèn)為程序是一系列相互作用的對(duì)象,而在函數(shù)式編程中一個(gè)程序會(huì)被看作是一個(gè)無(wú)狀態(tài)的函數(shù)計(jì)算的串行。 開(kāi)篇就要提到一個(gè)大的話題:編程范型。什么是編程范型?引用維基百科中的解釋: 編程范型或編程范式(英語(yǔ):Programming paradigm),(范即模范之意,范式即模式、方法),是一類典型的編程風(fēng)格,是指從事軟件工程...

    xiguadada 評(píng)論0 收藏0
  • Python垃圾回收詳解

    摘要:而采用的是引用計(jì)數(shù)機(jī)制為主,標(biāo)記清理和分代收集兩種機(jī)制為輔的策略。現(xiàn)在我們先去考慮一下,什么情況下引用計(jì)數(shù),什么情況下,當(dāng)引用次數(shù)為時(shí),肯定就是需要進(jìn)行回收的時(shí)刻。引用計(jì)數(shù)機(jī)制缺點(diǎn)維護(hù)引用計(jì)數(shù)需要消耗一定的資源循環(huán)應(yīng)用時(shí),無(wú)法回收。 上一篇文章:私有化規(guī)則與屬性Property下一篇文章:Python進(jìn)程專題總覽篇 高級(jí)語(yǔ)言一般都有垃圾回收機(jī)制,其中c、c++使用的是用戶自己管維護(hù)內(nèi)...

    leo108 評(píng)論0 收藏0
  • 手把手寫(xiě)C++服務(wù)器(31):服務(wù)器性能提升關(guān)鍵——IO復(fù)用技術(shù)【兩萬(wàn)字長(zhǎng)文】

    摘要:前面幾講手撕了網(wǎng)關(guān)服務(wù)器回顯服務(wù)器服務(wù)的代碼,但是這幾個(gè)一次只能監(jiān)聽(tīng)一個(gè)文件描述符,因此性能非常原始低下。復(fù)用能使服務(wù)器同時(shí)監(jiān)聽(tīng)多個(gè)文件描述符,是服務(wù)器性能提升的關(guān)鍵。表示要操作的文件描述符,指定操作類型,指定事件。 ?本系列文章導(dǎo)航: 手把手寫(xiě)C++服務(wù)器(0):專欄文章-匯總導(dǎo)航【更...

    big_cat 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<