C++ 寫時拷貝 2

什么情況下會用到c++中的拷貝構造函數】：

?1）用已經存在的同類的對象去構造出另一個新的對象

? 2）當函數的形參是類的對象時，這時調用此函數，使用的是值的拷貝，也會調用拷貝構造函數
? 3）當函數的返回值是類的對象時，這時當函數調用完后，會將函數的對象拷貝構造出一個臨時的對象并傳給函數的返回處

【淺拷貝】：(位拷貝（值拷貝）)

1、概念：所謂的淺拷貝就是當在進行對象的復制時，只是進行對象的數據成員的拷貝，其中默認的拷貝構造函數也是淺拷貝。大多數情況下，使用淺拷貝是沒有問題的，但是當出現動態成員，就會出現問題。

2、關于淺拷貝的使用舉例:

[plain]?view plain?copy
  1. #include<iostream>??
  2. using?namespace?std;??
  3. class?Test??
  4. {??
  5. public:??
  6. ????//構造函數??
  7. ????Test(int?a)??
  8. ????????:_a(a)??
  9. ????{}??
  10. ????//拷貝構造函數??
  11. ????Test(const?Test&?x)??
  12. ????{??
  13. ????????_a?=?x._a;??
  14. ????}??
  15. ??
  16. private:??
  17. ????int?_a;??
  18. };??
  19. int?main()??
  20. {??
  21. ????Test?b(10);??
  22. ????Test?c(b);??
  23. ????return?0;??
  24. }??

3、淺拷貝的缺陷：

? ? ? 淺拷貝對于指針成員不可行。多個對象共用同一塊空間，同一內存地址，但是在調用析構函數釋放空間的時候，多次調用析構函數，這塊空間被釋放了多次，此時程序就會崩潰。

【引用計數的拷貝】：

1、（怎么引入的）概念：因為淺拷貝的缺陷，所以在這個時候我們就引入了引用計數的拷貝。

? ? ?【說明】：引用計數的拷貝是用來解決淺拷貝存在的問題的，所以它也是一種淺拷貝

2、如何實現：我們為每個內存的字符數組添加一個引用計數pcount,即就是在構造函數申請空間的時候多申請出來4個字節。表示有多少個對象使用這塊內存，有多少個對象使用，就讓pcount值加1，當對象被析構的時候，讓pcount值減1，當pcount值為0的時候，將這塊內存釋放掉。當然pcount也要實現內存共享，所以它也是一個堆中的數據，每個對象都有一個指向它的指針。

3、【說明】：但在此時,pcount的類型的選取，就會要有所考慮？

? ? 1）如果選取int類型：（不采取）

