C++自修入門實境秀、C++ Primer 5版研讀秀 93/ ~12.3.1. Design of the Query Program~練習1...

頁425

約是第93集起，之前一起讀懂實境秀當掉沒錄到，可見臉書直播466集： https://www.facebook.com/oscarsun72/videos/2526965857414533



Key Types for Ordered Containers

有序容器鍵值型別的特徵

就像可以提供我們自定義的比對運算給演算法運用一樣（§10.3，頁385），我們也可以提供我們自己對於鍵值的比對運算來取代程式庫預設用上的小於運算子「＜」。這種取代的自訂運算必須對這個鍵值型別定義一個嚴格的弱次序（strict weak ordering，【就是弱小的放前面的意思，愈小的放愈前面，且小的不能變大，原來放在前面的不能又變成放在後面就是了 https://www.boost.org/sgi/stl/StrictWeakOrdering.html 】）。即便我們要用到的可呼叫物件或函式可能會很複雜，我們仍然可以把「嚴格的弱次序」想成「小於」這樣的關係。在自行定義這樣的比對運算（函式）時就必須遵守以下的規則（這些規則就是所謂的「嚴格的弱次序」規則）：

 兩個鍵值不能同時小於彼此；也就是說，如果k1小於k2，那麼k2就決定不能也小於k1。

 如果k1小於k2而且k2小於k3，那麼k1就一定要小於k3。

 如果兩個鍵值彼此都不小於對方，那麼就必須斷定這兩個鍵值是相等的（“equivalent”）。如果k1等於k2而且k2等於k3，那麼k1就一定要等於k3。【以上就叫「嚴格的弱次序（strict weak ordering）」】

如果兩個鍵值彼此相等（也就是說彼此都不會小於對方）那麼用到這樣型別的作為鍵值的容器就會將此二者視為等值。當以這樣的型別作為map容器的鍵值時，有而且只有一個元素可以對應到這樣等值的鍵值，且這些等值鍵值，隨取一個（either key），都能用來存取它所對應到的「值」。

注意：

在實務上，只要一個類別（type）對小於運算子有所定義，且符合了嚴格的弱次序（defines a ＜ operator that "behaves normally"），就能用來作為鍵值的型別。38:30

The specified operation must define a strict weak ordering over the key type.

嚴格的弱次序（strict weak ordering）

→由下文 上下文（前後文） 判斷，應翻成：絕對的等差級別、確定的大小次序。weak就是「＜」.

只要一個型別定義了有序的正常表現的、有規則的、嚴謹的小於運算子「＜」，就可以用來作為鍵值（型別）

Using a Comparison Function for the Key Type

使用了自定義比較運算（comparison function）的鍵值型別

容器用以安排（組織，organize）它元素的依據運算，其型別是作為此容器型別的一部分而存在的。

The type of the operation that a container uses to organize its elements is part of the type of that container.

要用上我們對元素自定義的運算，就必須在定義一個關聯式容器時指明我們這個運算的型別是什麼。這個運算型別是在定義一個容器物件時接在元素型別後指出的，和元素型別都包在那對的角括弧（angle brackets）中的。【前面是宣告、定義容器物件，指出我們需要的是怎樣的一個容器；後面則是對這樣的容器來建構與初始化】在定義容器時用上的角括弧，其中的每個型別就是一個型別，所以當實際建構（create創建）這個容器物件時，我們就必須提供一個符合在宣告或定義這個容器時所指明的那種型別的自定義比較運算，來給建構此容器的建構器用。【意思也就是關聯式容器的建構器，有一種是接受我們在宣告、定義時提供的那種運算型別來作為它第2個引數來傳入的】

舉例來說，我們不能直接以Sales_data作為元素來定義出一個的multiset這樣的關聯式容器，因為Sales_date類別並沒有小於運算子「＜」【對小於運算子未作定義】。雖然如此，但我們卻可以藉由從§10.3.1（頁387、431、446）定義出來的compareIsbn函式來定義我們所要的以Sales_data為元素的multiset。因為那個compareIsbn函式是就已知的兩個Sales_data，針對它們的ISBN書號，實作出了符合嚴格的弱次序（strict weak ordering）的比較運算。這個compareIsbn函式的內容就像這樣：

只要函式定義了某型別嚴格的大小次序（strict weak ordering），就能用來作為建構關聯式容器的引數。第93集 1:54:02 前面許多時間軸標記已經死掉，因為電腦當掉了。

頁426

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)

{

return lhs.isbn() ＜ rhs.isbn();

}

為了要用上我們自定義的比較運算，我們在定義這個multiset容器時就必須同時提供兩個型別：一個是鍵值的型別，在這裡也就是Sales_data，一個則是比較運算用的型別，在這裡就是函式指標（function pointer）型別（§6.7，頁247），它指向的就是我們在這裡所提供的compareIsbn這個函式。當我們定義像這種multiset的物件時，我們就必須提供一個指標指出我們想要用到的運算是什麼，這個指標在此例中，就是一個指向compareIsbn函式的指標：

//bookstore這個multiset容器可以有著許多同一個ISBN書本的交易記錄

//在bookstore容器中的元素【交易記錄】會照ISBN來排序

multiset＜Sales_data, decltype(compareIsbn) *＞ bookstore(compareIsnb);

