第二部分：C++標準庫

1.為了支持不同種類的IO處理操作，標準庫定義了以下類型的IO，分別定義在三個獨立的文件中：iostream文件中定義了用于讀寫流的基本類型；fstream文件中定義了讀寫命名文件的類型；sstream文件中定義了讀寫內存string對象的類型。

其中寬字符版本（wchar_t類型）的類型和函數的名字以一個w開始（P278）。類型ifstream和istringstream都繼承自istream，通過繼承機制，可以像使用istream對象一樣來使用ifstream和istringstream對象，例如不僅可以對一個istream對象調用getline和>>，也可以對一個ifstream或istringstream對象調用getline和>>。

2.IO對象無法進行拷貝或賦值，因此不能將形參或返回類型設置為流類型，進行IO操作的函數通常以引用方式傳遞和返回流，讀寫一個IO對象會改變其狀態，因此傳遞和返回的引用不能是const的（P279）。流的各種狀態如下圖所示：

一個流一旦發生錯誤，其后續的IO操作都會失敗，只有當一個流處于無錯狀態時，才可以從它讀取數據或向它寫入數據。當流的狀態位eofbit、failbit或badbit中的任何一個都沒有被置位時，cin被視為真，表示輸入流處于正常狀態，可以繼續讀取數據（此時if(cin)的判斷即為真，反之為假）。

3.每個輸出流都管理一個緩沖區，用來保存程序讀寫的數據，導致緩沖區刷新的原因有：

• 程序正常結束，作為main函數的return操作的一部分，緩沖刷新被執行
• 緩沖區滿時，需要刷新緩沖，刷新后新的數據才能繼續寫入緩沖區
• 可以使用操縱符如endl（會輸出一個換行，然后刷新緩沖區）、flush（如cout<<”hi”<<flush，輸出hi然后刷新緩沖區，但不輸出任何額外字符）、ends（會輸出一個空字符，然后刷新緩沖區）來顯式刷新緩沖區（P282）
• 在每個輸出操作之后，可以用操縱符unitbuf設置流的內部狀態（cout<<unitbuf，則所有輸出操作之后都會立即刷新緩沖區），來清空緩沖區。默認情況下，對cerr是設置unitbuf的，因此寫到cerr的內容都是立即刷新的
• 一個輸出流可能被關聯到另一個流。在這種情況下，當讀寫被關聯的流時，關聯到的流的緩沖區會被刷新。例如，默認情況下，cin和cerr都關聯到cout。因此，讀cin或寫cerr都會導致cout的緩沖區被刷新。流中的tie方法可以用來設置流的關聯性，具體見P283

4.文件IO相關的fstream相關的操作如下圖，這里的fstream可以是ifstream、ofstream或fstream：

每個文件流都定義了一個名為open的成員函數，創建文件流對象時可以提供文件名（可選的），如果提供了文件名則open會被自動調用，如ifstream in(infile)，如果定義了一個空文件流對象，可以隨后調用open來將它與文件關聯起來，如ofstream out; out.open(“filename”);，當一個fstream對象離開其作用域時，與之關聯的文件會自動close。每個流都有一個關聯的文件模式（如in表示以讀方式打開，out表示以寫方式打開，具體見P286），在每次打開文件時，都要設置文件模式，當未顯示指定模式時，使用默認值。

5.內存IO相關的sstream相關的操作如下圖，這里的sstream可以是istringstream、ostringstream或stringstream：

string流的具體使用方式見P288。

6.C++標準庫中提供的順序容器如下圖：

選擇所使用容器的原則見P293，通常使用vector是最好的選擇，除非有很好的理由選擇其他容器，array比內置數組更安全、更容易使用，在使用數組時盡量使用array。

7.容器均定義為模版類，順序容器幾乎可以保存任意類型的元素，可以定義一個容器，其元素的類型是另外一個容器。容器的通用操作如下圖所示：

反向迭代器就是一種反向遍歷容器的迭代器，與正向迭代器相比，各種操作的含義都發生了顛倒，如對反向迭代器執行++操作，會得到上一個元素。

8.迭代器有著公共的接口，具體見P296，forward_list迭代器不支持遞減運算符（--）。一個迭代器范圍由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者是尾元素之后的位置，這兩個迭代器通常被稱為begin和end，可以通過反復遞增begin來到達end，換句話說end不在begin之前。

9.容器的定義和初始化方式如下圖所示：

將一個新容器創建為另一個容器的拷貝的方法有兩種：可以直接拷貝整個容器，或者（array除外）拷貝由一個迭代器對指定的元素范圍。為了創建一個容器為另一個容器的拷貝，兩個容器的類型及其元素類型必須匹配。不過當傳遞迭代器參數來拷貝一個范圍時，就不要求容器類型是相同的了。而且新容器和原容器中的元素類型也可以不同，只要能將要拷貝的元素轉換為要初始化的容器的元素類型即可（P300）。只有順序容器的構造函數才接受大小參數，關聯容器并不支持。當定義一個array時，除了指定元素類型還要指定容器大小，如array<int，42>。對于內置數組類型是不能進行拷貝或對象賦值操作的，但是可以對array進行拷貝或對象賦值操作（P301）。

10.容器的賦值運算和swap操作如下圖（注意區別初始化與賦值）：