[cpp]?view plain?copy
  1. #include<iostream>??
  2. using?namespace?std;??
  3. class?String??
  4. {??
  5. public:??
  6. ????//構造函數??
  7. ????String(const?char*?ptr?=?"")??
  8. ????{??
  9. ????????if(ptr?==?NULL)??
  10. ????????{??
  11. ????????????_ptr?=?new?char[1];??
  12. ????????????_pcount?=?1;??
  13. ????????????*_ptr?=?'\0';??
  14. ????????}??
  15. ????????else??
  16. ????????{??
  17. ????????????_pcount?=?1;??
  18. ????????????_ptr?=?new?char[strlen(ptr)+1];??
  19. ????????????strcpy(_ptr,ptr);??
  20. ????????}??
  21. ????}??
  22. ????//拷貝構造函數??
  23. ????String(String&?s)??
  24. ????????:_ptr(s._ptr)??
  25. ????????,_pcount(s._pcount)??
  26. ????{??
  27. ????????_pcount++;??
  28. ????}??
  29. ????//賦值運算符重載??
  30. ????String&?operator=(const?String&?s)??
  31. ????{??
  32. ????????if(this?!=?&s)??
  33. ????????{??
  34. ????????????if(--_pcount?==?0)??
  35. ????????????{??
  36. ????????????????delete[]?_ptr;??
  37. ????????????????//delete?_pcount;??
  38. ????????????}??
  39. ????????????else??
  40. ????????????{??
  41. ????????????????_ptr?=?s._ptr;??
  42. ????????????????_pcount?=?s._pcount;??
  43. ????????????????(_pcount)++;??
  44. ????????????}??
  45. ????????}??
  46. ????????return?*this;??
  47. ????}??
  48. ????//析構函數??
  49. ????~String()??
  50. ????{??
  51. ????????if((0?==?--_pcount)?&&?_ptr!=?NULL)??
  52. ????????{??
  53. ????????????delete[]_ptr;??
  54. ????????????//delete?_pcount;??
  55. ????????????_ptr?=?NULL;??
  56. ????????}??
  57. ??????????
  58. ????}??
  59. ????//重載[]??
  60. ????char&?operator[](size_t?size)??
  61. ????{??
  62. ????????if(--_pcount?>1)??
  63. ????????{??
  64. ????????????char*?ptemp?=?new?char[strlen(_ptr)+1];??
  65. ????????????int?pcount?=?1;??
  66. ????????????strcpy(ptemp,_ptr);??
  67. ????????????_pcount--;??
  68. ????????????_ptr?=?ptemp;??
  69. ????????????_pcount?=?pcount;???
  70. ????????}??
  71. ????????return?_ptr[size];??
  72. ????}??
  73. private:??
  74. ????char*_ptr;??
  75. ????int?_pcount;??
  76. };??
  77. ??
  78. void?FunTest()??
  79. {??
  80. ????String?s1("hello");??
  81. ????String?s2(s1);??
  82. ????String?s3(s2);??
  83. ????s3?=?s2;??
  84. }??
  85. int?main()??
  86. {??
  87. ????FunTest();??
  88. ????return?0;??
  89. }??
調試：



（注意這里我將斷點就走到s2，意在說明問題）：本來增加s2的時候，兩個對象的計數應該是一樣的，但是現在一個是1，一個是2，不同步，我們了解到這兩個對象的計數變量的地址是不一樣的。說明此pcount是公共的，可以被多個對象同時訪問。

? ? 2）如果選取的是static類型的：（不采取） ?