在這裡我們是用decltype來指明我們會提供的運算型別是什麼，要切記的是，當我們想要使用decltype來表示一個函式指標（function pointer）時，我們就必須在它回傳的值後再加上一個星號（*）來指出我們要傳入建構器的是一個已知函式型別的指標（§6.7，頁250），而不是函式型別而已。這裡是用compareIsbn函式來對bookstore容器作初始化的，這樣一來，當我們新增元素到這個bookstore容器時，這些元素就會藉由compareIsbn的運算來決定它們放在bookstore中的順序。因此，在bookstore中的Sales_data元素就會根據它們的資料成員ISBN號碼【在本書範例中這個資料成員名為「bookNo」】來排序了。在此例中，我們可以直接用「compareIsbn」當作bookstore建構器的引數，而不必寫成「&compareIsbn」【對compareIsbn函式做取址運算，「&」在這裡是取址運算子！】因為在C++程式碼中，直接使用一個函式的名稱在必要時就會被自動轉成對此函式的指標（§6.7，頁248）。如果需要，我們當然也可以寫成「&compareIsbn」，但效果是相同的。

可見在定義multiset這種容器時，必須提供想使用計算的型別是指標型別，而不是函式型別。因為decltype(compareIsbn)傳回來的是函式型別（function type），而不是函式指標（function pointer）型別，所以才要再後端再加上「*」以表我們要取用的是函式指標，而不是函式型別。

在「&」前沒有型別，就應該不會是作「參考」的意思來用，而是作「取址運算子」來理解

練習11.9

2:12:30第93集

試著定義一個map，其元素所儲存的會是由指定文字可以對應到這個文字出現的行號清單，這樣的資料。也就是其元素的鍵值會是某個文字，而其「值」則是一個list容器，這個容器儲存的會是這個文字出現的行號清單。3:19:00

#include＜iostream＞

#include＜sstream＞

#include＜iterator＞

#include＜list＞

#include＜map＞

#include＜string＞//要用getline要引用strinig標頭！

using namespace std;

int main() {

map＜string, list＜int＞＞m;

//istream_iterator＜string＞in(cin), end;

ostream_iterator＜int＞out(cout, ",");

string word, line;

int lNo = 0;

while (getline(cin, line)) {

lNo++;

istringstream iss(line);

while (iss ＞＞ word) {

m[word].push_back(lNo);

}

}

for (auto a : m)

{

cout ＜＜ a.first ＜＜ ":\t";

copy(a.second.cbegin(), a.second.cend(), out);

cout ＜＜ endl;

}

}

練習11.10

3:30:47

是否可以定義一個map，其元素之鍵值是vector＜int＞::iterator型別，而值是int型別。若是鍵值是list＜int＞::iterator而值是int呢？以上二種情況，如果不行，請說明為什麼？

因為list的迭代器list＜int＞::iterator並不支援隨機存取，而map在新增或比對元素時，須支援隨機存取才行。

3:58:08複習表10.5迭代器分類(頁410~412，有五種！)及練習10.39(頁412)和迭代器iterator的種類很有關係。

答案就在頁412： 4:24:17

程式庫容器，除了list、forward_list也都提供了這種迭代器成員（型別成員，type member）

array、deque 、string與vector的迭代器都是隨機存取迭代器，就跟我們用來存取一個內建陣列元素的指標一樣。

練習10.39：

list不具備隨機存取迭代器（random-access iterator），但具備雙向迭代器（bidirectional iterator）

而vector則具備最高層級的隨機存取迭代器（random-access iterator）

https://github.com/oscarsun72/prog1-C-Primer-5th-Edition-s-Exercises/blob/exercise11_10/prog1/prog1.cpp

https://github.com/oscarsun72/prog1-C-Primer-5th-Edition-s-Exercises/blob/exercise11_10review_list_int_iterator/prog1/prog1.cpp

https://github.com/oscarsun72/prog1-C-Primer-5th-Edition-s-Exercises/blob/exercise11_10review_vector_int_iterator/prog1/prog1.cpp

list不支援隨機存取，所以不行

Table 9.1. Sequential Container Types

僅支援雙向的循序存取

循序就必然要與「位置」有關。而map是以鍵值來存取元素的，不是位置。

在實務上，最重要的是，定義了「行為正常」的 ＜運算子的一個型別可被當作一個鍵值使用。

見頁347：

at和下標運算子（[]運算子,subscript operator）不能套用在list上，list是不支援隨機存取元素的，僅支援循序存取（見頁326，Table 9.1. Sequential Container Types）

表9.6 :存取一個循序容器中元素的運算

at 和下標運算子（subscript operator)只對 string、vector、deque 和 array 有效。 back 對 forward_list 無效。第93集6:25:00

list果然不行：

Severity Code Description

Error C2678 binary '＜': no operator found which takes a left-hand operand of type 'const _Ty' (or there is no acceptable conversion) with [ _Ty=std::_List_iterator＜std::_List_val＜std::_List_simple_types＜int＞＞＞ ]

如list中不能拿第1個迭代器跟第10個比較，它只能循序存取

練習11.11

試著不要用decltype來重新定義bookstore看看。4:43:00

函式被當作指標來傳遞

因此在建構一個multiset時，提供替代的運算函式，在被當作引數傳遞給其建構器（constructor）的時候，就只是指標，而不是函式來傳遞。故須提供一個函式指標，而不是函式型別。然函式在被當作引數傳遞時，默認的情況下就是被直接轉成指標來傳遞的。

#include＜iostream＞

#include＜vector＞

#include＜set＞

#include"Sales_data.h"

using namespace std;