經過c1=c2賦值運算之后，左邊容器將與右邊容器相等，如果兩個容器原來大小不同，賦值后兩者的大小都與右邊容器的原大小相同。賦值運算要求左邊和右邊的運算對象具有相同的類型，順序容器還定義了一個名為assign的成員，允許從一個不同但相容的類型賦值，或者從容器的一個子序列賦值（P302）。除array外，swap交換兩個容器內容的操作保證會很快，因為元素本身并未交換，swap只是交換了兩個容器的內部數據結構（如指針）。這意味著，除string外，指向容器的迭代器、引用和指針在swap操作之后都不會失效，它們仍指向swap操作之前所指向的那些元素。但是，在swap之后，這些元素已經屬于不同的容器了。例如，假定iter在swap之前指向svec1[3]的string，那么在swap之后它指向svec2[3]的元素。與其他容器不同，對一個string調用swap會導致迭代器、引用和指針失效。與其他容器不同，swap兩個array會真正交換它們的元素，因此交換兩個array所需的時間與array中元素的數目成正比。對于array，在swap操作之后，指針、引用和迭代器所綁定的元素保持不變，但元素值已經與另一個array中對應元素的值進行了交換。

11.每個容器類型都支持相等運算符(==和!=)，除了無序關聯容器外的所有容器都支持關系運算符(>、>=、<=)。關系運算符左右兩邊的運算對象必須是相同類型的容器，且必須保存相同類型的元素。只有當其元素類型也定義了相應的比較運算符時，才可以使用關系運算符來比較兩個容器（P304）。

12.可用以下方式向順序容器中添加元素：

需要注意的是，不同容器使用不同的策略來分配元素空間，而這些策略直接影響性能。在一個vector或string的尾部之外的任何位置，或是一個deque的首尾之外的任何位置添加元素，都需要移動元素。而且，向一個vector或string添加元素可能引起整個對象存儲空間的重新分配。重新分配一個對象的存儲空間需要分配新的內存，并將元素從舊的空間移動到新的空間中。在用一個對象來初始化容器時，或將一個對象插入到容器中時，實際上放入到容器中的是對象值的一個拷貝，而不是對象本身。容器中的元素與提供值的對象之間沒有任何關聯，隨后對容器中元素的任何改變都不會影響到原始對象，反之亦然。list、vector、deque、string支持push_back；list、forward_list、deque支持push_front；vector、deque、list、string都支持insert（P307）。emplace函數在容器中直接構造元素（而不是拷貝元素），傳遞給emplace函數的參數必須與元素類型的構造函數相匹配。

13.順序容器中訪問元素的操作如下：

注意上述函數或下標返回的都是引用。刪除元素的操作會改變容器的大小所以不適用于array，非array容器的刪除元素的方式如下圖：

刪除元素的成員函數并不檢查其參數。在刪除元素之前，程序員必須確保它(們)是存在的。可用下圖所示的方法改變容器大小：

14.forward_list是單向鏈表，在單向鏈表中沒有一個簡單方法來獲取一個元素的前驅，所以forward_list中的函數與前述的那些容器中的函數有所不同，具體如下圖所示（P313）：

15.容器操作，如添加元素或刪除元素可能使迭代器失效，具體情況見P315。由于向迭代器添加元素和從迭代器刪除元素的代碼可能會使迭代器失效，因此必須保證每次改變容器的操作之后都正確地重新定位選代器。

16.為了支持快速隨機訪問，vector將元素連續存儲，每個元素緊挨著前一個元素存儲。vector和string類型提供了一些成員函數，允許與它的實現中內存分配部分互動。capacity操作顯示容器在不擴張內存空間的情況下可以容納多少個元素，reserve操作允許通知容器它應該準備保存多少個元素。如下圖：

只有當需要的內存空間超過當前容量時，reserve調用才會改變vector的容量，如果需求大小大于當前容量，reserve至少分配與需求一樣大的內存空間（可能更大，依賴具體實現），如果需求大小小于或等于當前容量，reserve什么也不做，所以調用reserve 永遠也不會減少容器占用的內存空間。當需求大小小于當前容量時，容器不會退回內存空間。因此在調用reserve之后，capacity將會大于或等于傳遞給reserve的參數。類似的，resize成員函數只改變容器中元素的數目而不是容器的容量。可以調用shrink_to_fit來要求deque、vector或string退回不需要的內存空間，此函數指出不再需要任何多余的內存空間，但是具體的實現可以選擇忽略此請求。容器的size是指它已經保存的元素的數目，而capacity則是在不分配新的內存空間的前提下它最多可以保存多少元素（P319）。

17.除了支持與其他順序容器一樣的構造函數，string還支持下圖所示的三種構造函數：

substr操作返回一個string，它是原始string的一部分或全部的拷貝，如下圖：

改變string的其他函數如下圖所示，具體參考P324：

與string相關的搜索函數如下圖所示：

string中的compare函數：

string中與數值轉換相關的函數如下：

18.容器適配器：除了順序容器外，標準庫還定義了三個順序容器適配器：stack、queue 和priority_queue。本質上，一個適配器是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型。默認情況下，stack和queue是基于deque實現的，priority_queue是在vector之上實現的，可以在創建一個適配器時將一個命名的順序容器作為第二個類型參數來重載默認容器類型，如stack<string，vector<string>>str_stk;表示在vector上實現棧。所有適配器都要求容器具有添加和刪除元素的能力，因此適配器不能構造在array之上。類似也不能用forward_list 來構造適配器，因為所有適配器都要求容器具有添加、刪除以及訪問尾元素的能力。stack支持的棧操作如下圖：