[cpp]?view plain?copy
  1. #include<iostream>??
  2. using?namespace?std;??
  3. class?String??
  4. {??
  5. public:??
  6. ????//構造函數??
  7. ????String(const?char*?ptr?=?"")??
  8. ????{??
  9. ????????if(ptr?==?NULL)??
  10. ????????{??
  11. ????????????_ptr?=?new?char[1];??
  12. ????????????_pcount?=?1;??
  13. ????????????*_ptr?=?'\0';??
  14. ????????}??
  15. ????????else??
  16. ????????{??
  17. ????????????_pcount?=?1;??
  18. ????????????_ptr?=?new?char[strlen(ptr)+1];??
  19. ????????????strcpy(_ptr,ptr);??
  20. ????????}??
  21. ????}??
  22. ????//拷貝構造函數??
  23. ????String(String&?s)??
  24. ????????:_ptr(s._ptr)??
  25. ????{??
  26. ????????_pcount++;??//因為是靜態的，所以直接進行計數的增值就可以了??
  27. ????}??
  28. ????//賦值運算符重載??
  29. ????String&?operator=(const?String&?s)??
  30. ????{??
  31. ????????if(this?!=?&s)??
  32. ????????{??
  33. ????????????if(--_pcount?==?0)??
  34. ????????????{??
  35. ????????????????delete[]?_ptr;??
  36. ????????????????//delete?_pcount;??
  37. ????????????}??
  38. ????????????else??
  39. ????????????{??
  40. ????????????????_ptr?=?s._ptr;??
  41. ????????????????_pcount?=?s._pcount;??
  42. ????????????????(_pcount)++;??
  43. ????????????}??
  44. ????????}??
  45. ????????return?*this;??
  46. ????}??
  47. ????//析構函數??
  48. ????~String()??
  49. ????{??
  50. ????????if((0?==?--_pcount)?&&?_ptr!=?NULL)??
  51. ????????{??
  52. ????????????delete[]_ptr;??
  53. ????????????//delete?_pcount;??
  54. ????????????_ptr?=?NULL;??
  55. ????????}??
  56. ??????????
  57. ????}??
  58. ????//重載[]??
  59. ????char&?operator[](size_t?size)??
  60. ????{??
  61. ????????if(--_pcount?>1)??
  62. ????????{??
  63. ????????????char*?ptemp?=?new?char[strlen(_ptr)+1];??
  64. ????????????int?pcount?=?1;??
  65. ????????????strcpy(ptemp,_ptr);??
  66. ????????????_pcount--;??
  67. ????????????_ptr?=?ptemp;??
  68. ????????????_pcount?=?pcount;???
  69. ????????}??
  70. ????????return?_ptr[size];??
  71. ????}??
  72. private:??
  73. ????char*_ptr;??
  74. ????static?int?_pcount;??
  75. };??
  76. int?String::_pcount?=?0;??
  77. void?FunTest()??
  78. {??
  79. ????String?s1("hello");??
  80. ????String?s2(s1);??
  81. ????String?s3(s2);??
  82. ????s3?=?s2;??
  83. ????String?s4("world");??
  84. ????String?s5(s4);??
  85. }??
  86. int?main()??
  87. {??
  88. ????FunTest();??
  89. ????return?0;??
  90. }??
調試：

? 先走到s3，然后走到s4，用s4來構造s5,結果就不對了，走到s4的時候，計數器又變成了1，說明這5個對象公用一個pcount，不能實現引用計數

? ? 3）那么我們這樣想：如果一個對象第一次開辟空間存放字符串再開辟一塊新的空間存放新的額引用計數，當它拷貝構造其它對象時讓其它對象的引用計數都指向存放引用計數的同一塊空間，pcount設置成int*就可以啦，但是這種方式有缺陷。（讀者可以自己實現下）

? ? ? ?缺陷一：每次new兩塊空間，創建多個對象的時候效率比較低

? ? ? ?缺陷二：它多次分配小塊空間，容易造成內存碎片化，導致分配不出來大塊內存

4、代碼實現：（所以我將優化版的代碼貼出來，其實就是仿照new的底層實現，開辟一塊空間，但是它的頭幾個字節用于計數）

[cpp]?view plain?copy
  1. <span?style="font-size:18px;">#include<iostream>??
  2. using?namespace?std;??
  3. class?String??
  4. {??
  5. public:??
  6. ????String(char?*ptr?=?"")??
  7. ????{??
  8. ????????if(ptr?==?NULL)??
  9. ????????{??
  10. ????????????_ptr?=?new?char[strlen(ptr)+5];??
  11. ????????????_ptr?=?new?char[5];??
  12. ????????????*(_ptr+4)?=?'\0';??
  13. ????????}??
  14. ????????else??
  15. ????????{??
  16. ????????????_ptr?=?new?char[strlen(ptr)+5];??
  17. ????????????*((int*)_ptr)?=?1;??
  18. ????????????_ptr?+=?4;??
  19. ????????????strcpy(_ptr,ptr);??
  20. ????????}??
  21. ????}??
  22. ????String(const?String&?s)??
  23. ????????:_ptr(s._ptr)??
  24. ????{??
  25. ????????(*((int*)(_ptr-4)))++;??
  26. ????}??
  27. ????String&?operator=(const?String&?s)??
  28. ????{??
  29. ????????if(this?!=?&s)??
  30. ????????{??
  31. ????????????if(--(*((int*)(_ptr-4)))?==?0)??
  32. ????????????{??
  33. ????????????????delete[]_ptr;??
  34. ????????????}??
  35. ????????????else??
  36. ????????????{??
  37. ????????????????_ptr?=?s._ptr;??
  38. ????????????????++(*(int*)(_ptr-4));??
  39. ????????????}??
  40. ????????}??
  41. ????????return?*this;??
  42. ????}??
  43. ????~String()??
  44. ????{??
  45. ????????if((_ptr?!=?NULL)?&&?((--(*((int*)(_ptr-4))))?==?0))??
  46. ????????{??
  47. ????????????delete[]_ptr;??
  48. ????????????_ptr?=?NULL;??
  49. ????????}??
  50. ????}??
  51. private:??
  52. ????char*?_ptr;??
  53. };??
  54. void?Funtest()??
  55. {??
  56. ????String?s1("hello");??
  57. ????String?s2(s1);??
  58. ????String?s3(s2);???
  59. ????s3?=?s2;??
  60. }??
  61. int?main()??
  62. {??
  63. ????Funtest();??
  64. ????return?0;??
  65. }</span>??