int main() {

Sales_data s; vector＜Sales_data＞v;

while (read(cin, s))

{

v.push_back(s);

}



// bookstore 可能會有數筆交易記錄有相同的ISBN

// bookstore 中的元素會以ISBN排序

multiset＜Sales_data, decltype(compareIsbn)*＞

bookstore(v.cbegin(),v.cend(),compareIsbn);



typedef decltype(compareIsbn)* compIsbn;//頁249

multiset＜Sales_data, compIsbn＞

bookstore_typedef_decltype(v.cbegin(),v.cend(),compareIsbn);



using compISbn=bool(*)(const Sales_data& ,const Sales_data&) ;//頁249

multiset＜Sales_data, compISbn＞

bookstore_using(v.cbegin(),v.cend(),compareIsbn);



typedef bool(*compISBn)(const Sales_data&, const Sales_data&) ; //和一般typedef的寫法不同。函式指標的別名得寫在「*」後，不能寫在參數列（parameter list）後（即整個原型別名稱的後端）

multiset＜Sales_data, compISBn＞

bookstore_typedef(v.cbegin(),v.cend(),compareIsbn);

//可見一個函式的型別就是把它的簽章（宣告）的名字拿掉，而用一對圓括號取代；若是對此函式型別（function type）的指標，則是在此對圓括號內再加上星號「*」

multiset＜Sales_data, bool(*)(const Sales_data&, const Sales_data&)＞//頁249

bookstore_PF(v.cbegin(),v.cend(),compareIsbn); //P：指標F：函式



for (Sales_data s : bookstore_using)//以上5種（bookstore……bookstore_PF）全對了

{

print(cout, s); cout ＜＜ endl;

}

}



原型別名稱完整的就是：

bool(*)(const Sales_data&, const Sales_data&)

函式名稱並非型別的一部分。

如果是函式型別就不會有星號

bool()(const Sales_data&, const Sales_data&)

Sales_data.cpp

bool compareIsbn(const Sales_data& Lsd, const Sales_data& Rsd)

{//不能用inline

return Lsd.isbn()＜Rsd.isbn();

}

Sales_data.h

bool compareIsbn(const Sales_data&, const Sales_data&);//不能用inline



copy(v.cbegin(), v.cend(), back_inserter(bookstore));

Severity Code Description

Error C2039 'push_back': is not a member of 'std::multiset＜Sales_data,bool (__cdecl *)(const Sales_data &,const Sales_data &),std::allocator＜_Ty＞＞' with [ _Ty=Sales_data ]

因為multiset沒有push_back成員函式，所以只能用它的建構器（constructor）來初始化（第一次增加元素，後面要再增減元素，就要讀第3節：11.3. Operations on Associative Containers。容器的運算，就包括容器內元素的增減等）

4:47:03

11.2.3. The pair Type

pair類別型別(type)（對組型別）

在我們瞭解關聯式容器相關的運算前，我們有必要先來瞭解一下什麼是pair型別。這種程式庫型別（library type）是定義在utility標頭檔中。

一個pair類別定義了二個資料成員（data member），也和容器一樣，pair也是模板（template），須由我們指定型別才能使用。在用pair時，我們必須提供2個型別名稱，這2個型別分別對應到pair物件內的2個資料成員，且這2個型別名稱不必是一樣的：

和前面11.2.2. Requirements on Key Type遙相呼應，只是作文上換句話說而已

我們可以由指定這兩個資料成員的型別來產生一個特定的對組型別

這兩個資料成員在map中前一個就是鍵值的型別，而後一個則是值的型別

鍵值與值對組（key-value pairs）

pair＜string, string＞ anon; // 具備存放兩個stringr型別的能力

pair＜string, size_t＞ word_count; // 可以存放一個string和一個size_t的pair

pair＜string, vector＜int＞＞ line; //可以存放一個string 和一個vector＜int＞型別的pair

頁427

5:1:22 5:7:48 5:25:10

pair類別的預設建構器會以值初始化（value initialize，§3.3.1，頁98）的方式來初始化它這2個資料成員。因此在上例中，anon在宣告（或定義）後就會是一個含有2個空字串（empty strings）的pair，而line就會是一個含有一個空字串與空vector的pair。在word_count裡的size_t這個成員，就會被初始化為0，其string這個成員則一樣會被初始化為空字串。

我們也可以分別給pair型別物件的2個成員分別提供一個初始器來做初始化：

