目錄

第七章 類 （Class）

定義抽象數(shù)據(jù)類型

類成員 （Member）

類的成員函數(shù)

非成員函數(shù)

類的構(gòu)造函數(shù)

訪問控制與封裝

友元

封裝的益處

類的其他特性

類的作用域

構(gòu)造函數(shù)再探

委托構(gòu)造函數(shù) （delegating constructor, C++11）

隱式的類型轉(zhuǎn)換

聚合類 （aggregate class）

字面值常量類

類的靜態(tài)成員

第八章 IO庫

前面章節(jié)已經(jīng)在用的IO庫設(shè)施

IO類

標(biāo)準(zhǔn)庫定義的IO類型

IO對象不可復(fù)制或賦值

條件狀態(tài)

管理輸出緩沖

文件輸入輸出

fstream特有的操作

文件模式

string流

stringstream特有的操作

第九章 順序容器

順序容器概述

順序容器類型

容器操作

類型

構(gòu)造函數(shù)

賦值和swap

大小

添加元素

訪問元素

刪除元素

特殊的forwad_list操作

改變?nèi)萜鞔笮?/p>

獲取迭代器

反向容器的額外成員

迭代器

容器操作可能使迭代器失效

容器內(nèi)元素的類型約束

vector對象是如何增長的

管理容量的成員函數(shù)

額外的string操作

構(gòu)造string的其他方法

substr操作

改變string的其他方法

string搜索操作

s.compare的幾種參數(shù)形式

string和數(shù)值轉(zhuǎn)換

容器適配器（adapter）

適配器的通用操作和類型

stack

queue和priority_queue

第十章 泛型算法

泛型算法

find

初識泛型算法

只讀算法

寫容器元素的算法

重排容器元素的算法

定制操作

向算法傳遞函數(shù)：

lambda表達(dá)式

lambda捕獲和返回

參數(shù)綁定

再探迭代器

插入迭代器

iostream迭代器

反向迭代器

泛型算法結(jié)構(gòu)

5類迭代器

算法的形參模式

算法命名規(guī)范

特定容器算法

第十一章 關(guān)聯(lián)容器

關(guān)聯(lián)容器概述

定義關(guān)聯(lián)容器

關(guān)鍵字類型的要求

pair

關(guān)聯(lián)容器操作

關(guān)聯(lián)容器迭代器

添加元素

刪除元素

下標(biāo)操作

查找元素

無序容器

第十二章 動(dòng)態(tài)內(nèi)存

動(dòng)態(tài)內(nèi)存與智能指針

shared_ptr類

直接管理內(nèi)存

shared_ptr和new結(jié)合使用

智能指針和異常

unique_ptr

weak_ptr

動(dòng)態(tài)數(shù)組

new和數(shù)組

allocator類

---

第七章 類 （Class）

定義抽象數(shù)據(jù)類型

• 類背后的基本思想：數(shù)據(jù)抽象（data abstraction）和封裝（encapsulation）。

• 數(shù)據(jù)抽象是一種依賴于接口（interface）和實(shí)現(xiàn)（implementation）分離的編程技術(shù)。

類成員 （Member）

• 必須在類的內(nèi)部聲明，不能在其他地方增加成員。

• 成員可以是數(shù)據(jù)，函數(shù)，類型別名。

類的成員函數(shù)

• 成員函數(shù)的聲明必須在類的內(nèi)部。

• 成員函數(shù)的定義既可以在類的內(nèi)部也可以在外部。

• 使用點(diǎn)運(yùn)算符 . 調(diào)用成員函數(shù)。

• 必須對任何const或引用類型成員以及沒有默認(rèn)構(gòu)造函數(shù)的類類型的任何成員使用初始化式。

• ConstRef::ConstRef(int ii): i(ii), ci(i), ri(ii) { }

• 默認(rèn)實(shí)參： Sales_item(const std::string &book): isbn(book), units_sold(0), revenue(0.0) { }

• *this：

  • 每個(gè)成員函數(shù)都有一個(gè)額外的，隱含的形參this。

  • this總是指向當(dāng)前對象，因此this是一個(gè)常量指針。

  • 形參表后面的const，改變了隱含的this形參的類型，如 bool same_isbn(const Sales_item &rhs) const，這種函數(shù)稱為“常量成員函數(shù)”（this指向的當(dāng)前對象是常量）。

  • return *this;可以讓成員函數(shù)連續(xù)調(diào)用。

  • 普通的非const成員函數(shù)：this是指向類類型的const指針（可以改變this所指向的值，不能改變this保存的地址）。

  • const成員函數(shù)：this是指向const類類型的const指針（既不能改變this所指向的值，也不能改變this保存的地址）。

非成員函數(shù)

• 和類相關(guān)的非成員函數(shù)，定義和聲明都應(yīng)該在類的外部。

類的構(gòu)造函數(shù)

• 類通過一個(gè)或者幾個(gè)特殊的成員函數(shù)來控制其對象的初始化過程，這些函數(shù)叫做構(gòu)造函數(shù)。

• 構(gòu)造函數(shù)是特殊的成員函數(shù)。

• 構(gòu)造函數(shù)放在類的public部分。

• 與類同名的成員函數(shù)。

• Sales_item(): units_sold(0), revenue(0.0) { }

• =default要求編譯器合成默認(rèn)的構(gòu)造函數(shù)。(C++11)

• 初始化列表：冒號和花括號之間的代碼： Sales_item(): units_sold(0), revenue(0.0) { }

訪問控制與封裝

• 訪問說明符（access specifiers）：

  • public：定義在 public后面的成員在整個(gè)程序內(nèi)可以被訪問； public成員定義類的接口。

  • private：定義在 private后面的成員可以被類的成員函數(shù)訪問，但不能被使用該類的代碼訪問； private隱藏了類的實(shí)現(xiàn)細(xì)節(jié)。

• 使用 class或者 struct：都可以被用于定義一個(gè)類。唯一的卻別在于訪問權(quán)限。

  • 使用 class：在第一個(gè)訪問說明符之前的成員是 priavte的。

  • 使用 struct：在第一個(gè)訪問說明符之前的成員是 public的。

友元

• 允許特定的非成員函數(shù)訪問一個(gè)類的私有成員.

• 友元的聲明以關(guān)鍵字 friend開始。 friend Sales_data add(const Sales_data&, const Sales_data&);表示非成員函數(shù)add可以訪問類的非公有成員。

• 通常將友元聲明成組地放在類定義的開始或者結(jié)尾。

• 類之間的友元：

  • 如果一個(gè)類指定了友元類，則友元類的成員函數(shù)可以訪問此類包括非公有成員在內(nèi)的所有成員。

封裝的益處

• 確保用戶的代碼不會無意間破壞封裝對象的狀態(tài)。

• 被封裝的類的具體實(shí)現(xiàn)細(xì)節(jié)可以隨時(shí)改變，而無需調(diào)整用戶級別的代碼。

類的其他特性

• 成員函數(shù)作為內(nèi)聯(lián)函數(shù) inline：

  • 在類的內(nèi)部，常有一些規(guī)模較小的函數(shù)適合于被聲明成內(nèi)聯(lián)函數(shù)。

  • 定義在類內(nèi)部的函數(shù)是自動(dòng)內(nèi)聯(lián)的。

  • 在類外部定義的成員函數(shù)，也可以在聲明時(shí)顯式地加上 inline。

• 可變數(shù)據(jù)成員 （mutable data member）：

  • mutable size_t access_ctr;

  • 永遠(yuǎn)不會是const，即使它是const對象的成員。

• 類類型：

  • 每個(gè)類定義了唯一的類型。

類的作用域

• 每個(gè)類都會定義它自己的作用域。在類的作用域之外，普通的數(shù)據(jù)和函數(shù)成員只能由引用、對象、指針使用成員訪問運(yùn)算符來訪問。

• 函數(shù)的返回類型通常在函數(shù)名前面，因此當(dāng)成員函數(shù)定義在類的外部時(shí)，返回類型中使用的名字都位于類的作用域之外。

• 如果成員使用了外層作用域中的某個(gè)名字，而該名字代表一種類型，則類不能在之后重新定義該名字。

• 類中的類型名定義都要放在一開始。

構(gòu)造函數(shù)再探

• 構(gòu)造函數(shù)初始值列表：

  • 類似python使用賦值的方式有時(shí)候不行，比如const或者引用類型的數(shù)據(jù)，只能初始化，不能賦值。（注意初始化和賦值的區(qū)別）

  • 最好讓構(gòu)造函數(shù)初始值的順序和成員聲明的順序保持一致。

  • 如果一個(gè)構(gòu)造函數(shù)為所有參數(shù)都提供了默認(rèn)參數(shù)，那么它實(shí)際上也定義了默認(rèn)的構(gòu)造函數(shù)。