【深拷貝】：（址拷貝）

1、概念：采取在堆中申請新的空間來存取數據，這樣數據之間相互獨立。址拷貝。

2、舉例：（string類中的拷貝構造函數）

[cpp]?view plain?copy
  1. <span?style="font-size:18px;">String(const?String&?s)??
  2. ????{??
  3. ????????_ptr?=?new?char[strlen(s._ptr)+1];??
  4. ????????strcpy(_ptr,s._ptr);??
  5. ????}</span>??

【寫時拷貝】：

1、（如何引入的）概念：但是當其中一個對象改變它的值時，其他對象的值就會隨之改變，所以此時我們采取這樣一種做法，就是寫時拷貝。

2、核心思想：

（寫入時拷貝）如果有多個調用者同時要求相同資源（如內存或磁盤上的數據存儲），它們會共同獲取相同的指針指向的資源，直到某個調用者試圖修改資源的內容時，系統才會真正復制一份專用副本給該調用者，而其他調用者所見到的最初的資源仍然保持不變。這過程中對其他調用者都是透明的。做法的優點：如果調用者沒有修改該資源，就不會有副本被創建，因此多個調用者只是讀取操作時可以共享同一份資源

（寫時拷貝）指用淺拷貝的方法拷貝其他對象，多個指針指向同一塊空間，只有當對其中一個對象修改時，才會開辟一個新的空間給這個對象，和它原來指向同一空間的對象不會收到影響。

3、做法：給要改變值的那個對象重新new出一塊內存，然后先把之前的引用的字符數據復制到新的字符數組中，這就是寫時拷貝。注意，同時還要把之前指向的內存的引用計數減1（因為它指向了新的堆中的字符數組），并在堆中重新new一個塊內存，用于保存新的引用計數，同時把新的字符數組的引用計數置為1。因為此時只有一個對象（就是改變值的對象）在使用這個內存。

4、代碼實現：