pair＜string, string＞ author{"James”,"Joyce"};

如上例，就會生成一個用"James"和"Joyce"初始化、叫做author的pair物件。

不像其他程式庫型別（library type），pair的這2個資料成員都是公用的（public，§7.2，頁268）。這2個資料成員分別名為first和second。對這2個成員的存取只要用普通的成員存取運算子（normal member access notation，§1.5.2，頁23）就可以了；就像我們在頁421的字頻計數程式在輸出述句時所寫的那樣：

cout ＜＜ w.first ＜＜ " occurs" ＜＜ w.second ＜＜ ((w.second ＞ 1) ? " times" : " time") ＜＜ endl;

這裡，w是一個對map中元素的參考，而map元素的型別則是pair。在這個輸出指令下，我們先印出pair元素裡的first這個成員，它即是map的鍵值（key），接著再印出second這個資料成員，它在此例是first這個成員所表的單字其字頻的計數。程式庫對pair定義的運算（也就是pair能做的操作）是相當少的，詳如表11.2所列：

pair類別的預設建構器會將其二個資料成員作值的初始化

除了用預設建構器來值初始化pair中的二個成員，也可以自訂初始器給它們

pair＜string, string＞ author{"James", "Joyce"};

前面好像也學過是要用大括弧的串列初始化（list initialization）

member access notation (§ 1.5.2, p. 23),

成員存取記號

成員存取運算子、點運算子

Table 11.2. Operations on pairs 表11.2 pair支援的運算



表11.2 : pair上的運算

pair＜T1, T2＞ p; p這個pair內含的是T1和T2型別的成員，且已經經過值初始化（§3.3.1，頁98）了。

pair＜Tl, T2＞ p(v1,v2) ; p這個pair其first是T1型別，而second則是T2這型別，分別由v1和v2來對它們做初始化。



pair＜T1, T2＞ p = {vl, v2}; 這樣的串列初始化（list initialization）寫法和p(v1,v2)直接初始化（direct initialize）是等義的

make_pair(v1, v2) 會傳回分別由v1和v2來初始化的一個pair。這個pair的成員型別則是由這2個傳入的v1和v2分別來推定的。

p.first 存取p這個pair中的first公用資料成員。

p.second 存取p這個pair中的second公用資料成員。

p1 relop p2

relop 意為 關係運算子（relational operator） pair也是有定義關係運算子（relational operator：＜,＞,＜=,＞=）的。它的順序是依照字典順序（dictionary ordering，其實就是ASCII的字元順序）。只要p1.first小於p2.first 或者 p2.first不小於p1.first而且p1.second也小於p2.second那麼p1＜p2就成立（is true）。這裡的「小於(＜)」，是用元素型別對小於運算子的定義來操作的。

p1 == p2

p1 !=p2 表示p1和p2這2個pair相等或不相等。只要p1和p2的first與second這2個資料成員分別相等，那麼p1和p2這2個pair就相等，否則就不等（!=）。這裡的等於，是用元素型別定義的「==」運算子來運算的。

6:5:30第93集

A Function to Create pair Objects

一個用來創建pair物件的函式

會/能夠產生/創建/建構pair型別物件的函式

此節主要是談如何在函式回傳時傳回一個pair型別的操作。

make_pair(v1, v2)

一個可以產生pair物件的函式

如果我們有函式是需要回傳一個pair物件，在新標準下我們可以串列初始化（list initialize）這個回傳的值（§6.3.2，頁226）：

6:7:10 6:38:50

頁428

pair＜string, int＞ process(vector＜string＞ &v)

{

// process v對v容器的處理

if (!v.empty())

return {v.back(), v.back().size()}; // list initialize用經過串列初始化的一個pair物件來回傳（應該說直接回傳一個串列初始器來初始化要回傳的pair

else

return pair＜string, int＞(); // explicitly constructed return value指明調用pair的預設建構器（default constructor）來創建一個經由值初始化的pair物件來回傳

}

容器back成員函式回傳的是對其最末元素的參考。要用容器的成員存取運算得先判斷容器是否有元素。詳頁347。v.back()回傳的是string ,而v.back().size()則回傳此string(容器)的大小（元素量==字元數）。

在上例中，如果v不是一個空的容器，程式碼就會回傳一個pair的物件，它是由v容器中最後一個的string元素及此元素的大小（字元多少）來構成的。然而如果v是空的、沒有元素，那麼就會實際建構一個空的pair物件來回傳。（空的pair就是只徒具型別，而不具有值；有值的話，也只是值初始化過後的值）

在早期的C++版本中，我們並不能藉由串列初始化（list initialization，也就是大括弧包覆的一串初始器）的方式來回傳諸如pair這樣的型別；因而我們可能就會將上述程式碼中的兩個return述句都寫成了實際建構出要回傳的值來回傳（如上例中第2個回傳式）。

if (!v.empty())

return pair＜string, int＞(v.back(), v.back().size());

又或者我們也可以利用make_pair來藉由指定符合pair型別的2個引數而產生一個新的pair出來：

if (!v.empty())

return make_pair(v.back(), v.back().size());

參見List Initializing the Return Value所舉例，此不過多了vector＜string＞ &v非空的參數列，而pair＜string, int＞是回傳型別，process是函式名稱。

pair＜string, int＞() ()是呼叫運算子（call operator），這裡是呼叫pair類別的預設建構器（因為它未帶任何引數）第93集6:38:40沒看到的就看臉書直播第473集約21分鐘前後

這個例子是說：要嘛用預設建構器（default constructor）建構一個空的pair來回傳，要嘛串列初始化（list initialization）回傳值型別（此為pair型別）

這裡用composed就是initialized:

we could have used make_pair to generate a new pair of the appropriate type from its two arguments:

標題作「Create」A Function to Create pair Objects，這裡作「generate」

練習11.12

寫個程式讀取一串成對的string和int資料，並將它們成對地存在在pair這個對組型別的物件中，再將每個pair物件，當作vector的元素儲存在vector裡。

6:41:10 6:46:30

可見pair只是型別，並不是關聯式容器專用的型別，循序容器也能用，如此地就用vector來儲存pair物件

#include＜iostream＞

#include＜vector＞

//#include＜utility＞//pair雖定義在此標頭中，但卻不必include就能用，如copy演算法等亦然

using namespace std;

pair＜string, int＞return_pair(vector＜pair＜string, int＞＞::const_iterator iter) {

return {iter-＞first,iter-＞second};

}

int main() {

vector＜pair＜string,int＞＞v;

vector＜pair＜string,int＞＞v1;

vector＜pair＜string,int＞＞v2;

vector＜pair＜string,int＞＞v3;

//istream_iterator＜string＞in(cin), end;

//while (in!=end) {

string w;int i;

vector＜pair＜string, int＞＞::const_iterator v1iter;

size_t vNo = 0;

while(cin＞＞w){

if (cin ＞＞ i) {

pair＜string, int＞pr(w, i);//v建構器初始化來創建pair

v.push_back(pr);

pair＜string, int＞prLI = {w, i };//v1串列初始化來創建pair

v1.push_back(prLI);

v1iter = v1.cbegin();//因為插入元素後原迭代器會失效，所以每次都要重取第一元素的迭代器

v2.push_back(return_pair(v1iter+vNo)); ++vNo;//v2最複雜,由函式傳回值來初始化以創建一個pair

v3.push_back(make_pair(w, i));//v3此式最簡單而直觀！

}

}

vNo=0;

vector＜pair＜string, int＞＞ a[4] = { v,v1,v2,v3 };

for(vector＜pair＜string, int＞＞ v:a){

cout ＜＜ vNo++ ＜＜ ":" ＜＜ endl;

for (pair＜string,int＞p:v)

{

cout＜＜ p.first; cout ＜＜ ":"

＜＜p.second ＜＜ endl;

}

cout ＜＜ "---------" ＜＜ endl;

}

}

練習11.13

在前一練習裡至少有3種方式可以建構出一個pair物件。因此，請將前面11.12那個練習的程式依此數種方式分別都寫出來，並解釋哪一種在編程（程式設計、撰寫程式）上是最容易寫與讀的，為什麼？

已見前一題。7:2:11

練習11.14

請將前面在§11.2.1（頁424，）練習11.7所做的那個以孩子名字來與他們家庭姓氏對應的map，擴充為利用vector來儲存一對包含孩子名字與生日的pair。

參見練習11.7

#include＜iostream＞

#include＜iterator＞

#include＜vector＞

#include＜map＞

using namespace std;

int main() {

map＜string, vector＜pair＜string,string＞＞＞ m;//3個string，分別存放家庭姓氏、孩子名字、孩子生日

//test text:

//Wells Oscar Wells joy Sun Oscar Washington Smith Sun June Wells Steve Washington Jack Sun Judy

//multimap＜string, vector＜string＞＞ m;

istream_iterator＜string＞in(cin), end;

string lastName,firstname;

while (in!=end)

{

lastName = *in;

firstname=*++in;

m[lastName].push_back(make_pair(firstname, *++in));

++in;

}

ostream_iterator＜string＞out(cout,",");

for (auto a :m)

{

cout ＜＜ a.first ＜＜ ":";

for (pair＜string,string＞ s : a.second)

{

*out++ = s.first;

*out++ = s.second;

cout ＜＜ "、";

}

cout ＜＜ endl;

cout ＜＜"----------------"＜＜ endl;

}

}

7:13:25

11.3. Operations on Associative Containers

11.3.在關聯式容器上運算

除了在表9.2（Table 9.2. Container Operations，頁330）所列出的型別成員外，關聯式容器類別還定義了在表11.3（頁429）中列出的型別成員。這些型別是拿來當作關聯式容器中鍵值與值的型別用的。

對set容器來說，key_type和value_type是一樣的，沒有分別。在set容器裡存放的元素其「值」就是其「鍵值」。而在map容器上，其元素型別則為鍵值與值對組（key-value pairs），也就是說每個在map中的元素都是一個pair型別的物件，【可是pair型別的物件卻不一定只能在map中用！】包含了一個鍵值和與此鍵值對應的「值」。因為map鍵值不能被改動，所以這些元素pair中的鍵值部分也就是const的：7:40:00

頁429

Table 11.3. Associative Container Additional Type Aliases

表11.3 :關聯式容器額外的型別別名

key_type 某個關聯式容器型別的鍵值型別。

對於map容器來說，就是pair＜const key_type,mapped_type＞

mapped_type 和每個鍵值關聯的型別（就是和鍵值對應到的值型別，被映射（map）的型別），這個型別只有map能用。即「值」的型別。

value_type 對set來說，就是key_type。對map而言，value_type就是pair＜const key_type, mapped_type＞這樣的型別。

7:32:00 7:40:40

set＜string＞::value_type v1;//v1的型別就是string

set＜string＞::key_type v2;//v2的型別也是string

map＜string,int＞::value_typ v3;//v3的型別是pair＜const string,int＞

map＜string,int＞::key_type v4;//v4的型別就是string

map＜string,int＞::mapped_type v5;//v5的型別就是int

和循序容器一樣（§9.2.2，頁332），都是用範疇運算子「::」來提取fetch其型別成員（type member）。比如說像

map＜string,int＞::key_type

此式，就是用範疇運算子「::」來指明存取key_type這個型別成員的。

而只有map相關的容器——如unordered_map、unordered_multimap、multimap——定義了mapped_type這樣的型別成員。

11.3.1. Associative Container Iterators

11.3.1.關聯式容器的迭代器

當我們對一個關聯式容器的迭代器解參考時，我們會得到一個value_type這樣型別的物件。【把這裡的value想成是元素值，而不是鍵值與值對組的值】在map容器中，一個value_type就是一個pair，它的first成員就是常值（const）的鍵值，而second則是「值」：

//取得一個指向word_count容器中第一元素的迭代器

auto map_it=word_count.begin();//it:iterator

//*map_it得到的就會是一個pair＜const string,size_t＞的物件

cont＜＜map_it-＞first;//會印出map_it指向的元素的鍵值

cout＜＜" "＜＜map_it-＞second;//會印出元素的「值」出來

map_it-＞first="new key";//會發生錯誤，不能編輯鍵值（因為鍵值是常值const）

++map_it-＞second;//這是可以的，可藉由map容器的迭代器來改動它元素的「值」。

注意：要記住map的value_type（元素值的型別）就是一個pair，而我們只能改動這個pair的「值」部分，卻不能改動它的鍵值。

Iterators for sets Are const

set容器的迭代器是唯讀的

雖然set容器定義了iterator和const_iterator這兩種型別的迭代器，但這兩種都只能對set元素作唯讀的存取，並不能更動其元素值。就像我們不能更動map容器元素的鍵值部分一樣，set元素的鍵值一樣也是不得更動的。【總之，鍵值就是不能更動的】我們只能用set的迭代器來讀取元素，而不是來編輯它：

set＜int＞ iset={0,1,2,3,4,5,6,7,8,9};

set＜int＞::iterator set_it=iset.begin();//傳回非常值的迭代器，卻仍只能唯讀其元素

if(set_it!=iset.end()){

*set_it=42;//錯誤！不能更動set的鍵值（也就是set的元素值），因為它是唯讀的

cout＜＜*set_it＜＜endl;//只讀取set元素（的鍵值）並列印出來是可以的

}

8:24:00即使set定義了const與nonconst的迭代器，但對於元素值仍只提供的唯讀存取權限。

頁430

Iterating across an Associative Container

在關聯式容器中使用迭代器

map、set這些容器型別都支援如表9.2（頁330）裡所列的begin和end運算。通常我們是利用這些成員函式來取得一個能夠巡覽存取容器元素的迭代器。比如，我們可以像下面這樣利用map的迭代器將之前在頁421所寫的字頻程式、它印出結果的迴圈部分重寫出來(那裡是用range for把其元素列印出來)：

//取得一個指向容器中第一元素的迭代器；word_count是一個map容器

auto map_it=word_count.cbegin();//auto這裡就是 map::iterator

//將現行的迭代器與尾端後迭代器（off-the-end iterator）比較看看

while(map_it!=word_count.cend()){

//解參考迭代器以印出map中元素的鍵值與值

cout＜＜map_it-＞first＜＜" occurs " ＜＜map_it-＞second＜＜" times" ＜＜endl;

++map_it;//遞增迭代器以推進讀取map容器中下一個元素

}

在這個while迴圈的條件式內及遞增迭代器之處，對迭代器的利用，都極似我們為了印出vector或string容器內容物而寫過的程式。我們在此先初始化一個迭代器map_it讓它指向word_count這個map容器中的第一個元素。只要這個迭代器的值和word_count尾端後迭代器（即end成員函式回傳的值）不相等，我們就印出這個迭代器所指向的元素、並推進這個迭代器。在輸出述句中，我們解參考了map_it這個迭代器來取得pair物件中的二個資料成員。這樣印出的結果會和我們之前寫的一樣。

注意：上述程式的輸出結果會是一個經由字典順序來排序的結果。當我們利用迭代器來巡覽map、multimap、set、multiset這樣的容器時，這些迭代器的運算結果都會是其鍵值已經經由遞增排序的結果。

set、map都支援Table 9.2. Container Operations所有的運算

8:53:43 8:58:50

既然前面提到排序，所以接下來就要來談談關聯式容器的運算與演算法的關係：

Associative Containers and Algorithms

關聯式容器與演算法的關係/關聯式容器套用泛用演算法的限制

通常我們並不會在關聯式容器上套用泛用演算法（generic algorithm，第10章）。因為關聯式容器的鍵值是唯讀的，這一特性，就無法讓它傳給排序重排元素、或編輯元素的演算法來用。因為這些演算法的操作都必須動到元素的值，而在set容器中的元素皆是唯讀的const，在map的，其第一部分（即鍵值）也是唯讀的const。

關聯式容器是可以搭配只會讀取元素的演算法來用沒錯。然而，這些演算法在找尋元素時多是以循序的方式來搜尋的。而關聯式容器的元素卻可以逕由鍵值來迅速找到；所以如果想用泛用的演算法來找尋關聯式容器內的元素，並不是個明智之舉。就像我們會在§11.3.5（頁436）見到，關聯式容器自己就定義了一個叫做find的成員函式，這個函式就可以逕由鍵值來將容器中的元素找出來。我們當然也可以用find這樣的演算法來尋找關聯式容器中的元素，但是find演算法卻必須在關聯式容器中挨家挨戶地找（一個個元素去找）才能找到我們要找的那個元素。因此，用關聯式容器的find成員函式來搜尋它們自己的元素，會比借用泛用演算法的find來找取要快捷得多！因此，從這些方面來看，泛用演算法在關聯式容器的領域中，可說是沒有用武之地、是不合用的。

然而在實務上，如果我們非要將關聯式容器與演算法搭配在一起用，那麼我們通常只會將這個關聯式容器作為演算法的來源容器（sequence）或目的容器來使用。比如說，我們可以用copy這樣的泛用演算法來將一個關聯式容器的元素拷貝到另一個容器（sequence）中。同樣地，我們也可以用（call）inserter這個迭代器來將一個插入迭代器（insert iterator）與關聯式容器綁在一起（bind），藉由inserter（using inserter），我們就可以讓這個關聯式容器作為另一個演算法的目的容器來使用。【所以關聯式容器和演算法的搭配使用，幾乎僅僅止於作為目的或來源容器使用。】

9:48:39

鍵值是唯讀的屬性就限制了我們無法在關聯式容器上套用那些會更動元素值與位置的演算法

因為迭代器是演算法必備的條件，怎樣的迭代器決定了可用上哪些的演算法，或決定了演算法可以怎樣運用一個容器對象。

可見此key也類似Access資料庫中的索引index,所以能加速搜尋

關聯式容器和演算法配合的常態是作為演算法的來源序列或目標容器對象

頁431

練習11.15

9:58:40

對一個元素是由int對應到vector＜int＞的map來說，它的mapped_type、key_type、value_type分別是什麼？

mapped_typ : vector＜int＞

key_type: int

value_type:pair＜int,vector＜int＞＞

value_type 九陽神功 連這裡也用得上！value_type還不如取成「element_type」

⑧找對主詞 誰的value？ 誰的？ 關聯式容器的元素本身的「值」，不是鍵值與值對組的值

10:5:10

練習11.16

用一個map的迭代器來寫一段運算式（expression）以便將其元素設定為某個值。

#include＜iostream＞

#include＜iterator＞

#include＜map＞

using namespace std;

int main() {

map＜string, string＞ m;m["孫"]= "守真" ;

map＜string, string＞::iterator map_it=m.begin();

ostream_iterator＜string＞out(cout);

*out = map_it-＞first;

*out++ = map_it-＞second; cout ＜＜ endl;

map_it-＞second = "任真";

*out = map_it-＞first;

*out++ = map_it-＞second; cout ＜＜ endl;

}

10:14:20

練習11.17

如果c是一個由string組成的multiset，而v是一個由string構成的vector。解釋下列的程式碼在做什麼，並指出哪些是對的、哪些是錯的。

copy(v.begin(), v.end(), inserter(c, c.end()));

copy(v.begin(), v.end(), back_inserter(c));

copy(c.begin(), c.end(), inserter(v, v.end()));

copy(c.begin(), c.end(), back_inserter(v));



#include＜iostream＞

#include＜iterator＞

#include＜vector＞

#include＜set＞

using namespace std;

int main() {

multiset＜string＞ c ;

istream_iterator＜string＞in(cin),end;

ostream_iterator＜string＞out(cout, ",");

copy(in, end, inserter(c, c.end()));

vector＜string＞v;

copy(in, end, inserter(v, v.end()));

copy(c.cbegin(), c.cend(), out); cout ＜＜ endl;

//copy(v.begin(), v.end(), inserter(c, c.end()));//OK

//copy(v.begin(), v.end(), back_inserter(c));//Error C2039 'push_back': is not a member of 'std::multiset＜std::string,std::less＜_Kty＞,std::allocator＜_Kty＞＞'因為關聯式容器set不支援back運算，應該是因為set插入元素是由鍵值排序，沒有所謂的「back」。

//copy(c.begin(), c.end(), inserter(v, v.end()));//OK

copy(c.begin(), c.end(), back_inserter(v));//OK，與前式同。因vector有push_back()也，也支援back運算

copy(c.cbegin(), c.cend(), out);

cout ＜＜ '\n' ＜＜ "----------" ＜＜ endl;

copy(v.cbegin(), v.cend(), out); cout ＜＜ endl;

}



10:28:10

練習11.18

請明確寫出在頁430程式碼迴圈中的map_it這個物件的型別是什麼。

map＜string, size_t＞ word_count; //從string 對應到size_t的一個空的map容器

auto map_it=word_count.cbegin();//auto這裡就是 map::iterator

map＜stinrg,size_t＞::const_iterator



#include＜iostream＞

#include＜iterator＞

#include＜map＞

using namespace std;

int main() {

// get an iterator positioned on the first element

map＜string, unsigned＞word_count;

istream_iterator＜string＞in(cin), end;

while (in != end) ++word_count[*++in] ;

map＜string, unsigned＞::const_iterator map_it = word_count.cbegin();

// compare the current iterator to the off-the-end iterator

while (map_it != word_count.cend()) {

// dereference the iterator to print the element key--value pairs

cout ＜＜ map_it-＞first ＜＜ " occurs "

＜＜ map_it-＞second ＜＜ " times" ＜＜ endl;

++map_it; // increment the iterator to denote the next element

}

}

10:34:40

練習11.19

試著由§11.2.2（頁425、426）bookstore這個multiset的begin成員函式回傳的值來初始化一個迭代器變數，寫出它的型別，而不是用auto或decltype來指定（推測）。

參見練習11.11

10:41:30

//bookstore這個multiset容器可以有著許多同一個ISBN書本的交易記錄

//在bookstore容器中的元素【交易記錄】會照ISBN來排序

multiset＜Sales_data, decltype(compareIsbn) *＞ bookstore(compareIsnb);



multiset＜Sales_data, decltype(compareIsbn) *＞::iterator bs_mulset_iter=bookstore.begin();



bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)