委托構(gòu)造函數(shù) （delegating constructor, C++11）

• 委托構(gòu)造函數(shù)將自己的職責(zé)委托給了其他構(gòu)造函數(shù)。

• Sale_data(): Sale_data("", 0, 0) {}

隱式的類型轉(zhuǎn)換

• 如果構(gòu)造函數(shù)只接受一個(gè)實(shí)參，則它實(shí)際上定義了轉(zhuǎn)換為此類類型的隱式轉(zhuǎn)換機(jī)制。這種構(gòu)造函數(shù)又叫轉(zhuǎn)換構(gòu)造函數(shù)（converting constructor）。

• 編譯器只會自動(dòng)地執(zhí)行僅一步類型轉(zhuǎn)換。

• 抑制構(gòu)造函數(shù)定義的隱式轉(zhuǎn)換：

  • 將構(gòu)造函數(shù)聲明為explicit加以阻止。

  • explicit構(gòu)造函數(shù)只能用于直接初始化，不能用于拷貝形式的初始化。

聚合類 （aggregate class）

• 滿足以下所有條件：

  • 所有成員都是public的。

  • 沒有定義任何構(gòu)造函數(shù)。

  • 沒有類內(nèi)初始值。

  • 沒有基類，也沒有virtual函數(shù)。

• 可以使用一個(gè)花括號括起來的成員初始值列表，初始值的順序必須和聲明的順序一致。

字面值常量類

• constexpr函數(shù)的參數(shù)和返回值必須是字面值。

• 字面值類型：除了算術(shù)類型、引用和指針外，某些類也是字面值類型。

• 數(shù)據(jù)成員都是字面值類型的聚合類是字面值常量類。

• 如果不是聚合類，則必須滿足下面所有條件：

  • 數(shù)據(jù)成員都必須是字面值類型。

  • 類必須至少含有一個(gè)constexpr構(gòu)造函數(shù)。

  • 如果一個(gè)數(shù)據(jù)成員含有類內(nèi)部初始值，則內(nèi)置類型成員的初始值必須是一條常量表達(dá)式；或者如果成員屬于某種類類型，則初始值必須使用成員自己的constexpr構(gòu)造函數(shù)。

  • 類必須使用析構(gòu)函數(shù)的默認(rèn)定義，該成員負(fù)責(zé)銷毀類的對象。

類的靜態(tài)成員

• 非static數(shù)據(jù)成員存在于類類型的每個(gè)對象中。

• static數(shù)據(jù)成員獨(dú)立于該類的任意對象而存在。

• 每個(gè)static數(shù)據(jù)成員是與類關(guān)聯(lián)的對象，并不與該類的對象相關(guān)聯(lián)。

• 聲明：

  • 聲明之前加上關(guān)鍵詞static。

• 使用：

  • 使用作用域運(yùn)算符::直接訪問靜態(tài)成員:r = Account::rate();

  • 也可以使用對象訪問：r = ac.rate();

• 定義：

  • 在類外部定義時(shí)不用加static。

• 初始化：

  • 通常不在類的內(nèi)部初始化，而是在定義時(shí)進(jìn)行初始化，如 double Account::interestRate = initRate();

  • 如果一定要在類內(nèi)部定義，則要求必須是字面值常量類型的constexpr。

第八章 IO庫

前面章節(jié)已經(jīng)在用的IO庫設(shè)施

• istream：輸入流類型，提供輸入操作。

• ostream：輸出流類型，提供輸出操作

• cin：一個(gè)istream對象，從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù)。

• cout：一個(gè)ostream對象，向標(biāo)準(zhǔn)輸出寫入數(shù)據(jù)。

• cerr：一個(gè)ostream對象，向標(biāo)準(zhǔn)錯(cuò)誤寫入消息。

• >>運(yùn)算符：用來從一個(gè)istream對象中讀取輸入數(shù)據(jù)。

• <<運(yùn)算符：用來向一個(gè)ostream對象中寫入輸出數(shù)據(jù)。

• getline函數(shù)：從一個(gè)給定的istream對象中讀取一行數(shù)據(jù)，存入到一個(gè)給定的string對象中。

IO類

標(biāo)準(zhǔn)庫定義的IO類型

• iostream頭文件：從標(biāo)準(zhǔn)流中讀寫數(shù)據(jù)，istream、ostream等。

• fstream頭文件：從文件中讀寫數(shù)據(jù)，ifstream、ofstream等。

• sstream頭文件：從字符串中讀寫數(shù)據(jù)，istringstream、ostringstream

IO對象不可復(fù)制或賦值

• 1.IO對象不能存在容器里.

• 2.形參和返回類型也不能是流類型。

• 3.形參和返回類型一般是流的引用。

• 4.讀寫一個(gè)IO對象會改變其狀態(tài)，因此傳遞和返回的引用不能是const的。

條件狀態(tài)

狀態(tài)解釋

strm:iostate	是一種機(jī)器無關(guān)的類型，提供了表達(dá)條件狀態(tài)的完整功能
strm:badbit	用來指出流已經(jīng)崩潰
strm:failbit	用來指出一個(gè)IO操作失敗了
strm:eofbit	用來指出流到達(dá)了文件結(jié)束
strm:goodbit	用來指出流未處于錯(cuò)誤狀態(tài)，此值保證為零
s.eof()	若流s的eofbit置位，則返回true
s.fail()	若流s的failbit置位，則返回true
s.bad()	若流s的badbit置位，則返回true
s.good()	若流s處于有效狀態(tài)，則返回true
s.clear()	將流s中所有條件狀態(tài)位復(fù)位，將流的狀態(tài)設(shè)置成有效，返回void
s.clear(flags)	將流s中指定的條件狀態(tài)位復(fù)位，返回void
s.setstate(flags)	根據(jù)給定的標(biāo)志位，將流s中對應(yīng)的條件狀態(tài)位置位，返回void
s.rdstate()	返回流s的當(dāng)前條件狀態(tài)，返回值類型為strm::iostate

上表中，strm是一種IO類型，（如istream）， s是一個(gè)流對象。

管理輸出緩沖

• 每個(gè)輸出流都管理一個(gè)緩沖區(qū)，執(zhí)行輸出的代碼，文本串可能立即打印出來，也可能被操作系統(tǒng)保存在緩沖區(qū)內(nèi)，隨后再打印。

• 刷新緩沖區(qū)，可以使用如下IO操縱符：

  • endl：輸出一個(gè)換行符并刷新緩沖區(qū)。

  • flush：刷新流，單不添加任何字符。

  • ends：在緩沖區(qū)插入空字符null，然后刷新。

  • unitbuf：告訴流接下來每次操作之后都要進(jìn)行一次flush操作。

  • nounitbuf：回到正常的緩沖方式。

文件輸入輸出

• 頭文件fstream定義了三個(gè)類型來支持文件IO：

  • ifstream從一個(gè)給定文件讀取數(shù)據(jù)。

  • ofstream向一個(gè)給定文件寫入數(shù)據(jù)。

  • fstream可以讀寫給定文件。

• 文件流：需要讀寫文件時(shí)，必須定義自己的文件流對象，并綁定在需要的文件上。

fstream特有的操作

操作解釋

fstream fstrm;	創(chuàng)建一個(gè)未綁定的文件流。
fstream fstrm(s);	創(chuàng)建一個(gè)文件流，并打開名為s的文件，s可以是string也可以是char指針
fstream fstrm(s, mode);	與前一個(gè)構(gòu)造函數(shù)類似，但按指定mode打開文件
fstrm.open(s)	打開名為s的文件，并和fstrm綁定
fstrm.close()	關(guān)閉和fstrm綁定的文件
fstrm.is_open()	返回一個(gè)bool值，指出與fstrm關(guān)聯(lián)的文件是否成功打開且尚未關(guān)閉

上表中，fstream是頭文件fstream中定義的一個(gè)類型，fstrm是一個(gè)文件流對象。

文件模式

文件模式解釋

in	以讀的方式打開
out	以寫的方式打開
app	每次寫操作前均定位到文件末尾
ate	打開文件后立即定位到文件末尾
trunc	截?cái)辔募?/td>
binary	以二進(jìn)制方式進(jìn)行IO操作。

string流

• 頭文件sstream定義了三個(gè)類型來支持內(nèi)存IO：

  • istringstream從string讀取數(shù)據(jù)。

  • ostringstream向string寫入數(shù)據(jù)。

  • stringstream可以讀寫給定string。

stringstream特有的操作

操作解釋

sstream strm	定義一個(gè)未綁定的stringstream對象
sstream strm(s)	用s初始化對象
strm.str()	返回strm所保存的string的拷貝
strm.str(s)	將s拷貝到strm中，返回void

上表中sstream是頭文件sstream中任意一個(gè)類型。s是一個(gè)string。

?

第九章 順序容器