queue和priority_queue支持的操作如下圖（P331）：

19.內存空間重新分配發生在容器添加或刪除元素時，特別是在動態數組類容器（如std::vector）中，當現有內存空間不足時，容器會申請更多的內存空間。在添加元素時，容器可能會為避免頻繁的分配而增加內存容量，并將現有元素遷移到新的內存區域。在刪除元素時，容器可能會釋放不再需要的內存，但這不總是自動發生（如std::vector需要手動調用shrink_to_fit()）。

20.泛型算法：它們實現了一些經典算法的公共接口，如排序和搜索，可用于不同類型的元素和多種容器類型。泛型算法本身不會執行容器的操作，只會運行在迭代器之上，執行迭代器的操作，算法永遠不會改變底層容器的大小，算法可能改變容器中保存的元素的值，也可能移動容器內的元素，但永遠不會直接添加或刪除元素（P337）。常見的泛型算法如：find(beg，end，val)返回一個迭代器（beg和end是表示元素范圍的迭代器），指向輸入序列中的第一個值為val的元素；accumulate(beg，end，init)返回輸入序列中所有值的和，和的初值由init指定，返回類型與init類型相同，使用+運算計算和；equal(beg1，end1，beg2)比較兩個序列是否相等，如果兩個序列對應值相等返回true，beg1、end1表示第一個序列的元素范圍，beg2表示第二個序列的首元素，像這種用一個單一迭代器表示第二個序列的算法都假定第二個序列至少與第一個一樣長；fill(beg，end，val)將值val賦予給定序列中的每一個元素；copy(beg，end，dest)從輸入范圍將元素拷貝到dest指定的目的序列，返回的是其目的位置迭代器（遞增后）的值；repalce(beg，end，old_val，new_val)將給定序列中的old_val替換成new_val；replace_copy(beg，end，dest，old_val，new_val)將給定序列拷貝到dest，并將序列中的old_val替換成new_val；sort(beg，end)將給定序列排序，利用元素類型的<運算符排序；unique(beg，end)對給定序列排序，將相鄰的重復序列“消除”，返回一個指向不重復元素尾后位置的迭代器。其他更多泛型算法見P770附錄A.2。

21.一種保證算法有足夠元素空間來容納輸出數據的方法是使用插入迭代器back_inserter，back_inserter接受一個指向容器的引用，返回一個與該容器綁定的插入迭代器。當通過此迭代器賦值時，賦值運算符會調用push_back將一個具有給定值的元素添加到容器中（P341）。

22.很多算法都會比較輸入序列中的元素，默認情況下，這類算法使用元素類型的<或==運算符完成比較。標準庫還為這些算法定義了額外的版本，允許我們提供自己定義的操作來代替默認運算符。例如，sort算法默認使用元素類型的<運算符，但可能我們希望的排序順序與<所定義的順序不同，或是我們的序列可能保存的是未定義<運算符的元素類型。這兩種情況下都需要重載sort的默認行為。sort的第二個版本sort(beg，end，comp)是重載過的，它接受第三個參數，此參數是一個謂詞（謂詞是一個可調用的表達式，其返回結果是一個能用作條件的值，有些算法只接受一元謂詞，有些算法只接受二元謂詞）。如sort(words.begin()，words.end()，isShorter)表示按isShorter函數定義的規則（按照單詞長度排序）給words排序，isShorter是一個二元謂詞。在將words按大小重排的同時，還希望具有相同長度的元素按字典序排列。為了保持相同長度的單詞按字典序排列，可以使用stable_sort算法，這種穩定排序算法維持相等元素的原有順序（P345）。

23.lambda表達式：一個lambda表達式表示一個可調用的代碼單元，可以將其理解為一個未命名的內聯函數。與任何函數類似，一個lambda具有一個返回類型、一個參數列表和一個函數體。但與函數不同，lambda可能定義在函數內部。一個lambda表達式具有如下形式：[capture list](parameter list)->return type {function body}，其中capture list（捕獲列表）是一個lambda所在函數中定義的局部變量的列表，return type、parameter list和function body與任何普通函數一樣，分別表示返回類型參數列表和函數體，但與普通函數不同，lambda必須使用尾置返回來指定返回類型，lambda的調用方式與普通函數的調用方式相同。在lambda中忽略括號和參數列表等價于指定一個空參數列表，如果忽略返回類型，lambda根據函數體中的代碼推斷出返回類型，如果函數體只有一個return語句，則返回類型從返回的表達式的類型推斷而來，否則返回類型為void（如果lambda的函數體包含任何單一return語句之外的內容，且未指定返回類型，則返回void），若返回類型被推斷為void則不能返回任何值。lambda不能有默認參數，因此lambda調用的實參數目永遠與形參數目相等。一個lambda只有在其捕獲列表中捕獲一個它所在函數中的局部變量，才能在函數體中使用該變量，但一個lambda可以直接使用定義在當前函數之外的名字。當定義一個lambda時，編譯器生成一個與lambda對應的新的（未命名的）類類型，當使用auto定義一個用lambda初始化的變量時，定義了一個從lambda生成的類型的對象。默認情況下從lambda生成的類都包含一個對應該lambda所捕獲的變量的數據成員，類似任何普通類的數據成員，lambda的數據成員也在lambda對象創建時被初始化。lambda可以采取值捕獲或者引用捕獲，當以引用捕獲方式捕獲一個變量時必須保證lambda執行時變量是存在的，具體如下圖（P352）：

