360-c++開發(fā)面經(jīng)（二）

關(guān)于vector簡單的說就是一個動態(tài)增長的數(shù)組，里面有一個指針指向一片連續(xù)的內(nèi)存空間，當(dāng)空間裝不下要容納的數(shù)據(jù)的時候會自動申請一片更大的空間（空間配置器）將原來的數(shù)據(jù)拷貝到新的空間，然后就會釋放舊的空間。當(dāng)刪除的時候空間并不會釋放只是清空了里面的數(shù)據(jù)。

vector的數(shù)據(jù)安排以及操作方式與數(shù)組非常相似，兩者唯一區(qū)別在于空間運用的靈活性，數(shù)組是靜態(tài)空間一旦配置了就不能再改變大小，如果要增容的話，就要把數(shù)據(jù)搬到新的數(shù)組里面，然后再把原來的空間釋放掉還給操作系統(tǒng)。vector是動態(tài)的隨著元素的增加，它的內(nèi)部機制會自動的擴充空間來容納新的元素。因此，vector的運用對于內(nèi)存的合理利用與運用的靈活性有很大的幫助，我們不必害怕空間不足而一開始就開辟一塊很大的內(nèi)存。

vector的實現(xiàn)技術(shù)，關(guān)鍵在于其對大小的控制以及重新配置時的數(shù)據(jù)移動效率。一旦vector的舊空間滿載了，如果客戶端每新增加一個元素，vector的內(nèi)部只是擴充了一個元素空間，其實這樣是比較不明智的。因為所謂的擴充空間（無論多大），過程都是配置新空間——數(shù)據(jù)移動——釋放舊空間，成本還是比較高的。vector維護的是一個連續(xù)的線性空間，所以vector支持隨機訪問。

在vector的動態(tài)增加大小的時候，并不是在原有的空間上持續(xù)增加成新的空間（無法保證原空間的后面還有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將原來的內(nèi)容拷貝過來，并釋放原來的空間。因此，對vector的任何操作一旦引起了空間的重新配置，指向原vector的所有迭代器會都失效了，這是比較容易犯的一個錯誤。

vector里的函數(shù)：

需要引入的頭文件不同

map: #include < map >

unordered_map: #include < unordered_map >

內(nèi)部實現(xiàn)機理不同

map：map內(nèi)部實現(xiàn)了一個紅黑樹（紅黑樹是非嚴(yán)格平衡二叉搜索樹，而AVL是嚴(yán)格平衡二叉搜索樹），紅黑樹具有自動排序的功能，因此map內(nèi)部的所有元素都是有序的，紅黑樹的每一個節(jié)點都代表著map的一個元素。因此，對于map進行的查找，刪除，添加等一系列的操作都相當(dāng)于是對紅黑樹進行的操作。map中的元素是按照二叉搜索樹（又名二叉查找樹、二叉排序樹，特點就是左子樹上所有節(jié)點的鍵值都小于根節(jié)點的鍵值，右子樹所有節(jié)點的鍵值都大于根節(jié)點的鍵值）存儲的，使用中序遍歷可將鍵值按照從小到大遍歷出來。

unordered_map: unordered_map內(nèi)部實現(xiàn)了一個哈希表（也叫散列表，通過把關(guān)鍵碼值映射到Hash表中一個位置來訪問記錄，查找的時間復(fù)雜度可達(dá)到O(1)，其在海量數(shù)據(jù)處理中有著廣泛應(yīng)用）。因此，其元素的排列順序是無序的。哈希表詳細(xì)介紹

優(yōu)缺點以及適用處

map：

優(yōu)點：

有序性，這是map結(jié)構(gòu)最大的優(yōu)點，其元素的有序性在很多應(yīng)用中都會簡化很多的操作

紅黑樹，內(nèi)部實現(xiàn)一個紅黑書使得map的很多操作在lgn的時間復(fù)雜度下就可以實現(xiàn)，因此效率非常的高

缺點：空間占用率高，因為map內(nèi)部實現(xiàn)了紅黑樹，雖然提高了運行效率，但是因為每一個節(jié)點都需要額外保存父節(jié)點、孩子節(jié)點和紅/黑性質(zhì)，使得每一個節(jié)點都占用大量的空間

適用處：對于那些有順序要求的問題，用map會更高效一些

unordered_map：

優(yōu)點：因為內(nèi)部實現(xiàn)了哈希表，因此其查找速度非常的快

缺點：哈希表的建立比較耗費時間

適用處：對于查找問題，unordered_map會更加高效一些，因此遇到查找問題，常會考慮一下用unordered_map

總結(jié)：