{

return lhs.isbn() ＜ rhs.isbn();

}



multiset＜Sales_data, bool(*)(const Sales_data &,const Sales_data &)＞::iterator bs_mulset_iter=bookstore.begin();



#include＜iostream＞

#include＜vector＞

#include＜set＞

#include"Sales_data.h"

using namespace std;

int main() {

Sales_data s; vector＜Sales_data＞v;

while (read(cin, s))

{

v.push_back(s);

}



// bookstore 可能會有數筆交易記錄有相同的ISBN

// bookstore 中的元素會以ISBN排序

multiset＜Sales_data, decltype(compareIsbn)*＞

bookstore(v.cbegin(),v.cend(),compareIsbn);



typedef decltype(compareIsbn)* compIsbn;//頁249

multiset＜Sales_data, compIsbn＞

bookstore_typedef_decltype(v.cbegin(),v.cend(),compareIsbn);



using compISbn=bool(*)(const Sales_data& ,const Sales_data&) ;//頁249

multiset＜Sales_data, compISbn＞

bookstore_using(v.cbegin(),v.cend(),compareIsbn);



typedef bool(*compISBn)(const Sales_data&, const Sales_data&) ;

multiset＜Sales_data, compISBn＞

bookstore_typedef(v.cbegin(),v.cend(),compareIsbn);



multiset＜Sales_data, bool(*)(const Sales_data&, const Sales_data&)＞//頁249

bookstore_PF(v.cbegin(),v.cend(),compareIsbn);



for (Sales_data s : bookstore_using)//以上5種（bookstore……bookstore_PF）全對了

{

print(cout, s); cout ＜＜ endl;

}

//練習11.19改用迭代器回傳

cout ＜＜ "------------" ＜＜ endl;

multiset＜Sales_data, compISbn＞::iterator bookstore_using_it{bookstore_using.begin()};

while (bookstore_using_it != bookstore_using.end())

{

print(cout, *bookstore_using_it++); cout ＜＜ endl;

}

cout ＜＜ endl;

}