對于值捕獲，被捕獲的變量的值是在lambda創建時拷貝，而不是調用時拷貝，所以創建之后的函數中對所捕獲的值的修改不會影響到lambda內對應的值（P350）。默認情況下，對于一個值被拷貝的變量，lambda不會改變其值。如果希望改變這個被捕獲的變量的值，就必須在參數列表首加上關鍵字mutable。一個引用捕獲的變量是否可以被修改依賴于此引用指向的是一個const類型還是一個非const類型。

24.for_each(beg，end，unaryOp)對輸入序列中的每個元素應用可調用對象unaryOp，unaryOp的返回值（如果有的話）被忽略（P348）。ref函數返回一個對象，包含給定的引用，例如ref(cin)返回對cin的引用，cref函數與ref函數類似，生成一個保存const引用的類（P357）。

25.bind函數：可以將bind函數看作一個通用的函數適配器，它接受一個可調用對象，生成一個新的可調用對象來“適應”原對象的參數列表。調用bind的一般形式為：auto newCallable=bind(callable，arg_list);，其中newCallable本身是一個可調用對象，arg_list是一個逗號分隔的參數列表，對應給定的callable的參數，當調用newCallable時，newCallable會調用callable，并傳遞給它arg_list中的參數。arg_list中的參數可能包含形如_n的名字，其中n是一個整數。這些參數是“占位符”，表示newCallable的參數，它們占據了傳遞給newCallable的參數的“位置”。數值n表示生成的可調用對象中參數的位置：_1為newCallable的第一個參數，_2為第二個參數，依此類推。名字_n都定義在一個名為placeholders的命名空間中，而這個命名空間本身定義在std命名空間中。為了使用這些名字，兩個命名空間都要寫上。可以使用using namespace name;的形式（using namespace std::placeholders;）來說明希望所有來自namespace_name的名字都可以在的程序中直接使用（P355）。

26.標準庫在頭文件iterator還定義了額外幾種迭代器：

• 插入迭代器：這些迭代器被綁定到一個容器上，可以用來向容器插入元素。插入器是一種迭代器適配器，它接受一個容器，生成一個迭代器，能實現向給定容器添加元素。插入迭代器操作如下圖：

  

  back_inserter(c)創建一個使用push_back的迭代器；front_inserter(c)創建一個使用push_front的迭代器；inserter(c，p)創建一個使用insert的迭代器，此函數接受第二個參數，這個參數必須是一個指向給定容器的迭代器，元素將被插入到給定選代器所表示的元素之前(c為目標容器，p是迭代器指向容器c中某個元素)（P358）。
• 流迭代器：這些迭代器被綁定到輸入或輸出流上，可用來遍歷所關聯的IO流。istream_iterator讀取輸入流，ostream_iterator向一個輸出流寫入數據。對于istream_iterator，默認初始化迭代器就創建了一個可以當作尾后值使用的迭代器，對于一個綁定到流的迭代器，值就與尾后迭代器相等。一旦其關聯的流遇到文件尾或遇到IO錯誤，迭代器的值就與尾后迭代器相等。可以為任何定義了輸入運算符（>>運算符）的類型創建istream_iterator對象，可以為任何定義了輸出運算符（<<運算符）的類型定義ostream_iterator對象，當創建一個ostream_iterator時，可以提供（可選的）第二參數，它是一個字符串，在輸出每個元素后都會打印此字符串，不允許任何空的或表示尾后位置的ostream_iterator。istream_iterator的操作如下圖：

  

  在將一個istream_iterator綁定到一個流時，標準庫并不保證迭代器立即從流讀取數據。具體實現可以推遲從流中讀取數據，直到使用迭代器時才真正讀取。標準庫中的實現所保證的是，在第一次解引用迭代器之前，從流中讀取數據的操作已經完成了。ostream_iterator的操作如下圖：

  

• 反向迭代器：這些迭代器向后而不是向前移動，除了forward_list之外的標準庫容器都有反向迭代器。可以通過調用rbegin、rend、crbegin和crend成員函數來獲得反向迭代器。這些成員函數返回指向容器尾元素和首元素之前一個位置的迭代器。與普通迭代器一樣，反向迭代器也有const和非const版本。只能從既支持++也支持--的迭代器來定義反向迭代器，畢竟反向迭代器的目的是在序列中反向移動，流迭代器不支持遞減運算，因為不可能在一個流中反向移動（P363）。反向迭代器的base方法可以將反向迭代器轉換成普通迭代器（P364）。
• 移動迭代器：這些專用的迭代器不是拷貝其中的元素，而是移動它們。

27.任何泛型算法的最基本的特性是它要求其迭代器提供哪些操作，算法所要求的迭代器操作可以分為5個迭代器類別，如下圖：

在泛型算法中，對每個迭代器參數來說，其能力必須與規定的最小類別至少相當，向算法傳遞一個能力更差的迭代器會產生錯誤。如：算法reverse要求雙向迭代器，算法sort要求隨機訪問迭代器（P366）。在任何其他算法分類之上，泛型算法還有一組參數規范，大多數算法具有以下四種形式之一：