順序容器概述

• 順序容器（sequential container）：為程序員提供了控制元素存儲和訪問順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時(shí)的位置相對應(yīng)。

順序容器類型

容器類型介紹

vector	可變大小數(shù)組。支持快速隨機(jī)訪問。在尾部之外的位置插入或刪除元素可能很慢。
deque	雙端隊(duì)列。支持快速隨機(jī)訪問。在頭尾位置插入/刪除速度很快。
list	雙向鏈表。只支持雙向順序訪問。在list中任何位置進(jìn)行插入/刪除操作速度都很快。
forward_list	單向鏈表。只支持單向順序訪問。在鏈表任何位置進(jìn)行插入/刪除操作速度都很快。
array	固定大小數(shù)組。支持快速隨機(jī)訪問。不能添加或者刪除元素。
string	與vector相似的容器，但專門用于保存字符。隨機(jī)訪問塊。在尾部插入/刪除速度快。

• 除了固定大小的array外，其他容器都提供高效、靈活的內(nèi)存管理。

• forward_list和array是新C++標(biāo)準(zhǔn)增加的類型。

• 通常使用vector是最好的選擇，除非你有很好的理由選擇其他容器。

• 新標(biāo)準(zhǔn)庫的容器比舊版的快得多。

容器操作

類型

操作解釋

iterator	此容器類型的迭代器類型
const_iterator	可以讀取元素但不能修改元素的迭代器類型
size_type	無符號整數(shù)類型，足夠保存此種容器類型最大可能的大小
difference_type	帶符號整數(shù)類型，足夠保存兩個(gè)迭代器之間的距離
value_type	元素類型
reference	元素的左值類型；和value_type &含義相同
const_reference	元素的const左值類型，即const value_type &

構(gòu)造函數(shù)

操作解釋

C c;	默認(rèn)構(gòu)造函數(shù)，構(gòu)造空容器
C c1(c2);或C c1 = c2;	構(gòu)造c2的拷貝c1
C c(b, e)	構(gòu)造c，將迭代器b和e指定范圍內(nèi)的所有元素拷貝到c
C c(a, b, c...)	列表初始化c
C c(n)	只支持順序容器，且不包括array，包含n個(gè)元素，這些元素進(jìn)行了值初始化
C c(n, t)	包含n個(gè)初始值為t的元素

• 只有順序容器的構(gòu)造函數(shù)才接受大小參數(shù)，關(guān)聯(lián)容器并不支持。

• array具有固定大小。

• 和其他容器不同，默認(rèn)構(gòu)造的array是非空的。

• 直接復(fù)制：將一個(gè)容器復(fù)制給另一個(gè)容器時(shí)，類型必須匹配：容器類型和元素類型都必須相同。

• 使用迭代器復(fù)制：不要求容器類型相同，容器內(nèi)的元素類型也可以不同。

賦值和swap

操作解釋

c1 = c2;	將c1中的元素替換成c2中的元素
c1 = {a, b, c...}	將c1中的元素替換成列表中的元素（不適用于array）
c1.swap(c2)	交換c1和c2的元素
swap(c1, c2)	等價(jià)于c1.swap(c2)
c.assign(b, e)	將c中的元素替換成迭代器b和e表示范圍中的元素，b和e不能指向c中的元素
c.assign(il)	將c中的元素替換成初始化列表il中的元素
c.assign(n, r)	將c中的元素替換為n個(gè)值是t的元素

• 使用非成員版本的swap是一個(gè)好習(xí)慣。

• assign操作不適用于關(guān)聯(lián)容器和array

大小

操作解釋

c.size()	c中元素的數(shù)目（不支持forward_list）
c.max_size()	c中可保存的最大元素?cái)?shù)目
c.empty()	若c中存儲了元素，返回false，否則返回true

添加元素

操作解釋

c.push_back(t)	在c尾部創(chuàng)建一個(gè)值為t的元素，返回void
c.emplace_back(args)	同上
c.push_front(t)	在c頭部創(chuàng)建一個(gè)值為t的元素，返回void
c.emplace_front(args)	同上
c.insert(p, t)	在迭代器p指向的元素之前創(chuàng)建一個(gè)值是t的元素，返回指向新元素的迭代器
c.emplace(p, args)	同上
c.insert(p, n, t)	在迭代器p指向的元素之前插入n個(gè)值為t的元素，返回指向第一個(gè)新元素的迭代器；如果n是0，則返回p
c.insert(p, b, e)	將迭代器b和e范圍內(nèi)的元素，插入到p指向的元素之前；如果范圍為空，則返回p
c.insert(p, il)	il是一個(gè)花括號包圍中的元素值列表，將其插入到p指向的元素之前；如果il是空，則返回p

• 因?yàn)檫@些操作會改變大小，因此不適用于array。

• forward_list有自己專有版本的insert和emplace。

• forward_list不支持push_back和emplace_back。

• 當(dāng)我們用一個(gè)對象去初始化容器或者將對象插入到容器時(shí)，實(shí)際上放入的是對象的拷貝。

• emplace開頭的函數(shù)是新標(biāo)準(zhǔn)引入的，這些操作是構(gòu)造而不是拷貝元素。

• 傳遞給emplace的參數(shù)必須和元素類型的構(gòu)造函數(shù)相匹配。

訪問元素

操作解釋

c.back()	返回c中尾元素的引用。若c為空，函數(shù)行為未定義
c.front()	返回c中頭元素的引用。若c為空，函數(shù)行為未定義
c[n]	返回c中下標(biāo)是n的元素的引用，n時(shí)候一個(gè)無符號證書。若n>=c.size()，則函數(shù)行為未定義
c.at(n)	返回下標(biāo)為n的元素引用。如果下標(biāo)越界，則拋出out_of_range異常

• 訪問成員函數(shù)返回的是引用。

• at和下標(biāo)操作只適用于string、vector、deque、array。

• back不適用于forward_list。

• 如果希望下標(biāo)是合法的，可以使用at函數(shù)。

刪除元素

操作解釋

c.pop_back()	刪除c中尾元素，若c為空，則函數(shù)行為未定義。函數(shù)返回void
c.pop_front()	刪除c中首元素，若c為空，則函數(shù)行為未定義。函數(shù)返回void
c.erase(p)	刪除迭代器p指向的元素，返回一個(gè)指向被刪除元素之后的元素的迭代器，若p本身是尾后迭代器，則函數(shù)行為未定義
c.erase(b, e)	刪除迭代器b和e范圍內(nèi)的元素，返回指向最后一個(gè)被刪元素之后元素的迭代器，若e本身就是尾后迭代器，則返回尾后迭代器
c.clear()	刪除c中所有元素，返回void

• 會改變?nèi)萜鞔笮?#xff0c;不適用于array。

• forward_list有特殊版本的erase

• forward_list不支持pop_back

• vector和string不支持pop_front

特殊的forwad_list操作

• 鏈表在刪除元素時(shí)需要修改前置節(jié)點(diǎn)的內(nèi)容，雙向鏈表會前驅(qū)的指針，但是單向鏈表沒有保存，因此需要增加獲取前置節(jié)點(diǎn)的方法。

• forward_list定義了before_begin，即首前（off-the-begining）迭代器，允許我們再在首元素之前添加或刪除元素。

操作解釋

lst.before_begin()	返回指向鏈表首元素之前不存在的元素的迭代器，此迭代器不能解引用。
lst.cbefore_begin()	同上，但是返回的是常量迭代器。
lst.insert_after(p, t)	在迭代器p之后插入元素。t是一個(gè)對象
lst.insert_after(p, n, t)	在迭代器p之后插入元素。t是一個(gè)對象，n是數(shù)量。若n是0則函數(shù)行為未定義
lst.insert_after(p, b, e)	在迭代器p之后插入元素。由迭代器b和e指定范圍。
lst.insert_after(p, il)	在迭代器p之后插入元素。由il指定初始化列表。
emplace_after(p, args)	使用args在p之后的位置，創(chuàng)建一個(gè)元素，返回一個(gè)指向這個(gè)新元素的迭代器。若p為尾后迭代器，則函數(shù)行為未定義。
lst.erase_after(p)	刪除p指向位置之后的元素，返回一個(gè)指向被刪元素之后的元素的迭代器，若p指向lst的尾元素或者是一個(gè)尾后迭代器，則函數(shù)行為未定義。
lst.erase_after(b, e)	類似上面，刪除對象換成從b到e指定的范圍。

改變?nèi)萜鞔笮?/h3> 操作解釋

c.resize(n)	調(diào)整c的大小為n個(gè)元素，若n<c.size()，則多出的元素被丟棄。若必須添加新元素，對新元素進(jìn)行值初始化
c.resize(n, t)	調(diào)整c的大小為n個(gè)元素，任何新添加的元素都初始化為值t

獲取迭代器

操作解釋