Table 10.5. Iterator Categories 迭代器型錄型別目錄

Input iterator

輸入型迭代器 Read, but not write; single-pass, increment only

只讀入，不輸出，不可重複使用，只能遞增/前進

Output iterato

輸出型迭代器r Write, but not read single-pass, increment only

只輸出，不讀入，不可重複使用，只能遞增/前進

Forward iterator

前進型迭代器 Read and write; multi-pass, increment only



Bidirectional iterator

雙向型迭代器 Read and write; multi-pass, increment and decrement

Random-access iterator

隨機存取迭代器 Read and write; multi-pass, full iterator arithmetic

具：讀寫功能、可重複使用、完全的迭代器運算

第93集4:5:40



隨機存取迭代器（random-access iterators ）:

這是最高層級/型/種的迭代器

provide constant-time（恆定時距，duration，中文版翻「常數時間」 第93集4:22:30）， access to any position in the sequence.

隨機存取迭代器提供的性能是能在序列中，以同樣時間，讀取任何元素。

除了前述各項迭代器（原文雖作bidirectional iterators,但其實應即囊括所有）的功能皆具備外，它還支援了表3.7（頁111）所列的運算：

1.關係運算子（relational operator），來比較兩個迭代器的相對位置，誰先誰後。

2.加減運算子（+，+=，-，-=）。只支援與整數的加減運算