其中alg是算法的名字，beg和end表示算法所操作的輸入范圍。dest、beg2和end2，都是迭代器參數，分別表示指定的目的位置和第二個范圍，除了這些迭代器參數，一些算法還接受額外的、非迭代器的特定參數。向輸出迭代器寫入數據的算法都假定目標空間足夠容納寫入的數據。除了參數規范，算法還遵循一套命名和重載規范，例如算法名以_if、_copy結尾的算法都有特定含義，具體見P369。與其他容器不同，鏈表類型list和forward_list定義了幾個成員函數形式的算法，對于list和forward_list應該優先使用成員函數版本的算法而不是通用版本的算法，因為前者性能更好。如下圖：

鏈表類型還定義了splice算法，如下圖：

28.關聯容器：關聯容器中的元素是按照關鍵字來保存和訪問的。C++標準庫共提供了八個關聯容器。如下圖：

無序容器使用哈希函數來組織元素（P374）。

29.關聯容器不支持順序容器的位置相關的操作，例如push_front或push_back，原因是關聯容器中元素是根據關鍵字存儲的，這些操作對關聯容器沒有意義。當定義一個map時，必須既指明關鍵字類型又指明值類型；而定義一個set時，只需指明關鍵字類型，因為set中沒有值。每個關聯容器都定義了一個默認構造函數，它創建一個指定類型的空容器。也可以將關聯容器初始化為另一個同類型容器的拷貝，或是從一個值范圍來初始化關聯容器，只要這些值可以轉化為容器所需類型就可以。也可以對關聯容器進行列表初始化（P377）。一個map或set中的關鍵字必須是唯一的，即，對于一個給定的關鍵字，只能有一個元素的關鍵字等于它。容器multimap和multiset沒有此限制，它們都允許多個元素具有相同的關鍵字。

30.對于有序容器：map、multimap、set以及multiset，關鍵字類型必須定義元素比較的方法。默認情況下，標準庫使用關鍵字類型的<運算符來比較兩個關鍵字。在集合類型中，關鍵字類型就是元素類型；在映射類型中，關鍵字類型是元素的第一部分的類型。可以提供自己定義的操作來代替關鍵字上的<運算符，所提供的操作必須在關鍵字類型上定義一個嚴格弱序，可以將嚴格弱序看作“小于等于”，雖然實際定義的操作可能是一個復雜的函數，無論怎樣定義比較函數，它必須具備如下基本性質：

為了指定使用自定義的操作，必須在定義關聯容器類型時提供此操作的類型。如前所述，用尖括號指出要定義哪種類型的容器，自定義的操作類型必須在尖括號中緊跟著元素類型給出，具體例子見P379。

31.pair是一個標準庫類型，一個pair保存兩個數據成員，pair的默認構造函數對數據成員進行值初始化，例如：pair<string，string> anon，則anon是一個包含兩個空string的pair。與其他標準庫類型不同，pair的數據成員是public的，兩個成員分別命名為first和second。pair上的操作如下圖（P380）：

32.關聯容器支持容器共同的類型和操作（見P295），即第7條中的圖9.2列出的內容，除此之外關聯容器還定義了下圖所示的類型：

對于set類型，key_type和value_type是一樣的，set中保存的值就是關鍵字。在一個map中，元素是關鍵字-值對。即每個元素是一個pair對象，包含一個關鍵字和一個關聯的值。可以使用作用域運算符來提取一個類型的成員，例如map<string，int>::key_type，只有map類型（unordered_map、unordered_multimap、multimap和map）才定義了mapped_type（P382）。當解引用一個關聯容器迭代器時，會得到一個類型為容器的value_type的值的引用。對map而言，value_type是一個pair類型，其first成員保存const的關鍵字，second成員保存值，一個map的value_type是一個pair，可以改變pair的值，但不能改變關鍵字成員的值。雖然set類型同時定義了iterator和const_iterator類型，但兩種類型都只允許只讀訪問set中的元素。與不能改變一個map元素的關鍵字一樣，一個set中的關鍵字也是const的。可以用一個set迭代器來讀取元素的值，但不能修改。可以使用begin、end迭代器遍歷map和set，當使用一個迭代器遍歷一個map、multimap、set或multiset時，選代器按關鍵字升序遍歷元素。通常不對關聯容器使用泛型算法，關鍵字是const這一特性意味著不能將關聯容器傳遞給修改或重排容器元素的算法，因為這類算法需要向元素寫入值，而set類型中的元素是const的，map中的元素是pair，其第一個成員是const的。關聯容器可用于只讀取元素的算法（P383）。

33.關聯容器的insert成員用于向容器中添加元素，如下圖：

關聯容器的刪除操作如下圖：

map和unordered_map容器提供了下標運算符和一個對應的at函數，如下圖：

set類型容器、multimap和unordered_multimap都不支持下標操作。map下標運算符接受一個索引（即一個關鍵字），獲取與此關鍵字相關聯的值。但是與其他下標運算符不同的是，如果關鍵字并不在map中，會為它創建一個元素并插入到map中，關聯值將進行值初始化，由于下標運算符可能插入一個新元素，所以只可以對非const的map使用下標操作。通常情況下，解引用一個迭代器所返回的類型與下標運算符返回的類型是一樣的，但對map則不然，當對一個map進行下標操作時，會獲得一個mapped_type對象，但當解引用一個map迭代器時，會得到一個value_type對象（P388）。如果一個multimap或multiset 中有多個元素具有給定關鍵字，則這些元素在容器中會相鄰存儲（因為它們是有序的）。在一個關聯容器中的查找操作如下圖：