c.begin(), c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend()	返回const_iterator

• 以c開頭的版本是C++11新標(biāo)準(zhǔn)引入的

• 當(dāng)不需要寫訪問時(shí)，應(yīng)該使用cbegin和cend。

反向容器的額外成員

操作解釋

reverse_iterator	按逆序?qū)ぶ吩氐牡?/td>
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(), c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()	返回const_reverse_iterator

• 不支持forward_list

迭代器

• 迭代器范圍：begin到end，即第一個(gè)元素到最后一個(gè)元素的后面一個(gè)位置。

• 左閉合區(qū)間：[begin, end)

• 左閉合范圍蘊(yùn)含的編程設(shè)定：

  • 如果begin和end相等，則范圍為空。

  • 如果二者不等，則范圍至少包含一個(gè)元素，且begin指向該范圍中的第一個(gè)元素。

  • 可以對begin遞增若干次，使得begin == end。

容器操作可能使迭代器失效

• 在向容器添加元素后：

  • 如果容器是vector或string，且存儲空間被重新分配，則指向容器的迭代器、指針、引用都會失效。

  • 對于deque，插入到除首尾位置之外的任何位置都會導(dǎo)致指向容器的迭代器、指針、引用失效。如果在首尾位置添加元素，迭代器會失效，但指向存在元素的引用和指針不會失效。

  • 對于list和forward_list，指向容器的迭代器、指針和引用依然有效。

• 在從一個(gè)容器中刪除元素后：

  • 對于list和forward_list，指向容器其他位置的迭代器、引用和指針仍然有效。

  • 對于deque，如果在首尾之外的任何位置刪除元素，那么指向被刪除元素外其他元素的迭代器、指針、引用都會失效；如果是刪除deque的尾元素，則尾后迭代器會失效，但其他不受影響；如果刪除的是deque的頭元素，這些也不會受影響。

  • 對于vector和string，指向被刪元素之前的迭代器、引用、指針仍然有效。

  • 注意：當(dāng)我們刪除元素時(shí)，尾后迭代器總是會失效。

  • 注意：使用失效的迭代器、指針、引用是嚴(yán)重的運(yùn)行時(shí)錯(cuò)誤！

  • 建議：將要求迭代器必須保持有效的程序片段最小化。

  • 建議：不要保存end返回的迭代器。

容器內(nèi)元素的類型約束

• 元素類型必須支持賦值運(yùn)算；

• 元素類型的對象必須可以復(fù)制。

• 除了輸入輸出標(biāo)準(zhǔn)庫類型外，其他所有標(biāo)準(zhǔn)庫類型都是有效的容器元素類型。

vector對象是如何增長的

vector和string在內(nèi)存中是連續(xù)保存的，如果原先分配的內(nèi)存位置已經(jīng)使用完，則需要重新分配新空間，將已有元素從就位置移動(dòng)到新空間中，然后添加新元素。

管理容量的成員函數(shù)

操作解釋

c.shrink_to_fit()	將capacity()減少到和size()相同大小
c.capacity()	不重新分配內(nèi)存空間的話，c可以保存多少個(gè)元素
c.reverse(n)	分配至少能容納n個(gè)元素的內(nèi)存空間

• shrink_to_fit只適用于vector、string和deque

• capacity和reverse只適用于vector和string。

額外的string操作

構(gòu)造string的其他方法

操作解釋

string s(cp, n)	s是cp指向的數(shù)組中前n個(gè)字符的拷貝，此數(shù)組
string s(s2, pos2)	s是string s2從下標(biāo)pos2開始的字符的拷貝。若pos2 > s2.size()，則構(gòu)造函數(shù)的行為未定義。
string s(s2, pos2, len2)	s是string s2從下標(biāo)pos2開始的len2個(gè)字符的拷貝。

• n,len2,pos2都是無符號值。

substr操作

操作解釋

s.substr(pos, n)	返回一個(gè)string，包含s中從pos開始的n個(gè)字符的拷貝。pos的默認(rèn)值是0，n的默認(rèn)值是s.size() - pos，即拷貝從pos開始的所有字符。

改變string的其他方法

操作解釋

s.insert(pos, args)	在pos之前插入args指定的字符。pos可以使是下標(biāo)或者迭代器。接受下標(biāo)的版本返回指向s的引用；接受迭代器的版本返回指向第一個(gè)插入字符的迭代器。
s.erase(pos, len)	刪除從pos開始的len個(gè)字符，如果len被省略，則刪除后面所有字符，返回指向s的引用。
s.assign(args)	將s中的字符替換成args指定的字符。返回一個(gè)指向s的引用。
s.append(args)	將args指定的字符追加到s，返回一個(gè)指向s的引用。
s.replace(range, args)	刪除s中范圍range中的字符，替換成args指定的字符。返回一個(gè)指向s的引用。

string搜索操作

• string類提供了6個(gè)不同的搜索函數(shù)，每個(gè)函數(shù)都有4個(gè)重載版本。

• 每個(gè)搜索操作都返回一個(gè)string::size_type值，表示匹配發(fā)生位置的下標(biāo)。如果搜索失敗則返回一個(gè)名為string::npos的static成員（類型是string::size_type，初始化值是-1，也就是string最大的可能大小）。

搜索操作解釋

s.find(args)	查找s中args第一次出現(xiàn)的位置
s.rfind(args)	查找s中args最后一次出現(xiàn)的位置
s.find_first_of(args)	在s中查找args中任何一個(gè)字符第一次出現(xiàn)的位置
s.find_last_of(args)	在s中查找args中任何一個(gè)字符最后一次出現(xiàn)的位置
s.find_first_not_of(args)	在s中查找第一個(gè)不在args中的字符
s.find_first_not_of(args)	在s中查找最后一個(gè)不在args中的字符

args必須是一下的形式之一：

args形式解釋

c, pos	從s中位置pos開始查找字符c。pos默認(rèn)是0
s2, pos	從s中位置pos開始查找字符串s。pos默認(rèn)是0
cp, pos	從s中位置pos開始查找指針cp指向的以空字符結(jié)尾的C風(fēng)格字符串。pos默認(rèn)是0
cp, pos, n	從s中位置pos開始查找指針cp指向的前n個(gè)字符。pos和n無默認(rèn)值。

s.compare的幾種參數(shù)形式

邏輯類似于C標(biāo)準(zhǔn)庫的strcmp函數(shù)，根據(jù)s是等于、大于還是小于參數(shù)指定的字符串，s.compare返回0、正數(shù)或負(fù)數(shù)。

參數(shù)形式解釋

s2	比較s和s2
pos1, n1, s2	比較s從pos1開始的n1個(gè)字符和s2
pos1, n1, s2, pos2, n2	比較s從pos1開始的n1個(gè)字符和s2
cp	比較s和cp指向的以空字符結(jié)尾的字符數(shù)組
pos1, n1, cp	比較s從pos1開始的n1個(gè)字符和cp指向的以空字符結(jié)尾的字符數(shù)組
pos1, n1, cp, n2	比較s從pos1開始的n1個(gè)字符和cp指向的地址開始n2個(gè)字符

string和數(shù)值轉(zhuǎn)換

轉(zhuǎn)換解釋

to_string(val)	一組重載函數(shù)，返回?cái)?shù)值val的string表示。val可以使任何算術(shù)類型。對每個(gè)浮點(diǎn)類型和int或更大的整型，都有相應(yīng)版本的to_string()。和往常一樣，小整型會被提升。
stoi(s, p, b)	返回s起始子串（表示整數(shù)內(nèi)容）的數(shù)值，p是s中第一個(gè)非數(shù)值字符的下標(biāo)，默認(rèn)是0，b是轉(zhuǎn)換所用的基數(shù)。返回int
stol(s, p, b)	返回long
stoul(s, p, b)	返回unsigned long
stoll(s, p, b)	返回long long
stoull(s, p, b)	返回unsigned long long
stof(s, p)	返回s起始子串（表示浮點(diǎn)數(shù)內(nèi)容）的數(shù)值，p是s中第一個(gè)非數(shù)值字符的下標(biāo)，默認(rèn)是0。返回float
stod(s, p)	返回double
stold(s, p)	返回long double

容器適配器（adapter）

• 適配器是使一事物的行為類似于另一事物的行為的一種機(jī)制，例如stack可以使任何一種順序容器以棧的方式工作。

• 初始化 deque<int> deq; stack<int> stk(deq); 從deq拷貝元素到stk。

• 創(chuàng)建適配器時(shí)，指定一個(gè)順序容器，可以覆蓋默認(rèn)的基礎(chǔ)容器： stack<string, vector<string> > str_stk;。

適配器的通用操作和類型

操作解釋