The result is the iterator advanced (or retreated) the integral number of elements within the sequence.

參見練習10.37。

3.減號運算子，套用在兩個迭代器上來比較二者所指元素的間距（distance）

4.下標運算子（[]運算子,subscript operator）

( iter[n] ) as a synonym for * (iter + n) .

表3.7（頁111）不具此項。就是對這個元素下標，這個元素是在iter所指元素「後或前n若為負值」n個位置的元素，以讀取其值。

sort演算法所需的就是這種迭代器

程式庫容器，除了list、forward_list也都提供了這種迭代器成員（型別成員，type member）

array、deque 、string與vector的迭代器都是隨機存取迭代器，就跟我們用來存取一個內建陣列元素的指標一樣。

練習10.38

寫出五種迭代器型錄，並指出每種迭代器所支援的運算 第93集4:28:00

Table 10.5. Iterator Categories

練習10.39

list不具備隨機存取迭代器（random-access iterator），但具備雙向迭代器（bidirectional iterator）

而vector則具備最高層級的隨機存取迭代器（random-access iterator）





頁426

在定義關聯式容器multiset時，要用自訂的運算來取代預設的，就必須同時提供兩個型別作為建構用的引數：一個為其原來的鍵值型別（key type），一為比較運算用的型別(comparison type)。（因為默認的運算，只須一個鍵值型別即可建構multiset）