如果沒有元素與給定關鍵字匹配，則lower_bound和upper_bound 會返回相等的迭代器：都指向給定關鍵字的插入點，能保持容器中元素順序的插入位置（P391）。

34.四個無序關聯容器不是使用比較運算符來組織元素，而是使用一個哈希函數和關鍵字類型的==運算符。無序容器提供了一組管理桶的函數：

無序容器在存儲上組織為一組桶，每個桶保存零個或多個元素，無序容器使用一個哈希函數將元素映射到桶。為了訪問一個元素，容器首先計算元素的哈希值，它指出應該搜索哪個桶，容器將具有一個特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復關鍵字，所有具有相同關鍵字的元素也都會在同一個桶中。因此，無序容器的性能依賴于哈希函數的質量和桶的數量和大小。對于相同的參數，哈希函數必須總是產生相同的結果。理想情況下，哈希函數還能將每個特定的值映射到唯一的桶，但將不同關鍵字的元素映射到相同的桶也是允許的。默認情況下，無序容器使用關鍵字類型的==運算符來比較元素，還使一個hash<key_type>類型的對象來生成每個元素的哈希值。標準庫為內置類型（包括指針）提供了hash模板。還為一些標準庫類型，包括string 和智能指針類型定義了hash。因此可以直接定義關鍵字是內置類型（包括指針類型）、string還有智能指針類型的無序容器。但是不能直接定義關鍵字類型為自定義類類型的無序容器，與容器不同，不能直接使用哈希模板，而必須提供自己的hash模板版本，參考P396。無論在有序容器中還是在無序容器中，具有相同關鍵字的元素都是相鄰存儲的。

35.動態內存的使用很容易出問題，因為確保在正確的時間釋放內存是極其困難的。有時會忘記釋放內存，在這種情況下就會產生內存泄漏；有時在尚有指針引用內存的情況下就釋放了它，在這種情況下就會產生引用非法內存的指針。為了更容易（同時也更安全）地使用動態內存，新的標準庫提供了兩種智能指針類型來管理動態對象。智能指針的行為類似常規指針，重要的區別是它負責自動釋放所指向的對象。新標準庫提供的這兩種智能指針的區別在于管理底層指針的方式：shared_ptr 允許多個指針指向同一個對象；unique_ptr 則“獨占”所指向的對象。標準庫還定義了一個名為weak_ptr的伴隨類，它是一種弱引用，指向shared_ptr所管理的對象。這三種類型都定義在memory頭文件中（P400）。

36.類似 vector，智能指針也是模板，因此當創建一個智能指針時，必須提供額外的信息指明指針可以指向的類型。如：shared_ptr<string> p1定義了一個可以指向string的shared_ptr指針p1。智能指針的使用方式與普通指針類似，解引用一個智能指針返回它指向的對象，如果在一個條件判斷中使用智能指針，效果就是檢測它是否為空。shared_ptr和unique_ptr支持的操作如下圖所示：

類似順序容器的emplace成員，make_shared 用其參數來構造給定類型的對象。例如，調用make_shared <string>時傳遞的參數必須與string的某個構造函數相匹配，調用make_shared <int>時傳遞的參數必須能用來初始化一個int，依此類推。如果不傳遞任何參數，對象就會進行值初始化。

37.可以認為每個shared_ptr都有一個關聯的計數器，通常稱其為引用計數。在內存中shared_ptr包含了一個指向對象的指針和一個指向控制塊的指針，每一個由shared_ptr管理的對象都有一個控制塊，該控制塊包含引用計數等信息，無論何時拷貝一個shared_ptr，計數器都會遞增。例如，當用一個shared_ptr初始化另一個shared_ptr或將它作為參數傳遞給一個函數以及作為函數的返回值時，它所關聯的計數器就會遞增。當給shared_ptr賦予一個新值或是shared_ptr被銷毀（例如一個局部的shared_ptr離開其作用域）時，計數器就會遞減。一旦一個shared_ptr的計數器變為0，它就會自動釋放自己所管理的對象。類似于構造函數，每個類都有一個析構函數。就像構造函數控制初始化一樣，析構函數控制此類型的對象銷毀時做什么操作，shared_ptr就是通過析構函數來完成銷毀工作的（P402）。對于一塊內存，shared_ptr類保證只要有任何shared_ptr對象引用它，它就不會被釋放掉。

38.程序使用動態內存出于以下三種原因之一：程序不知道自己需要使用多少對象；程序不知道所需對象的準確類型；程序需要在多個對象間共享數據。