內(nèi)存占有率的問題就轉(zhuǎn)化成紅黑樹 VS hash表 , 還是unorder_map占用的內(nèi)存要高。

但是unordered_map執(zhí)行效率要比map高很多

對于unordered_map或unordered_set容器，其遍歷順序與創(chuàng)建該容器時輸入的順序不一定相同，因為遍歷是按照哈希表從前往后依次遍歷的

map和unordered_map的使用

unordered_map的用法和map是一樣的，提供了 insert，size，count等操作，并且里面的元素也是以pair類型來存貯的。其底層實現(xiàn)是完全不同的，上方已經(jīng)解釋了，但是就外部使用來說卻是一致的。

在C++中，動態(tài)內(nèi)存的管理是通過一對運算符來完成的：new，在動態(tài)內(nèi)存中為對象分配空間并返回一個指向該對象的指針，可以選擇對對象進行初始化；delete，接受一個動態(tài)對象的指針，銷毀該對象，并釋放與之關(guān)聯(lián)的內(nèi)存。

動態(tài)內(nèi)存的使用很容易出問題，因為確保在正確的時間釋放內(nèi)存是極其困難的。有時會忘記釋放內(nèi)存，在這種情況下會產(chǎn)生內(nèi)存泄露；有時在尚有指針引用內(nèi)存的情況下就釋放了它，在這種情況下就會產(chǎn)生引用非法內(nèi)存的指針。

為了更容易(同時也更安全)地使用動態(tài)內(nèi)存，C++11標(biāo)準(zhǔn)庫提供了兩種智能指針(smart pointer)類型來管理動態(tài)對象。智能指針的行為類似常規(guī)指針，重要的區(qū)別是它負(fù)責(zé)自動釋放所指的對象。C++11標(biāo)準(zhǔn)庫提供的這兩種智能指針的區(qū)別在于管理底層指針的方式：shared_ptr允許多個指針指向同一個對象；unique_ptr則"獨占"所指向的對象。C++11標(biāo)準(zhǔn)庫還定義了一個名為weak_ptr的輔助類，它是一種弱引用，指向shared_ptr所管理的對象。這三種類型都定義在memory頭文件中。智能指針是模板類而不是指針。類似vector，智能指針也是模板，當(dāng)創(chuàng)建一個智能指針時，必須提供額外的信息即指針可以指向的類型。默認(rèn)初始化的智能指針中保存著一個空指針。智能指針的使用方式與普通指針類似。解引用一個智能指針返回它指向的對象。如果在一個條件判斷中使用智能指針，效果就是檢測它是否為空。

智能指針實質(zhì)就是重載了->和*操作符的類，由類來實現(xiàn)對內(nèi)存的管理，確保即使有異常產(chǎn)生，也可以通過智能指針類的析構(gòu)函數(shù)完成內(nèi)存的釋放。

shared_ptr的類型轉(zhuǎn)換不能使用一般的static_cast，這種方式進行的轉(zhuǎn)換會導(dǎo)致轉(zhuǎn)換后的指針無法再被shared_ptr對象正確的管理。應(yīng)該使用專門用于shared_ptr類型轉(zhuǎn)換的 static_pointer_cast<T>() , const_pointer_cast<T>() 和dynamic_pointer_cast<T>()。

使用shared_ptr避免了手動使用delete來釋放由new申請的資源，標(biāo)準(zhǔn)庫也引入了make_shared函數(shù)來創(chuàng)建一個shared_ptr對象，使用shared_ptr和make_shared，你的代碼里就可以使new和delete消失，同時又不必?fù)?dān)心內(nèi)存的泄露。shared_ptr是一個模板類。

C++開發(fā)處理內(nèi)存泄漏最有效的辦法就是使用智能指針，使用智能指針就不會擔(dān)心內(nèi)存泄露的問題了，因為智能指針可以自動刪除分配的內(nèi)存。

智能指針是指向動態(tài)分配(堆)對象指針，用于生存期控制，能夠確保自動正確的銷毀動態(tài)分配的對象，防止內(nèi)存泄露。它的一種通用實現(xiàn)技術(shù)是使用引用計數(shù)。每次使用它，內(nèi)部的引用計數(shù)加1，每次析構(gòu)一次，內(nèi)部引用計數(shù)減1，減為0時，刪除所指向的堆內(nèi)存。

每一個shared_ptr的拷貝都指向相同的內(nèi)存。在最后一個shared_ptr析構(gòu)的時候, 內(nèi)存才會被釋放。

可以通過構(gòu)造函數(shù)、賦值函數(shù)或者make_shared函數(shù)初始化智能指針。