比較運算用的型別comparison type,是一個函式指標（function pointer）的型別,它是用來指向我們要用來替代預設比較運算用的函式的：

comparison type, which is a function pointer type (§ 6.7, p. 247) that can point to compareIsbn. When we define objects of this type, we supply a pointer to the operation we intend to use. In this case, we supply a pointer to compareIsbn:

∵ 要定義一個關聯式容器須提供建構其容器的型別引數，蓋一個關聯式容器是由的元素型別，如陣列大小為陣列型別之一部分，關聯式容器的元素型別也是它型別的一部分，我們必須為它們提供適當的型別作為其元素的型別，以構成其容器型別。

∴ 因為函式本身不是型別，要把它作為型別來定義容器，就必須使用函式指標（function pointer），這才是型別，應即是指標此一複合型別（compound type）：

the comparison type, which is a function pointer type (§ 6.7 , p. 247 ) that can point to compareIsbn .

multiset＜Sales_data, decltype(compareIsbn) *＞ bookstore(compareIsbn);



複習前面的函式指標（function pointer）

可見在定義multiset這種容器時，必須提供想使用計算的型別是指標型別，而不是函式型別。因為decltype(compareIsbn)傳回來的是函式型別（function type），而不是函式指標（function pointer）型別，所以才要再後端再加上「*」以表我們要取用的是函式指標，而不是函式型別。



我們可以寫出compareIsbn而非&compareIsbn作為建構器引數，因為使用 —個函式的名稱時，如果需要，它會自動被轉換為一個指標（§6.7，頁248）。我們也可以寫成 &compareIsbn，效果相同。

&在此為取址運算子，「&compareIsbn」即以函式指標型別來傳遞compareIsbn此函式。

練習11.9

#include＜iostream＞

#include＜sstream＞

#include＜iterator＞

#include＜list＞

#include＜map＞

#include＜string＞//要用getline要引用strinig標頭！



using namespace std;

int main() {

map＜string, list＜int＞＞m;

//istream_iterator＜string＞in(cin), end;

ostream_iterator＜int＞out(cout, ",");

string word, line;

int lNo = 0;

while (getline(cin, line)) {

lNo++;

istringstream iss(line);

while (iss ＞＞ word) {

m[word].push_back(lNo);

}

}

for (auto a : m)

{

cout ＜＜ a.first ＜＜ ":\t";

copy(a.second.cbegin(), a.second.cend(), out);

cout ＜＜ endl;

}

}

第93集 3:19:00以下是錯的，多蠢，詳見實境秀第71集看笑話！

#include＜iostream＞

#include＜iterator＞

#include＜list＞

#include＜map＞

using namespace std;

int main() {

map＜string, list＜string＞＞m;

istream_iterator＜string＞in(cin), end;

ostream_iterator＜string＞out(cout, ",");

string word;

while (in!=end)

{

word = *in;

m[word].push_back(*++in);

++in;

}

for (auto a : m)

{

cout ＜＜ a.first ＜＜":\t";

copy(a.second.cbegin(),a.second.cend(), out);

cout ＜＜ endl;

}

}