39.C++語言定義了兩個運算符來分配和釋放動態內存。運算符new分配內存，delete釋放new分配的內存。相對于智能指針，使用這兩個運算符管理內存非常容易出錯。在自由空間分配的內存是無名的，因此new無法為其分配的對象命名，而是返回一個指向該對象的指針：int *pi=new int;則pi指向一個動態分配的、未初始化的無名對象。默認情況下，動態分配的對象是默認初始化的，這意味著內置類型或組合類型的對象的值將是未定義的，而類類型對象將用默認構造函數進行初始化。也可以對動態分配的對象進行值初始化，只需在類型名之后跟一對空括號即可：string *ps=new string();，此時string會被值初始化為空。如果提供了一個括號包圍的初始化器，就可以使用auto從此初始化器來推斷我們想要分配的對象的類型。但是，由于編譯器要用初始化器的類型來推斷要分配的類型，只有當括號中僅有單一初始化器時才可以使用auto：auto pl=new auto(obj);是正確而auto p2=new auto{a，b，c};是錯誤的。類似其他任何const對象，一個動態分配的const對象必須進行初始化（P408）。默認情況下，如果new不能分配所要求的內存空間，它會拋出一個類型為bad_alloc的異常，也可以改變new的方式來阻止它拋出異常，如：int *p2 =new(nothrow) int; 傳遞給new一個由標準庫定義的名為nothrow的對象，以此來告訴它不能拋出異常，如果這種形式的new不能分配所需內存，它會返回一個空指針。可以通過delete p的形式來將動態分配的內存還給系統，傳遞給delete的p指針必須是n動態分配的內存或者是一個空指針。釋放一塊并非new分配的內存，或者將相同的指針值釋放多次，其行為是未定義的（P409）。由內置指針（而不是智能指針）管理的動態內存在被顯式釋放前一直都會存在。當delete 一個指針后，指針值就變為無效了，雖然指針值已經無效，但是在很多機器上指針仍然保存著（已經釋放了的）動態內存的地址，所以在delete指針后，最好將其置為nullptr。但可能還存在指向這個（已經釋放了的）動態內存的地址的其他指針，在delete之后，這些指針就變成了空懸指針，即指向一塊曾經保存數據對象但現在已經無效的內存的指針。

40.可以用new返回的指針來初始化智能指針，接受指針參數的智能指針構造函數是explicit的（被explicit修飾的構造函數只能用于直接初始化（使用()初始化，如Class foo(parameter)），而不能用于拷貝初始化（用=初始化，如Class foo=parameter））。因此不能將一個內置指針隱式轉換為一個智能指針，必須使用直接初始化形式來初始化一個智能指針：shared_ptr<int> p1=new int(1024)是錯誤的，必須使用直接初始化形式shared_ptr <int> p2(new int(1024));。默認情況下，一個用來初始化智能指針的普通指針必須指向動態內存，因為智能指針默認使用 delete釋放它所關聯的對象。但也可以將智能指針綁定到一個指向其他類型的資源的指針上，但是為了這樣做，必須提供自己的操作來替代delete。如下圖：

與賦值類似，reset會更新引用計數，如果需要的話，會釋放p指向的對象。shared_ptr可以協調對象的析構，但這僅限于其自身的拷貝（也是shared_ptr）之間。所以推薦使用make_shared 而不是new，這樣就能在分配對象的同時就將shared_ptr與之綁定，從而避免了無意中將同一塊內存綁定到多個獨立創建的shared_ptr上（注意這里的獨立創建的含義，說明他們在內存中指向不同的控制塊，擁有不同的計數器，但實際卻指向同一個對象）。如果多個獨立的shared_ptr指向同一塊內存，則這幾個shared_ptr是獨立計數的。當將一個 shared_ptr綁定到一個普通指針時，就將內存的管理責任交給了這個shared_ptr，一旦這樣做了，就不應該再使用內置指針來訪問shared_ptr所指向的內存了。也不要使用 get初始化另一個智能指針或為智能指針賦值：智能指針類型定義了一個名為get的函數，它返回一個內置指針，指向智能指針管理的對象。此函數是為了這樣一種情況而設計的：當需要向不能使用智能指針的代碼傳遞一個內置指針時。get用來將指針的訪問權限傳遞給代碼，只有在確定代碼不會delete指針的情況下，才能使用get。特別是，永遠不要用get初始化另一個智能指針或者為另一個智能指針賦值（P414）。

41.可以將智能指針用于異常處理，來確保資源的正確釋放，具體參考P415。智能指針可以提供對動態分配的內存安全而又方便的管理，但這建立在正確使用的前提下。為了正確使用智能指針，必須堅持一些基本規范：

• 不使用相同的內置指針值初始化（或reset）多個智能指針。
• 不delete get()返回的指針。
• 不使用get()初始化或reset另一個智能指針。
• 如果使用get()返回的指針，當最后一個對應的智能指針銷毀后，指針就變為無效了。
• 如果使用智能指針管理的資源不是new分配的內存，記住傳遞給它一個刪除器（即自定義的delete操作）。

42.一個unique_ptr“擁有”它所指向的對象。與shared_ptr不同，某個時刻只能有一個 unique_ptr指向一個給定對象。當unique_ptr 被銷毀時，它所指向的對象也被銷毀。由于一個 unique_ptr擁有它指向的對象，因此 unique_ptr不支持普通的拷貝或賦值操作。unique_ptr的相關操作如下圖：

雖然不能拷貝或賦值 unique_ptr，但可以通過調用release（并沒有進行資源的釋放）或reset 將指針的所有權從一個（非const）unique_ptr轉移給另一個unique_ptr，具體例子見P418。調用release 會切斷unique_ptr和它原來管理的對象間的聯系。release 返回的指針通常被用來初始化另一個智能指針或給另一個智能指針賦值。但是如果不用另一個智能指針來保存release返回的指針，我們的程序就要負責資源的釋放。不能拷貝unique_ptr的規則有一個例外，可以拷貝或賦值一個將要被銷毀的unique_ptr，最常見的例子是從函數返回一個unique_ptr。類似 shared_ptr，unique_ptr默認情況下用 delete 釋放它指向的對象，與shared_ptr一樣，可以重載一個unique_ptr中默認的刪除器（即delete操作），但是unique_ptr管理刪除器的方式與shared_ptr不同。重載一個 unique_ptr中的刪除器會影響到unique_ptr類型以及如何構造（或reset）該類型的對象，必須在尖括號中unique_ptr指向類型之后提供刪除器類型。在創建或reset 一個這種 unique_ptr類型的對象時，必須提供一個指定類型的可調用對象(刪除器)：unique_ptr<objT，delT> p(newobjT，fcn);（P419）。