[cpp]?view plain?copy
  1. <span?style="font-size:18px;">#include<iostream>??
  2. using?namespace?std;??
  3. class?String??
  4. {??
  5. public:??
  6. ????//構造函數??
  7. ????String(const?char*?ptr?=?"")??
  8. ????{??
  9. ????????if(ptr?==?NULL)??
  10. ????????{??
  11. ????????????_ptr?=?new?char[1];??
  12. ????????????_pcount?=?new?int(1);??
  13. ????????????*_ptr?=?'\0';??
  14. ????????}??
  15. ????????else??
  16. ????????{??
  17. ????????????_pcount?=?new?int(1);??
  18. ????????????_ptr?=?new?char[strlen(ptr)+1];??
  19. ????????????strcpy(_ptr,ptr);??
  20. ????????}??
  21. ????}??
  22. ????//拷貝構造函數??
  23. ????String(String&?s)??
  24. ????????:_ptr(s._ptr)??
  25. ????????,_pcount(s._pcount)??
  26. ????{??
  27. ????????(*_pcount)++;??
  28. ????}??
  29. ????//賦值運算符重載??
  30. ????String&?operator=(const?String&?s)??
  31. ????{??
  32. ????????if(this?!=?&s)??
  33. ????????{??
  34. ????????????if(--(*_pcount)?==?0)??
  35. ????????????{??
  36. ????????????????delete[]?_ptr;??
  37. ????????????????delete?_pcount;??
  38. ????????????}??
  39. ????????????else??
  40. ????????????{??
  41. ????????????????_ptr?=?s._ptr;??
  42. ????????????????_pcount?=?s._pcount;??
  43. ????????????????(*_pcount)++;??
  44. ????????????}??
  45. ????????}??
  46. ????????return?*this;??
  47. ????}??
  48. ????//析構函數??
  49. ????~String()??
  50. ????{??
  51. ????????if(0?==?--(*_pcount)?&&?_ptr!=?NULL)??
  52. ????????{??
  53. ????????????delete[]_ptr;??
  54. ????????????delete?_pcount;??
  55. ????????????_ptr?=?NULL;??
  56. ????????}??
  57. ??????????
  58. ????}??
  59. ????//重載[]??
  60. ????char&?operator[](size_t?size)??
  61. ????{??
  62. ????????if(--(*_pcount)?>1)??
  63. ????????{??
  64. ????????????char*?ptemp?=?new?char[strlen(_ptr)+1];??
  65. ????????????int*?pcount?=?new?int(1);??
  66. ????????????strcpy(ptemp,_ptr);??
  67. ????????????(*_pcount)--;??
  68. ????????????_ptr?=?ptemp;??
  69. ????????????_pcount?=?pcount;???
  70. ????????}??
  71. ????????return?_ptr[size];??
  72. ????}??
  73. private:??
  74. ????char*_ptr;??
  75. ????int*?_pcount;??
  76. };??
  77. ??
  78. void?FunTest()??
  79. {??
  80. ????String?s1("hello");??
  81. ????String?s2(s1);??
  82. ????String?s3(s2);??
  83. ????s3?=?s2;??
  84. ????String?s4(s1);??
  85. ????s1[0]?=?'y';??
  86. }??
  87. int?main()??
  88. {??
  89. ????FunTest();??
  90. ????return?0;??
  91. }</span>??

經調試，結果如下：


【注意】：因為不止一個對象使用這一塊內存，當修改自己的時，也等于修改了他人的。在向這塊存儲單元寫之前，應該確信沒有其他人使用它。如果引用計數大于1，在寫之前必須拷貝這塊存儲單元，這樣就不會影響他人了。


本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383780.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383780.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383780.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【Java學習筆記十一】圖形用戶界面

【Java學習筆記十一】圖形用戶界面