shared_ptr基于”引用計數(shù)”模型實現(xiàn)，多個shared_ptr可指向同一個動態(tài)對象，并維護一個共享的引用計數(shù)器，記錄了引用同一對象的shared_ptr實例的數(shù)量。當(dāng)最后一個指向動態(tài)對象的shared_ptr銷毀時，會自動銷毀其所指對象(通過delete操作符)。

shared_ptr的默認(rèn)能力是管理動態(tài)內(nèi)存，但支持自定義的Deleter以實現(xiàn)個性化的資源釋放動作。

最安全的分配和使用動態(tài)內(nèi)存的方法是調(diào)用一個名為make_shared的標(biāo)準(zhǔn)庫函數(shù)。此函數(shù)在動態(tài)內(nèi)存中分配一個對象并初始化它，返回指向此對象的shared_ptr。當(dāng)要用make_shared時，必須指定想要創(chuàng)建的對象的類型，定義方式與模板類相同。在函數(shù)名之后跟一個尖括號，在其中給出類型。例如，調(diào)用make_shared<string>時傳遞的參數(shù)必須與string的某個構(gòu)造函數(shù)相匹配。如果不傳遞任何參數(shù)，對象就會進行值初始化。

通常用auto定義一個對象來保存make_shared的結(jié)果。

當(dāng)進行拷貝或賦值操作時，每個shared_ptr都會記錄有多少個其它shared_ptr指向相同的對象。

可以認(rèn)為每個shared_ptr都有一個關(guān)聯(lián)的計數(shù)器，通常稱其為引用計數(shù)(reference count)。無論何時拷貝一個shared_ptr，計數(shù)器都會遞增。例如，當(dāng)用一個shared_ptr初始化另一個shared_ptr，或?qū)⑺鳛閰?shù)傳遞給一個函數(shù)以及作為函數(shù)的返回值時，它所關(guān)聯(lián)的計數(shù)器就會遞增。當(dāng)給shared_ptr賦予一個新值或是shared_ptr被銷毀(例如一個局部的shared_ptr離開其作用域)時，計數(shù)器就會遞減。一旦一個shared_ptr的計數(shù)器變?yōu)?，它就會自動釋放自己所管理的對象。

當(dāng)指向一個對象的最后一個shared_ptr被銷毀時，shared_ptr類會自動銷毀此對象。它是通過另一個特殊的成員函數(shù)析構(gòu)函數(shù)(destructor)來完成銷毀工作的。類似于構(gòu)造函數(shù)，每個類都有一個析構(gòu)函數(shù)。就像構(gòu)造函數(shù)控制初始化一樣，析構(gòu)函數(shù)控制此類型的對象銷毀時做什么操作。shared_ptr的析構(gòu)函數(shù)會遞減它所指向的對象的引用計數(shù)。如果引用計數(shù)變?yōu)?，shared_ptr的析構(gòu)函數(shù)就會銷毀對象，并釋放它占用的內(nèi)存。

如果將shared_ptr存放于一個容器中，而后不再需要全部元素，而只使用其中一部分，要記得用erase刪除不再需要的那些元素。

使用shared_ptr注意事項：

(1)、不要把一個原生指針給多個shared_ptr管理；

(2)、不要把this指針給shared_ptr；

(3)、不要在函數(shù)實參里創(chuàng)建shared_ptr；

(4)、不要不加思考地把指針替換為shared_ptr來防止內(nèi)存泄漏，shared_ptr并不是萬能的，而且使用它們的話也是需要一定的開銷的；

(5)、環(huán)狀的鏈?zhǔn)浇Y(jié)構(gòu)shared_ptr將會導(dǎo)致內(nèi)存泄漏(可以結(jié)合weak_ptr來解決)；

(6)、共享擁有權(quán)的對象一般比限定作用域的對象生存更久，從而將導(dǎo)致更高的平均資源使用時間；

(7)、在多線程環(huán)境中使用共享指針的代價非常大，這是因為你需要避免關(guān)于引用計數(shù)的數(shù)據(jù)競爭；

(8)、共享對象的析構(gòu)器不會在預(yù)期的時間執(zhí)行；

(9)、不使用相同的內(nèi)置指針值初始化(或reset)多個智能指針；

(10)、不delete get()返回的指針；

(11)、不使用get()初始化或reset另一個智能指針；

(12)、如果使用get()返回的指針，記住當(dāng)最后一個對應(yīng)的智能指針銷毀后，你的指針就變?yōu)闊o效了；

(13)、如果你使用智能指針管理的資源不是new分配的內(nèi)存，記住傳遞給它一個刪除器。