size_type	一種類型，須以保存當(dāng)前類型的最大對象的大小
value_type	元素類型
container_type	實(shí)現(xiàn)適配器的底層容器類型
A a;	創(chuàng)建一個(gè)名為a的空適配器
A a(c)	創(chuàng)建一個(gè)名為a的適配器，帶有容器c的一個(gè)拷貝
關(guān)系運(yùn)算符	每個(gè)適配器都支持所有關(guān)系運(yùn)算符：==、!=、<、 <=、>、>=這些運(yùn)算符返回底層容器的比較結(jié)果
a.empty()	若a包含任何元素，返回false;否則返回true
a.size()	返回a中的元素?cái)?shù)目
swap(a, b)	交換a和b的內(nèi)容，a和b必須有相同類型，包括底層容器類型也必須相同
a.swap(b)	同上

stack

操作解釋

s.pop()	刪除棧頂元素，不返回。
s.push(item)	創(chuàng)建一個(gè)新元素，壓入棧頂，該元素通過拷貝或移動(dòng)item而來
s.emplace(args)	同上，但元素由args來構(gòu)造。
s.top()	返回棧頂元素，不刪除。

• 定義在stack頭文件中。

• stack默認(rèn)基于deque實(shí)現(xiàn)，也可以在list或vector之上實(shí)現(xiàn)。

queue和priority_queue

操作解釋

q.pop()	刪除隊(duì)首元素，但不返回。
q.front()	返回隊(duì)首元素的值，不刪除。
q.back()	返回隊(duì)尾元素的值，不刪除。只適用于queue
q.top()	返回具有最高優(yōu)先級的元素值，不刪除。
q.push(item)	在隊(duì)尾壓入一個(gè)新元素。
q.emplace(args)

• 定義在queue頭文件中。

• queue默認(rèn)基于deque實(shí)現(xiàn)，priority_queue默認(rèn)基于vector實(shí)現(xiàn)。

• queue可以在list或vector之上實(shí)現(xiàn)，priority_queue也可以用deque實(shí)現(xiàn)。

第十章 泛型算法

泛型算法

• 因?yàn)樗鼈儗?shí)現(xiàn)共同的操作，所以稱之為“算法”；而“泛型”、指的是它們可以操作在多種容器類型上。

• 泛型算法本身不執(zhí)行容器操作，只是單獨(dú)依賴迭代器和迭代器操作實(shí)現(xiàn)。

• 頭文件： #include <algorithm>或者 #include <numeric>(算數(shù)相關(guān))

• 大多數(shù)算法是通過遍歷兩個(gè)迭代器標(biāo)記的一段元素來實(shí)現(xiàn)其功能。

• 必要的編程假定：算法永遠(yuǎn)不會改變底層容器的大小。算法可能改變?nèi)萜髦斜４娴脑氐闹?#xff0c;也可能在容器內(nèi)移動(dòng)元素，但不能直接添加或者刪除元素。

find

• vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);

• 輸入：兩個(gè)標(biāo)記范圍的迭代器和目標(biāo)查找值。返回：如果找到，返回對應(yīng)的迭代器，否則返回第二個(gè)參數(shù)，即標(biāo)記結(jié)尾的迭代器。

初識泛型算法

• 標(biāo)準(zhǔn)庫提供了超過100個(gè)算法，但這些算法有一致的結(jié)構(gòu)。

• 理解算法的最基本的方法是了解它們是否讀取元素、改變元素、重排元素順序。

只讀算法

• 只讀取范圍中的元素，不改變元素。

• 如 find和 accumulate（在numeric中定義，求和）。

• find_first_of，輸入：兩對迭代器標(biāo)記兩段范圍，在第一段中找第二段中任意元素，返回第一個(gè)匹配的元素，找不到返回第一段的end迭代器。

• 通常最好使用cbegin和cend。

• equal：確定兩個(gè)序列是否保存相同的值。

寫容器元素的算法

• 一些算法將新值賦予序列中的元素。

• 算法不檢查寫操作。

• fill： fill(vec.begin(), vec.end(), 0); 將每個(gè)元素重置為0

• fill_n： fill_n(vec.begin(), 10, 0);

• 插入迭代器back_inserter：

  • 用來確保算法有足夠的空間存儲數(shù)據(jù)。

  • #include <iterator>

  • back_inserter(vec)

• 拷貝算法copy：

• 輸入：前兩個(gè)參數(shù)指定輸入范圍，第三個(gè)指向目標(biāo)序列。

• copy (ilst.begin(), ilst.end(), back_inserter(ivec));

• copy時(shí)必須保證目標(biāo)目的序列至少要包含與輸入序列一樣多的元素。

重排容器元素的算法

• 這些算法會重排容器中元素的順序。

• 排序算法sort：

  • 接受兩個(gè)迭代器，表示要排序的元素范圍。

• 消除重復(fù)unique：

  • 之前要先調(diào)用sort

  • 返回的迭代器指向最后一個(gè)不重復(fù)元素之后的位置。

  • 順序會變，重復(fù)的元素被“刪除”。

  • 并沒有真正刪除，真正刪除必須使用容器操作。

定制操作

向算法傳遞函數(shù)：

• 謂詞（predicate）：

  • 是一個(gè)可調(diào)用的表達(dá)式，返回結(jié)果是一個(gè)能用作條件的值

  • 一元謂詞：接受一個(gè)參數(shù)

  • 二元謂詞：接受兩個(gè)參數(shù)

• 例子：

  • stable_sort：

    • 保留相等元素的原始相對位置。

    • stable_sort(words.begin(), words.end(), isShorter);

lambda表達(dá)式

• 有時(shí)可能希望操作可以接受更多的參數(shù)。

• lambda表達(dá)式表示一個(gè)可調(diào)用的代碼單元，可以理解成是一個(gè)未命名的內(nèi)聯(lián)函數(shù)。

• 形式：[capture list](parameter list) -> return type {function body}。

  • 其中capture list捕獲列表是一個(gè)lambda所在函數(shù)定義的局部變量的列表（通常為空）。不可忽略。

  • return type是返回類型。可忽略。

  • parameter是參數(shù)列表。可忽略。

  • function body是函數(shù)體。不可忽略。

  • auto f = [] {return 42;}

• 例子：

  • find_if:

    • 接受一對表示范圍的迭代器和一個(gè)謂詞，用來查找第一個(gè)滿足特定要求的元素。返回第一個(gè)使謂詞返回非0值的元素。

    • auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});

  • for_each：

    • 接受一個(gè)可調(diào)用對象，并對序列中每個(gè)元素調(diào)用此對象。

    • for_each(wc, words.end(), [](const string &s){cout << s << " ";})

lambda捕獲和返回

• 定義lambda時(shí)會生成一個(gè)新的類類型和該類型的一個(gè)對象。

• 默認(rèn)情況下，從lambda生成的類都包含一個(gè)對應(yīng)該lambda所捕獲的變量的數(shù)據(jù)成員，在lambda對象創(chuàng)建時(shí)被初始化。

• 值捕獲：前提是變量可以拷貝，size_t v1 = 42; auto f = [v1] {return v1;};。

• 引用捕獲：必須保證在lambda執(zhí)行時(shí)，變量是存在的，auto f2 = [&v1] {return v1;};

• 盡量減少捕獲的數(shù)據(jù)量，盡可能避免捕獲指針或引用。

• 隱式捕獲：讓編譯器推斷捕獲列表，在捕獲列表中寫一個(gè)&（引用方式）或=（值方式）。auto f3 = [=] {return v1;}

lambda捕獲列表：

捕獲列表解釋

[]	空捕獲列表。lambda不能使用所在函數(shù)中的變量。一個(gè)lambda只有在捕獲變量后才能使用它們。
[names]	names是一個(gè)逗號分隔的名字列表，這些名字都是在lambda所在函數(shù)的局部變量，捕獲列表中的變量都被拷貝，名字前如果使用了&，則采用引用捕獲方式。
[&]	隱式捕獲列表，采用引用捕獲方式。lambda體中所使用的來自所在函數(shù)的實(shí)體都采用引用方式使用。
[=]	隱式捕獲列表，采用值捕獲方式。
[&, identifier_list]	identifier_list是一個(gè)逗號分隔的列表，包含0個(gè)或多個(gè)來自所在函數(shù)的變量。這些變量采用值捕獲方式，而任何隱式捕獲的變量都采用引用方式捕獲。identifier_list中的名字前面不能使用&
[=, identifier_list]	identifier_list中的變量采用引用方式捕獲，而任何隱式捕獲的變量都采用值方式捕獲。identifier_list中的名字不能包括this，且前面必須使用&

參數(shù)綁定

• lambda表達(dá)式更適合在一兩個(gè)地方使用的簡單操作。

• 如果是很多地方使用相同的操作，還是需要定義函數(shù)。

• 函數(shù)如何包裝成一元謂詞？使用參數(shù)綁定。