43.weak_ptr是一種不控制所指向對象生存期的智能指針，它指向由一個shared_ptr管理的對象。將一個weak_ptr綁定到一個shared_ptr 不會改變shared_ptr的引用計數。一旦最后一個指向對象的shared_ptr被銷毀，對象就會被釋放。即使有weak_ptr指向對象，對象也還是會被釋放。weak_ptr支持的操作如下圖：

由于對象可能不存在，不能使用weak_ptr直接訪問對象，而必須調用1ock。此函數檢查weak_ptr指向的對象是否仍存在。如果存在，lock返回一個指向共享對象的 shared_ptr。與任何其他shared_ptr類似，只要此shared_ptr存在，它所指向的底層對象也就會一直存在（P420）。

44.大多數應用應該使用標準庫容器而不是動態分配的數組。使用容器更為簡單、更不容易出現內存管理錯誤并且可能有更好的性能。使用容器的類可以使用默認版本的拷貝、賦值和析構操作，分配動態數組的類則必須定義自己版本的操作，在拷貝、復制以及銷毀對象時管理所關聯的內存。為了讓new分配一個對象數組，需要在類型名之后跟一對方括號，在其中指明要分配的對象的數目，方括號中的大小必須是整型，但不必是常量。例如：int *pia=new int[get size()];//pia指向第一個int。也可以用一個表示數組類型的類型別名來分配一個數組，這樣new表達式中就不需要方括號了：typedef int art[42]; int *p=new art;（P423）。當用new分配一個數組時，并未得到一個數組類型的對象，而是得到一個數組元素類型的指針。由于分配的內存并不是一個數組類型，因此不能對動態數組調用begin或end。出于相同的原因，也不能用范圍for語句來處理（所謂的）動態數組中的元素。默認情況下，new分配的對象，不管是單個分配的還是數組中的，都是默認初始化的。可以對數組中的元素進行值初始化，方法是在大小之后跟一對空括號，int *pia2 =new int[10]();。不能使用auto分配動態數組。分配一個大小為0的動態數組是合法的，當用new分配一個大小為0的數組時，new返回一個合法的非空指針。此指針保證與new返回的其他任何指針都不相同。對于零長度的數組來說，此指針就像尾后指針一樣，可以像使用尾后迭代器一樣使用這個指針。可以用此指針進行比較操作，可以向此指針加上（或從此指針減去）0，也可以從此指針減去自身從而得到0。但此指針不能解引用，畢竟它不指向任何元素。可以使用delete [] p的形式釋放動態數組，數組中的元素按逆序銷毀，即最后一個元素首先被銷毀，然后是倒數第二個，依此類推。當釋放一個指向數組的指針時，空方括號對是必需的，它指示編譯器此指針指向一個對象數組的第一個元素。如果在delete一個指向數組的指針時忽略了方括號（或者在 delete 一個指向單一對象的指針時使用了方括號），其行為是未定義的（P425）。標準庫提供了一個可以管理new分配的數組的unique_ptr版本。為了用一個unique_ptr管理動態數組，必須在對象類型后面跟一對空方括號：unique_ptr<int []> up(new int[10]);。當一個unique_ptr指向一個數組時，不能使用點和箭頭成員運算符。畢竟unique_ptr指向的是一個數組而不是單個對象，因此這些運算符是無意義的。另一方面，當一個unique_ptr指向一個數組時，我們可以使用下標運算符來訪問數組中的元素：

與unique_ptr不同，shared_ptr不直接支持管理動態數組。如果希望使用shared_ptr管理一個動態數組，必須提供自己定義的刪除器（P426）。shared_ptr未定義下標運算符，而且智能指針類型不支持指針算術運算，因此為了訪問數組中的元素，必須用get獲取一個內置指針，然后用它來訪問數組元素。

45.new有一些靈活性上的局限，其中一方面表現在它將內存分配和對象構造組合在了一起。類似的，delete將對象析構和內存釋放組合在了一起。標準庫 allocator 類定義在頭文件memory中，它幫助我們將內存分配和對象構造分離開來。它提供一種類型感知的內存分配方法，它分配的內存是原始的、未構造的（P427）。allocator是一個模版，它支持的操作如下圖：

allocator分配的內存是未構造的，可以按需要在此內存中構造對象，可以多次調用 a.allocate 來獲取不同的內存塊，這些內存塊通常是不連續的。在新標準庫中，construct成員函數接受一個指針和零個或多個額外參數，在給定位置構造一個元素，額外參數用來初始化構造的對象，這些額外參數必須是與構造的對象的類型相匹配的合法的初始化器。為了使用allocate返回的內存，必須用construct構造對象，使用未構造的內存，其行為是未定義的。當用完對象后，必須對每個構造的元素調用destroy來銷毀它們，函數destroy接受一個指針，對指向的對象執行析構函數。一旦元素被銷毀后，就可以重新使用這部分內存來保存其他string，也可以將其歸還給系統，釋放內存通過調用deallocate來完成（P429）。標準庫還為 allocator類定義了幾個伴隨算法，可以在未初始化內存中創建對象。如下圖：

allocator類的使用方法可以參考P468的例子。