圖形用戶界面或圖形用戶接口(Graphical User Interface&#xff0c;GUI)是指采用圖形方式,借助菜單、按鈕等標準界面元素&#xff0c;用戶可以通過鼠標等外設向計算機系統發出指令、啟動操作&#xff0c;并將系統運行的結果同樣以圖形方式顯示給用戶的技術。 GUI是事件驅動的&…
閱讀更多...
C++ 寫時拷貝 3

C++ 寫時拷貝 3

http://blog.csdn.net/ljianhui/article/details/22895505 字符串一種在程序中經常要使用到的數據結構&#xff0c;然而在C中卻沒有字符串這種類型。在C中&#xff0c;為了方便字符串的使用&#xff0c;在STL中提供了一個string類。該類維護一個char指針&#xff0c;并封裝和提…
閱讀更多...
C++類模板實例化條件

C++類模板實例化條件

&#xff08;我不想了解這個&#xff0c;可是考試要考。。。。 并不是每次使用模板類都會實例化一個類 聲明一個類模板的指針和引用不會引起類模板的實例化如果檢查這個指針或引用的成員時時&#xff0c;類模板會實例化定義一個對象的時候需要有類的定義&#xff0c;會實例化…
閱讀更多...
C++ String類寫時拷貝 4

C++ String類寫時拷貝 4

http://blog.51cto.com/zgw285763054/1839752 維基百科&#xff1a; 寫入時復制&#xff08;英語&#xff1a;Copy-on-write&#xff0c;簡稱COW&#xff09;是一種計算機程序設計領域的優化策略。其核心思想是&#xff0c;如果有多個調用者&#xff08;callers&#xff09;同時…
閱讀更多...
C++筆試復習

C++筆試復習

基礎知識點 C中對象數組在定義的時候全部進行實例化&#xff08;與Java不同&#xff0c;Java相當于只是定義了一個指針數組&#xff0c;沒有進行實例化&#xff09; 程序的三種基本控制結構是&#xff1a;順序結構、循環結構、選擇結構 一個C程序開發步驟通常包括&#xff1a…
閱讀更多...
C++函數默認參數

C++函數默認參數

聲明是用戶可以看到的部分&#xff0c;客戶非常信任地使用這個特性&#xff0c;希望得到一定的結果&#xff0c;但是你在實現里使用了不同的缺省值&#xff0c;那么將是災難性的。因此編譯器禁止聲明和定義時同時定義缺省參數值。 類的成員函數的參數表在聲明時默認參數位于參…
閱讀更多...
C語言鏈表各類操作詳解

C語言鏈表各類操作詳解

http://blog.csdn.net/pf4919501/article/details/38818335鏈表概述　　 鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表有一個“頭指針”變量&#xff0c;以head表示&#xff0c;它存放一個地址。該地址指向一個元素。…
閱讀更多...
Java筆試復習

Java筆試復習

Java程序運行 Java程序的執行必須經過編輯、編譯和運行三個步驟 編輯指編寫代碼&#xff0c;最終形成后綴名為.java的Java源文件編譯指使用Java編譯器&#xff08;javac指令&#xff09;將源文件翻譯為二進制代碼&#xff0c;編譯后生成后綴名為.class的字節碼文件&#xff0c…
閱讀更多...
數據結構之自建算法庫——鏈棧

數據結構之自建算法庫——鏈棧

http://blog.csdn.net/sxhelijian/article/details/48463801本文針對數據結構基礎系列網絡課程(3)&#xff1a;棧和隊列中第4課時棧的鏈式存儲結構及其基本運算實現。 按照“0207將算法變程序”[視頻]部分建議的方法&#xff0c;建設自己的專業基礎設施算法庫。 鏈棧算法庫采用…
閱讀更多...
Java類名與包名不區分大小寫

Java類名與包名不區分大小寫

剛才寫了一個簡單的Java程序&#xff0c;經過測試得到一個令人震驚的結論&#xff1a;Java類名和包名是不區分大小寫的 可以看一下這個例子&#xff1a; package Test;class aBcdEfG {}class AbCdefg {}public class TTT {public static void main(String[] args){AbCdefg tm…
閱讀更多...
epoll實現高并發聊天室

epoll實現高并發聊天室

http://blog.csdn.net/qq_31564375/article/details/51581038項目介紹 本項目是實現一個簡單的聊天室&#xff0c;聊天室分為服務端和客戶端。本項目將很多復雜的功能都去掉了&#xff0c;線程池、多線程編程、超時重傳、確認收包等等都不會涉及。總共300多行代碼&#xff0c;讓…
閱讀更多...
BZOJ2809-左偏樹合并

BZOJ2809-左偏樹合并

Description 在一個忍者的幫派里&#xff0c;一些忍者們被選中派遣給顧客&#xff0c;然后依據自己的工作獲取報償。在這個幫派里&#xff0c;有一名忍者被稱之為 Master。除了 Master以外&#xff0c;每名忍者都有且僅有一個上級。為保密&#xff0c;同時增強忍者們的領導力&a…
閱讀更多...
處理大并發之一 對epoll的理解，epoll客戶端服務端代碼

處理大并發之一 對epoll的理解，epoll客戶端服務端代碼

http://blog.csdn.net/zhuxiaoping54532/article/details/56494313處理大并發之一對epoll的理解&#xff0c;epoll客戶端服務端代碼序言&#xff1a;該博客是一系列的博客&#xff0c;首先從最基礎的epoll說起&#xff0c;然后研究libevent源碼及使用方法&#xff0c;最后研究n…
閱讀更多...
epoll詳解

epoll詳解

http://blog.csdn.net/majianfei1023/article/details/45772269歡迎轉載&#xff0c;轉載請注明原文地址&#xff1a;http://blog.csdn.net/majianfei1023/article/details/45772269一.基本概念&#xff1a;1.epoll是什么&#xff1a;epoll是Linux內核為處理大批量文件描述符而…
閱讀更多...
數據分割-并查集+set

數據分割-并查集+set

小w來到百度之星的賽場上&#xff0c;準備開始實現一個程序自動分析系統。 這個程序接受一些形如xixj 或 xi≠xj 的相等/不等約束條件作為輸入&#xff0c;判定是否可以通過給每個 w 賦適當的值&#xff0c;來滿足這些條件。 輸入包含多組數據。 然而粗心的小w不幸地把每組數據…
閱讀更多...
linux c++線程池的實現

linux c++線程池的實現

http://blog.csdn.net/zhoubl668/article/details/8927090?t1473221020107 線程池的原理大家都知道&#xff0c;直接上代碼了^_^ Thread.h [cpp] view plaincopy #ifndef __THREAD_H #define __THREAD_H #include <vector> #include <string> #inc…
閱讀更多...
樹啟發式合并入門

樹啟發式合并入門

所謂啟發式合并&#xff0c;就是一種符合直覺的合并方法&#xff1a;將小的子樹合并在大的子樹上。 這些問題一般是相似的問題背景&#xff1a;都是樹上的計數問題&#xff0c;都不能直接從上往下進行暴力&#xff0c;都需要從下往上計數時對子樹信息進行運算從而得到父親節點的…
閱讀更多...
鏈棧基本操作

鏈棧基本操作

http://blog.csdn.net/jwentao01/article/details/46765517###;棧基本概念&#xff1a; 棧&#xff08;stack&#xff09;是限定在表尾進行插入和刪除操作的線性表&#xff08;或單鏈表&#xff09;。 //只能在一段進行插入和刪除&#xff0c;因此不存在&#xff0c;在中間進行…
閱讀更多...
Linux網絡編程---I/O復用模型之select

Linux網絡編程---I/O復用模型之select

https://blog.csdn.net/men_wen/article/details/53456435Linux網絡編程—I/O復用模型之select 1. IO復用模型 IO復用能夠預先告知內核&#xff0c;一旦發現進程指定的一個或者多個IO條件就緒&#xff0c;它就通知進程。IO復用阻塞在select或poll系統調用上&#xff0c;而不是阻…
閱讀更多...
UVa12633-Super Rooks on Chessboard-容斥+FFT

UVa12633-Super Rooks on Chessboard-容斥+FFT

題目大意就是給你一個R*C的棋盤&#xff0c;上面有超級兵&#xff0c;這種超級兵會攻擊 同一行、同一列、同一主對角線的所有元素&#xff0c;現在給你N個超級兵的坐標&#xff0c;需要你求出有多少方塊是不能被攻擊到的(R,C,N<50000) 遇到這種計數問題就要聯想到容斥&#…
閱讀更多...
最新文章

Copyright @ 2022~2023