• 標(biāo)準(zhǔn)庫bind函數(shù)：

  • 定義在頭文件functional中，可以看做為一個(gè)通用的函數(shù)適配器。

  • auto newCallable = bind(callable, arg_list);

  • 我們再調(diào)用newCallable的時(shí)候，newCallable會調(diào)用callable并傳遞給它arg_list中的參數(shù)。

  • _n代表第n個(gè)位置的參數(shù)。定義在placeholders的命名空間中。using std::placeholder::_1;

  • auto g = bind(f, a, b, _2, c, _1);，調(diào)用g(_1, _2)實(shí)際上調(diào)用f(a, b, _2, c, _1)

  • 非占位符的參數(shù)要使用引用傳參，必須使用標(biāo)準(zhǔn)庫ref函數(shù)或者cref函數(shù)。

再探迭代器

插入迭代器

• 插入器是一種迭代器適配器，接受一個(gè)容器，生成一個(gè)迭代器，能實(shí)現(xiàn)向給定容器添加元素。

• 三種類型：

  • back_inserter：創(chuàng)建一個(gè)使用push_back的迭代器。

  • front_inserter創(chuàng)建一個(gè)使用push_front的迭代器。

  • inserter創(chuàng)建一個(gè)使用insert的迭代器。接受第二個(gè)參數(shù)，即一個(gè)指向給定容器的迭代器，元素會被查到迭代器所指向的元素之前。

插入迭代器操作：

操作解釋

it=t	在it指定的當(dāng)前位置插入值t。假定c是it綁定的容器，依賴于插入迭代器的不同種類，此賦值會分別調(diào)用c.push_back(t)、c.push_front(t)、c.insert(t, p)，其中p是傳遞給inserter的迭代器位置
*it, ++it, it++	這些操作雖然存在，但不會對it做任何事情，每個(gè)操作都返回it

iostream迭代器

• 迭代器可與輸入或輸出流綁定在一起，用于迭代遍歷所關(guān)聯(lián)的 IO 流。

• 通過使用流迭代器，我們可以用泛型算法從流對象中讀取數(shù)據(jù)以及向其寫入數(shù)據(jù)。

istream_iterator的操作：

操作解釋

istream_iterator<T> in(is);	in從輸入流is讀取類型為T的值
istream_iterator<T> end;	讀取類型是T的值的istream_iterator迭代器，表示尾后位置
in1 == in2	in1和in2必須讀取相同類型。如果他們都是尾后迭代器，或綁定到相同的輸入，則兩者相等。
in1 != in2	類似上條
*in	返回從流中讀取的值
in->mem	與*(in).mem含義相同
++in, in++	使用元素類型所定義的>>運(yùn)算符從流中讀取下一個(gè)值。前置版本返回一個(gè)指向遞增后迭代器的引用，后置版本返回舊值。

ostream_iterator的操作：

操作解釋

ostream_iterator<T> out(os);	out將類型為T的值寫到輸出流os中
ostream_iterator<T> out(os, d);	out將類型為T的值寫到輸出流os中，每個(gè)值后面都輸出一個(gè)d。d指向一個(gè)空字符結(jié)尾的字符數(shù)組。
out = val	用<<運(yùn)算符將val寫入到out所綁定的ostream中。val的類型必須和out可寫的類型兼容。
*out, ++out, out++	這些運(yùn)算符是存在的，但不對out做任何事情。每個(gè)運(yùn)算符都返回out。

反向迭代器

• 反向迭代器就是在容器中從尾元素向首元素反向移動(dòng)的迭代器。

• 對于反向迭代器，遞增和遞減的操作含義會顛倒。

• 實(shí)現(xiàn)向后遍歷，配合rbegin和rend。

泛型算法結(jié)構(gòu)

5類迭代器

迭代器類別解釋支持的操作

輸入迭代器	只讀，不寫；單遍掃描，只能遞增	==,!=,++,*,->
輸出迭代器	只寫，不讀；單遍掃描，只能遞增	++,*
前向迭代器	可讀寫；多遍掃描，只能遞增	==,!=,++,*,->
雙向迭代器	可讀寫；多遍掃描，可遞增遞減	==,!=,++,--,*,->
隨機(jī)訪問迭代器	可讀寫，多遍掃描，支持全部迭代器運(yùn)算	==,!=,<,<=,>,>=,++,--,+,+=,-,-=,*,->,iter[n]==*(iter[n])

算法的形參模式

• alg(beg, end, other args);

• alg(beg, end, dest, other args);

• alg(beg, end, beg2, other args);

• alg(beg, end, beg2, end2, other args);

其中，alg是算法名稱，beg和end表示算法所操作的輸入范圍。dest、beg2、end2都是迭代器參數(shù)，是否使用要依賴于執(zhí)行的操作。

算法命名規(guī)范

• 一些算法使用重載形式傳遞一個(gè)謂詞。

• 接受一個(gè)元素值的算法通常有一個(gè)不同名的版本：加_if，接受一個(gè)謂詞代替元素值。

• 區(qū)分拷貝元素的版本和不拷貝的版本：拷貝版本通常加_copy。

特定容器算法

• 對于list和forward_list，優(yōu)先使用成員函數(shù)版本的算法而不是通用算法。

list和forward_list成員函數(shù)版本的算法：

操作解釋

lst.merge(lst2)	將來自lst2的元素合并入lst，二者都必須是有序的，元素將從lst2中刪除。
lst.merge(lst2, comp)	同上，給定比較操作。
lst.remove(val)	調(diào)用erase刪除掉與給定值相等(==)的每個(gè)元素
lst.remove_if(pred)	調(diào)用erase刪除掉令一元謂詞為真的每個(gè)元素
lst.reverse()	反轉(zhuǎn)lst中元素的順序
lst.sort()	使用<排序元素
lst.sort(comp)	使用給定比較操作排序元素
lst.unique()	調(diào)用erase刪除同一個(gè)值的連續(xù)拷貝。使用==。
lst.unique(pred)	調(diào)用erase刪除同一個(gè)值的連續(xù)拷貝。使用給定的二元謂詞。

• 上面的操作都返回void

list和forward_list的splice成員函數(shù)版本的參數(shù)：

參數(shù)解釋

(p, lst2)	p是一個(gè)指向lst中元素的迭代器，或者一個(gè)指向flst首前位置的迭代器。函數(shù)將lst2中的所有元素移動(dòng)到lst中p之前的位置或是flst中p之后的位置。將元素從lst2中刪除。lst2的類型必須和lst相同，而且不能是同一個(gè)鏈表。
(p, lst2, p2)	同上，p2是一個(gè)指向lst2中位置的有效的迭代器，將p2指向的元素移動(dòng)到lst中，或?qū)2之后的元素移動(dòng)到flst中。lst2可以是于lst或flst相同的鏈表。
(p, lst2, b, e)	b和e表示lst2中的合法范圍。將給定范圍中的元素從lst2移動(dòng)到lst或first中。lst2與lst可以使相同的鏈表，但p不能指向給定范圍中的元素。

• 使用lst.splice(args)或flst.splice_after(args)

第十一章 關(guān)聯(lián)容器

• 關(guān)聯(lián)容器和順序容器的不同：關(guān)聯(lián)容器中的元素時(shí)按照關(guān)鍵字來保存和訪問的。

• 關(guān)聯(lián)容器支持通過關(guān)鍵字來高效地查找和讀取元素，基本的關(guān)聯(lián)容器類型是 map和 set。

關(guān)聯(lián)容器類型：

容器類型解釋

按順序存儲
map	關(guān)鍵數(shù)組：保存關(guān)鍵字-值對
set	關(guān)鍵字即值，即只保存關(guān)鍵字的容器
multimap	支持同一個(gè)鍵多次出現(xiàn)的map
multiset	支持同一個(gè)鍵多次出現(xiàn)的set
無序集合
unordered_map	用哈希函數(shù)組織的map
unordered_set	用哈希函數(shù)組織的set
unordered_multimap	哈希組織的map，關(guān)鍵字可以重復(fù)出現(xiàn)
unordered_multiset	哈希組織的set，關(guān)鍵字可以重復(fù)出現(xiàn)

關(guān)聯(lián)容器概述

定義關(guān)聯(lián)容器

• 需要指定元素類型。

• 列表初始化：

  • map：map<string, int> word_count = {{"a", 1}, {"b", 2}};

  • set：set<string> exclude = {"the", "a"};

關(guān)鍵字類型的要求

• 對于有序容器，關(guān)鍵字類型必須定義元素比較的方法。默認(rèn)是<。

• 如果想傳遞一個(gè)比較的函數(shù)，可以這樣定義：multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

pair

• 在utility頭文件中定義。

• 一個(gè)pair保存兩個(gè)數(shù)據(jù)成員，兩個(gè)類型不要求一樣。

pair的操作：

操作解釋

pair<T1, T2> p;	p是一個(gè)pair，兩個(gè)類型分別是T1和T2的成員都進(jìn)行了值初始化。
pair<T1, T2> p(v1, v2);	first和second分別用v1和v2進(jìn)行初始化。
pair<T1, T2>p = {v1, v2};	等價(jià)于`p(v1, v2)
make_pair(v1, v2);	pair的類型從v1和v2的類型推斷出來。
p.first	返回p的名為first的數(shù)據(jù)成員。
p.second	返回p的名為second的數(shù)據(jù)成員。
p1 relop p2	運(yùn)算關(guān)系符按字典序定義。
p1 == p2	必須兩對元素兩兩相等
p1 != p2	同上

關(guān)聯(lián)容器操作

關(guān)聯(lián)容器額外的類型別名：

類型別名解釋

key_type	此容器類型的關(guān)鍵字類型
mapped_type	每個(gè)關(guān)鍵字關(guān)聯(lián)的類型，只適用于map
value_type	對于map，是pair<const key_type, mapped_type>; 對于set，和key_type相同。

關(guān)聯(lián)容器迭代器

• 解引用一個(gè)關(guān)聯(lián)容器迭代器時(shí)，會得到一個(gè)類型為容器的value_type的值的引用。

• set的迭代器是const的。

• 遍歷關(guān)聯(lián)容器：使用begin和end，遍歷map、multimap、set、multiset時(shí)，迭代器按關(guān)鍵字升序遍歷元素。

添加元素

關(guān)聯(lián)容器insert操作：

insert操作關(guān)聯(lián)容器

c.insert(v) c.emplace(args)	v是value_type類型的對象；args用來構(gòu)造一個(gè)元素。 對于map和set，只有元素的關(guān)鍵字不存在c中才插入或構(gòu)造元素。函數(shù)返回一個(gè)pair，包含一個(gè)迭代器，指向具有指定關(guān)鍵字的元素，以及一個(gè)指示插入是否成功的bool值。對于multimap和multiset則會插入范圍中的每個(gè)元素。
c.insert(b, e) c.insert(il)	b和e是迭代器，表示一個(gè)c::value_type類型值的范圍；il是這種值的花括號列表。函數(shù)返回void。對于 map和set，只插入關(guān)鍵字不在c中的元素。
c.insert(p, v) c.emplace(p, args)	類似insert(v)，但將迭代器p作為一個(gè)提示，指出從哪里開始搜索新元素應(yīng)該存儲的位置。返回一個(gè)迭代器，指向具有給定關(guān)鍵字的元素。

向map添加元素：

• word_count.insert({word, 1});

• word_count.insert(make_pair(word, 1));

• word_count.insert(pair<string, size_t>(word, 1));

• word_count.insert(map<string, size_t>::value_type (word, 1));

刪除元素

從關(guān)聯(lián)容器中刪除元素：

操作解釋

c.erase(k)	從c中刪除每個(gè)關(guān)鍵字為k的元素。返回一個(gè)size_type值，指出刪除的元素的數(shù)量。
c.erase(p)	從c中刪除迭代器p指定的元素。p必須指向c中一個(gè)真實(shí)元素，不能等于c.end()。返回一個(gè)指向p之后元素的迭代器，若p指向c中的尾元素，則返回c.end()
c.erase(b, e)	刪除迭代器對b和e所表示范圍中的元素。返回e。

下標(biāo)操作

map和unordered_map的下標(biāo)操作：

操作解釋

c[k]	返回關(guān)鍵字為k的元素；如果k不在c中，添加一個(gè)關(guān)鍵字為k的元素，對其值初始化。
c.at(k)	訪問關(guān)鍵字為k的元素，帶參數(shù)檢查；若k不存在在c中，拋出一個(gè)out_of_range異常。

查找元素

在一個(gè)關(guān)聯(lián)容器中查找元素:

操作解釋

c.find(k)	返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字為k的元素，若k不在容器中，則返回尾后迭代器
c.count(k)	返回關(guān)鍵字等于k的元素的數(shù)量。對于不允許重復(fù)關(guān)鍵字的容器，返回值永遠(yuǎn)是0或1。
c.lower_bound(k)	返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字不小于k的元素。
c.upper_bound(k)	返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字大于k的元素。
c.equal_range(k)	返回一個(gè)迭代器pair，表示關(guān)鍵字等于k的元素的范圍。若k不存在，pair的兩個(gè)成員均等于c.end()。

• lower_bound和upper_bound不適用于無序容器。

• 下標(biāo)和at操作只適用于非const的map和unordered_map。

無序容器

• 有序容器使用比較運(yùn)算符來組織元素；無序容器使用哈希函數(shù)和關(guān)鍵字類型的==運(yùn)算符。

• 理論上哈希技術(shù)可以獲得更好的性能。

• 無序容器在存儲上組織為一組桶(bucket)，每個(gè)桶保存零個(gè)或多個(gè)元素。無序容器使用一個(gè)哈希函數(shù)將元素映射到桶。

無序容器管理操作：

操作解釋

桶接口
c.bucket_count()	正在使用的桶的數(shù)目
c.max_bucket_count()	容器能容納的最多的桶的數(shù)目
c.bucket_size(n)	第n個(gè)桶中有多少個(gè)元素
c.bucket(k)	關(guān)鍵字為k的元素在哪個(gè)桶中
桶迭代
local_iterator	可以用來訪問桶中元素的迭代器類型
const_local_iterator	桶迭代器的const版本
c.begin(n)，c.end(n)	桶n的首元素迭代器
c.cbegin(n)，c.cend(n)	與前兩個(gè)函數(shù)類似，但返回const_local_iterator。
哈希策略
c.load_factor()	每個(gè)桶的平均元素?cái)?shù)量，返回float值。
c.max_load_factor()	c試圖維護(hù)的平均比桶大小，返回float值。c會在需要時(shí)添加新的桶，以使得load_factor<=max_load_factor
c.rehash(n)	重組存儲，使得bucket_count>=n，且bucket_count>size/max_load_factor
c.reverse(n)	重組存儲，使得c可以保存n個(gè)元素且不必rehash。

第十二章 動(dòng)態(tài)內(nèi)存

• 對象的生命周期：

  • 全局對象在程序啟動(dòng)時(shí)分配，結(jié)束時(shí)銷毀。

  • 局部對象在進(jìn)入程序塊時(shí)創(chuàng)建，離開塊時(shí)銷毀。

  • 局部static對象在第一次使用前分配，在程序結(jié)束時(shí)銷毀。

  • 動(dòng)態(tài)分配對象：只能顯式地被釋放。

• 對象的內(nèi)存位置：

  • 靜態(tài)內(nèi)存用來保存局部static對象、類static對象、定義在任何函數(shù)之外的變量。

  • 棧內(nèi)存用來保存定義在函數(shù)內(nèi)的非static對象。

  • 堆內(nèi)存，又稱自由空間，用來存儲動(dòng)態(tài)分配的對象。

動(dòng)態(tài)內(nèi)存與智能指針

• 動(dòng)態(tài)內(nèi)存管理：

  • new：在動(dòng)態(tài)內(nèi)存中為對象分配空間并返回一個(gè)指向該對象的指針。

  • delete：接受一個(gè)動(dòng)態(tài)對象的指針，銷毀該對象，并釋放與之關(guān)聯(lián)的內(nèi)存。

• 智能指針：

  • 管理動(dòng)態(tài)對象。

  • 行為類似常規(guī)指針。

  • 負(fù)責(zé)自動(dòng)釋放所指向的對象。

  • 智能指針也是模板。

shared_ptr類

shared_ptr和unique_ptr都支持的操作：

操作解釋

shared_ptr<T> sp unique_ptr<T> up	空智能指針，可以指向類型是T的對象
p	將p用作一個(gè)條件判斷，若p指向一個(gè)對象，則為true
*p	解引用p，獲得它指向的對象。
p->mem	等價(jià)于(*p).mem
p.get()	返回p中保存的指針，要小心使用，若智能指針釋放了對象，返回的指針?biāo)赶虻膶ο笠簿拖Я恕?/td>
swap(p, q) p.swap(q)	交換p和q中的指針

shared_ptr獨(dú)有的操作：

操作解釋

make_shared<T>(args)	返回一個(gè)shared_ptr，指向一個(gè)動(dòng)態(tài)分配的類型為T的對象。使用args初始化此對象。
shared_ptr<T>p(q)	p是shared_ptr q的拷貝；此操作會遞增q中的計(jì)數(shù)器。q中的指針必須能轉(zhuǎn)換為T*
p = q	p和q都是shared_ptr，所保存的指針必須能互相轉(zhuǎn)換。此操作會遞減p的引用計(jì)數(shù)，遞增q的引用計(jì)數(shù)；若p的引用計(jì)數(shù)變?yōu)?，則將其管理的原內(nèi)存釋放。
p.unique()	若p.use_count()是1，返回true；否則返回false
p.use_count()	返回與p共享對象的智能指針數(shù)量；可能很慢，主要用于調(diào)試。

• 使用動(dòng)態(tài)內(nèi)存的三種原因：

  • 程序不知道自己需要使用多少對象（比如容器類）。

  • 程序不知道所需要對象的準(zhǔn)確類型。

  • 程序需要在多個(gè)對象間共享數(shù)據(jù)。

直接管理內(nèi)存

• 用new動(dòng)態(tài)分配和初始化對象。

  • new無法為分配的對象命名（因?yàn)樽杂煽臻g分配的內(nèi)存是無名的），因此是返回一個(gè)指向該對象的指針。

  • int *pi = new int(123);

  • 一旦內(nèi)存耗盡，會拋出類型是bad_alloc的異常。

• 用delete將動(dòng)態(tài)內(nèi)存歸還給系統(tǒng)。

  • 接受一個(gè)指針，指向要釋放的對象。

  • delete后的指針稱為空懸指針（dangling pointer）。

• 使用new和delete管理動(dòng)態(tài)內(nèi)存存在三個(gè)常見問題：

  • 1.忘記delete內(nèi)存。

  • 2.使用已經(jīng)釋放掉的對象。

  • 3.同一塊內(nèi)存釋放兩次。

• 堅(jiān)持只使用智能指針可以避免上述所有問題。

shared_ptr和new結(jié)合使用

定義和改變shared_ptr的其他方法：

操作解釋

shared_ptr<T> p(q)	p管理內(nèi)置指針q所指向的對象；q必須指向new分配的內(nèi)存，且能夠轉(zhuǎn)換為T*類型
shared_ptr<T> p(u)	p從unique_ptr u那里接管了對象的所有權(quán)；將u置為空
shared_ptr<T> p(q, d)	p接管了內(nèi)置指針q所指向的對象的所有權(quán)。q必須能轉(zhuǎn)換為T*類型。p將使用可調(diào)用對象d來代替delete。
shared_ptr<T> p(p2, d)	p是shared_ptr p2的拷貝，唯一的區(qū)別是p將可調(diào)用對象d來代替delete。
p.reset()	若p是唯一指向其對象的shared_ptr，reset會釋放此對象。若傳遞了可選的參數(shù)內(nèi)置指針q，會令p指向q，否則會將p置空。若還傳遞了參數(shù)d，則會調(diào)用d而不是delete來釋放q。
p.reset(q)	同上
p.reset(q, d)	同上

智能指針和異常

• 如果使用智能指針，即使程序塊由于異常過早結(jié)束，智能指針類也能確保在內(nèi)存不需要的時(shí)候?qū)⑵溽尫拧?/p>

• 智能指針陷阱：

  • 不用相同的內(nèi)置指針初始化（或reset）多個(gè)智能指針

  • 不delete get()返回的指針。

  • 如果你使用get()返回的指針，記得當(dāng)最后一個(gè)對應(yīng)的智能指針銷毀后，你的指針就無效了。

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

unique_ptr

• 某一個(gè)時(shí)刻只能有一個(gè)unique_ptr指向一個(gè)給定的對象。

• 不支持拷貝或者賦值操作。

• 向后兼容：auto_ptr：老版本，具有unique_ptr的部分特性。特別是，不能在容器中保存auto_ptr，也不能從函數(shù)返回auto_ptr。

unique_ptr操作:

操作解釋

unique_ptr<T> u1	空unique_ptr，可以指向類型是T的對象。u1會使用delete來是釋放它的指針。
unique_ptr<T, D> u2	u2會使用一個(gè)類型為D的可調(diào)用對象來釋放它的指針。
unique_ptr<T, D> u(d)	空unique_ptr，指向類型為T的對象，用類型為D的對象d代替delete
u = nullptr	釋放u指向的對象，將u置為空。
u.release()	u放棄對指針的控制權(quán)，返回指針，并將u置空。
u.reset()	釋放u指向的對象
u.reset(q)	令u指向q指向的對象
u.reset(nullptr)	將u置空

weak_ptr

• weak_ptr是一種不控制所指向?qū)ο笊嫫诘闹悄苤羔槨?/p>

• 指向一個(gè)由shared_ptr管理的對象，不改變shared_ptr的引用計(jì)數(shù)。

• 一旦最后一個(gè)指向?qū)ο蟮膕hared_ptr被銷毀，對象就會被釋放，不管有沒有weak_ptr指向該對象。

weak_ptr操作:

操作解釋

weak_ptr<T> w	空weak_ptr可以指向類型為T的對象
weak_ptr<T> w(sp)	與shared_ptr指向相同對象的weak_ptr。T必須能轉(zhuǎn)換為sp指向的類型。
w = p	p可以是shared_ptr或一個(gè)weak_ptr。賦值后w和p共享對象。
w.reset()	將w置為空。
w.use_count()	與w共享對象的shared_ptr的數(shù)量。
w.expired()	若w.use_count()為0，返回true，否則返回false
w.lock()	如果expired為true，則返回一個(gè)空shared_ptr；否則返回一個(gè)指向w的對象的shared_ptr。

動(dòng)態(tài)數(shù)組

new和數(shù)組

• new一個(gè)動(dòng)態(tài)數(shù)組：

  • 類型名之后加一對方括號，指明分配的對象數(shù)目（必須是整型，不必是常量）。

  • 返回指向第一個(gè)對象的指針。

  • int *p = new int[size];

• delete一個(gè)動(dòng)態(tài)數(shù)組：

  • delete [] p;

• unique_ptr和數(shù)組：

  • 指向數(shù)組的unique_ptr不支持成員訪問運(yùn)算符（點(diǎn)和箭頭）。

操作解釋

unique_ptr<T[]> u	u可以指向一個(gè)動(dòng)態(tài)分配的數(shù)組，整數(shù)元素類型為T
unique_ptr<T[]> u(p)	u指向內(nèi)置指針p所指向的動(dòng)態(tài)分配的數(shù)組。p必須能轉(zhuǎn)換為類型T*。
u[i]	返回u擁有的數(shù)組中位置i處的對象。u必須指向一個(gè)數(shù)組。

allocator類

• 標(biāo)準(zhǔn)庫allocator類定義在頭文件memory中，幫助我們將內(nèi)存分配和對象構(gòu)造分離開。

• 分配的是原始的、未構(gòu)造的內(nèi)存。

• allocator是一個(gè)模板。

• allocator<string> alloc;

標(biāo)準(zhǔn)庫allocator類及其算法：

操作解釋

allocator<T> a	定義了一個(gè)名為a的allocator對象，它可以為類型為T的對象分配內(nèi)存
a.allocate(n)	分配一段原始的、未構(gòu)造的內(nèi)存，保存n個(gè)類型為T的對象。
a.deallocate(p, n)	釋放從T*指針p中地址開始的內(nèi)存，這塊內(nèi)存保存了n個(gè)類型為T的對象；p必須是一個(gè)先前由allocate返回的指針。且n必須是p創(chuàng)建時(shí)所要求的大小。在調(diào)用deallocate之前，用戶必須對每個(gè)在這塊內(nèi)存中創(chuàng)建的對象調(diào)用destroy。
a.construct(p, args)	p必須是一個(gè)類型是T*的指針，指向一塊原始內(nèi)存；args被傳遞給類型為T的構(gòu)造函數(shù)，用來在p指向的內(nèi)存中構(gòu)造一個(gè)對象。
a.destroy(p)	p為T*類型的指針，此算法對p指向的對象執(zhí)行析構(gòu)函數(shù)。

allocator伴隨算法：

操作解釋

uninitialized_copy(b, e, b2)	從迭代器b和e給定的輸入范圍中拷貝元素到迭代器b2指定的未構(gòu)造的原始內(nèi)存中。b2指向的內(nèi)存必須足夠大，能夠容納輸入序列中元素的拷貝。
uninitialized_copy_n(b, n, b2)	從迭代器b指向的元素開始，拷貝n個(gè)元素到b2開始的內(nèi)存中。
uninitialized_fill(b, e, t)	在迭代器b和e執(zhí)行的原始內(nèi)存范圍中創(chuàng)建對象，對象的值均為t的拷貝。
uninitialized_fill_n(b, n, t)	從迭代器b指向的內(nèi)存地址開始創(chuàng)建n個(gè)對象。b必須指向足夠大的未構(gòu)造的原始內(nèi)存，能夠容納給定數(shù)量的對象。

• 定義在頭文件memory中。

• 在給定目的位置創(chuàng)建元素，而不是由系統(tǒng)分配內(nèi)存給他們。

?

總結(jié)

以上是生活随笔為你收集整理的CppPrimer学习笔记（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。