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

頁446

第97集開始

如果我們的類別已有它自己定義的等於運算子「==」，那麼我們就可以只覆寫hash函式就可以了：

//用FooHash來產生雜湊碼（hash code）；Foo必須具備它自己定義的等於運算子「==」

unordered_set＜Foo, decltype(FooHash)*＞fooset(10,FooHash);

也就是一個類別必須定義了自己的等於運算子才能省略在用它來定義一個新的無序容器時的第3個參數/引數

如果我們的類別有自己的==運算子，我們可以只覆寫hash function就行了：（中文版翻譯）

//使用FooHash來產生hash code，Foo必須有一個==運算子

unordered_set＜Foo, decltype(FooHash) *＞ fooSet(10, FooHash);

6:00自定義Sales_data的等於運算子「==」：

標頭檔.h內宣告：

bool operator==(const Sales_data&,const Sales_data&);//自定義Sales_data的等於運算子之宣告部分

cpp檔案定義

bool operator==(const Sales_data&lhs, const Sales_data&rhs)//自定義Sales_data的等於運算子

{

if (lhs.isbn() == rhs.isbn())

return true;

return false;

}



16:02

練習11.37

無序的容器相較其對應的有序容器有什麼優點。而同樣的容器，若使用有序的又有什麼長處？

無序容器與同版本的有序容器的優缺點

理論上無序容器效能較佳，但限制亦多。如前若要用自定型別作鍵值，必要定義自己的hash函式和等號運算子（或等於運算）

如果hash函式沒設計好或者貯體（bucket）配置不當，也會影響無序容器的效能

有序、無序，二者應是互補的關係

無序容器除了還有雜湊函數（hash function）等特定操作外，其他有序版本有的運算，它都支援，參下題改寫前例，都僅只換了型別便可知。優點是多此功能，缺點也是多此麻煩。

不需要排序鍵值時，無序容器就派得上用場了：

無序容器最大的用途在於當鍵值型別的物件並沒有明確大小順序的時候。【即不具備嚴格的弱次序（strict weak ordering）】在沒有必要維持鍵值順序、或維持其順序的成本大到無法負擔的時候，無序容器也是很有用的。

雖然原則上，雜湊在組織管理無序容器的元素時也能提供不錯的性能表現，但在實務上通常都必須付出相當多的測試與不斷地調整，才能有望在實際上達到該有的理想水平。因此，通常用有序容器來操作，還容易得多（且往往還有更好的性能）。

必須把握的要領訣竅（撇步）是：只在（if）以下兩種情況才使用無序容器：

1.鍵值型別是無法排序的

2.性能測試反應（或出現）的問題是雜湊足以應付的

練習11.38

請將§11.1的字頻程式（頁421）與§11.3.6的文字轉換程式（頁441）改用unordered_map來重寫。

word_count

#include＜iostream＞

#include＜iterator＞

#include＜unordered_map＞//唯二不同，須引用而已

using namespace std;

int main() {

unordered_map＜string, size_t＞ word_count;//唯二不同，改型別而已

string word;

while (cin ＞＞ word)

++word_count[word];

for (const auto& w : word_count) //印出來的順序也會與有序版的不同

cout ＜＜ w.first ＜＜ " occurs " ＜＜ w.second

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

}

練習11.33

#include＜iostream＞

#include＜fstream＞

#include＜iterator＞

#include＜unordered_map＞//唯3不同，須引用而已

using namespace std;

int main() {

unordered_map＜string, string＞mReplace;//唯3不同

ifstream ifs("V:\\Programming\\C++\\OCRtxtCorrect1.txt");

ifstream ifsInput("V:\\Programming\\C++\\input1.txt");

istream_iterator＜string＞in(ifs), end;

string key, value;

while (in != end) {

key = *in; value = *++in;

mReplace.insert(make_pair(key, value)); ++in;

}

istream_iterator＜string＞input(ifsInput), e;

unordered_map＜string, string＞::const_iterator mIt;//唯3不同

string ocr;

while (input != e)

{

ocr = *input;

mIt = mReplace.find(ocr);

if (mIt != mReplace.cend())

cout ＜＜ mIt-＞second ＜＜ endl;

else

cout ＜＜ ocr ＜＜ endl;

++input;

}

}

30:20

頁447

Chapter Summary

本章總結（撮要、摘要）

關聯式容器是依據鍵值的值來查找與存取元素。對鍵值的使用，是關聯式容器與循序容器關鍵不同的所在；而循序容器的元素是藉由位置（定位點）來存取的。【守真按：其實二者似異而實同，所謂藉由定位點來存取，其實其定位點或索引值，就如同關聯式容器的鍵值！都是依據鍵值而查找元素之「值」的。可以說關聯式容器鍵值的型別並不限於無號的，而循序容器的「鍵值」則一定要是無號型別，因為它是作為表示位置的記號，如「0」就是第1個位置。而關聯式容器就無此限制。鍵值（key）就是索引值（index）的證明。以map來模擬陣列（array）或循序容器（sequential container）詳見：https://github.com/oscarsun72/prog1-C-Primer-5th-Edition-s-Exercises/blob/p447_Key_is_index/prog1/prog1.cpp 】

無序容器是藉由貯體（bucket）來代為管理元素，所以須先將元素歸併到合適的貯體（bucket）中，才要先將元素經由hash取其雜湊值（就是雜湊碼），以此雜湊值（hash value）來決定要置入到哪個貯體（bucket）中。

而有序容器則是直接管理元素，並不需要貯體代理。因此有序容器的元素型別一定要具備嚴格的弱次序（strict weak ordering）。50:00 2:21:50所以只要有定義其小於運算子「＜」或相當於這運算子的函式運算，就可以以此型別來作為有序容器的鍵值型別。詳見測試（此測試已定義了小於運算子「＜」）：https://github.com/oscarsun72/prog1-C-Primer-5th-Edition-s-Exercises/tree/p425_426ordered_c_keyType_strict_weak_ordering/prog1

有序容器是利用鍵值型別的小於運算子（＜）來排序元素的。無序容器則是利用鍵值的等於運算子（==）來組織元素（難怪無序容器有群組化功能，因為它憑藉的是「==」等於！相等的就放在同一個貯體（bucket）中，當然要bucket_size容得下才行！）這裡英文版引介得真是支離破碎，完全不懂得將觀念有條理地組織起來論述！繞來繞去，把學生搞了昏頭轉向，不知所措，抓不到重點與頭緒。

至於無序容器的元素要放在哪個貯體（bucket）中，就需要用到雜湊函數（hash function）來換算（代理），將換算的結果當作有如有序的鍵值一樣。雜湊函數算出來的，就是雜湊值（hash value），它是型別為hash＜key_tyep＞的物件。（hash＜key_tyep＞意思就是在鍵值型別上做雜湊hash運算以取得雜湊碼（hash code）。）取得雜湊值（hash value）後才能決定要放在哪個貯體。大概雜湊碼相同的就會放在同一個貯體，特別是元素鍵值相同的，就會放在一塊。這就是利用鍵值型別等於運算子運算的結果來安排。

所以有序容器其實就是用鍵值型別的小於運算子來組織元素並排序元素，而無序容器則是用鍵值型別的等於運算子來組織元素而不排序元素。

有序，何必還要用到雜湊（hash）呢？就是因為無序可言，才需要借助雜湊運算來取得其組織的規則。【英文版這裡不把觀念教清楚，卻只是陳述一大堆規則要人死背硬記？】沒錄到的部分可以看臉書直播第500集 https://www.facebook.com/oscarsun72/videos/2564449926999459/

關聯式容器與循序容器在很多運算上是相同。而其中相異的部分，許多是因為關聯式陣列是利用鍵值來組織它的元素的原故。不管是有序容器還是無序容器，都是用鍵值（鍵值型別的小於運算（子）或等於運算（子））來組織它們的元素的。

其實循序容器的「鍵值」（索引值）型別必為unsigned，因為是要標識位置用的，位置當然只有第1位、第2個位置這樣的正整數意義啦，只不過是從0開始，故是無號型別（無號就是無負號）。而關聯式容器的鍵值型別就未必。

有序容器的迭代器是依鍵值的次序來巡覽其各個元素的。不管有序或無序的容器都會將鍵值相同的元素放在一起；因為無序容器只有元素的群組化，而有序容器除了群組化還加以排序。



2:33:50 2:39:20

所以有序容器不是天生有就序，它還是動用到一個比較用的函式（或定義了小於運算子），符合了嚴格的弱次序（strict weak ordering），才能對其內元素進行排序：

Ordered containers use a comparison function to order the elements by key.

By default, the comparison is the ＜ operator on the keys.

Unordered containers use the key type’s == operator and an object of type hash＜key_type＞ to organize their elements.

不論是有序還是無序的容器，有相同鍵值的元素的都會挨在一塊兒：

Elements with the same key are stored adjacent to one another in both the ordered and unordered containers.

Defined Terms

涉及的詞彙（專有名詞）

2:43:10

associative array

關聯式陣列

將鍵值作為索引值的陣列。其實也是以鍵值取值的容器。

Array whose elements are indexed by key rather than positionally. We say that the array maps a key to its associated value.

前面我們有以map模擬array（key_is_index），這裡是array模擬關聯式容器。

這裡更印證了末學先前所體悟的 3:54:40 C++容器其實是3大類！都是與「maps a key to its associated value」有關的

hash

hash是一種特殊程式庫模板（template），無序容器用它來安排元素置放的位置。【守真按：hash是由元素型別來算出雜湊碼（hash code）以決定該型別之各個元素要放在哪些貯體（bucket）中。】

hash Special library template that the unordered containers use to manage the position of their elements.

可見關聯式容器仍舊逃不掉元素「位置」的存取也！只是它取「位置」的方式與有序容器不同罷了！有序是用「小於運算子及特效之運算」，而關聯式容器則是用「等於運算子及特效之運算」。

hash function

hash function 雜湊函數：原來雜湊計算的原理就是用某個型別的值來映射（map to）到一個size_t的無號整數值（所以此函式回傳的型別是size_t。導入引數為鍵值型別，回傳值是size_t，這叫「map」！）。理論上（原則上），計算出的結果若相同，就應當要對應到（map to）相同的整數值。計算的結果不同，也應該要對應到不同的整數值。【守真按：這就是所謂雜湊函數的效能或品質問題。○在無序容器中這是決定元素置放貯體的關鍵】

把它想成「發號碼牌」或「抽號碼牌」就對了，拿到第幾號就到哪一號貯體（bucket）去報到囉

hash function Function that maps values of a given type to integral ( size_t ) values.

Equal values must map to equal integers; unequal values should map to unequal integers where possible.

5:0:40

這種「Equal values must map to equal integers; unequal values should map to unequal integers where possible.」能力就是hash函式的好壞評準（即其品質、效能之所依），所以決定不是亂雜湊的

key_type

由關聯式容器類別定義出來的型別成員。（所以要用範疇運算子「::」來引用）這樣的型別是用以存（store）取（retrieve）「值」的鍵值型別。（that is the type for the keys used to store and retrieve value.【守真按：這store和retrieve ⑧找對主詞 →的對象都是「value」（「值」）！】）對於map來說，key_type是用來對map作索引（下標）的型別。對set來說，它就是value_type。

map

map是一種關聯式容器，它定義了一個關聯式陣列。（Associative container typ that defines an associative array.）就像vector,map也是類別模板（class template）。只是map須由2個型別來定義，一個是鍵值的型別，一個是鍵值對應的「值」的型別。解參考 一個map的迭代器，得到的會是一個pair型別的物件，它帶著的是一個常值的鍵值和與它關聯的「值」。

5:4:55

關聯式容器與關聯式陣列的關係：

map Associative container type that defines an associative array.

map定義一個關聯式陣列的關聯式容器。

頁448

mapped_type

mapped_type是由map型別的容器所定義的型別成員，它是map中與鍵值關聯的「值」的型別。

multimap

5:8:15

multimap ：鍵值可重複的map並不支援下標（subscript）運算。【守真按：所謂的下標，一定是指定位置的；鍵值可以重複，就不知到底要指定哪一個位置了！】

multimap does not support subscripting.

可見下標（subscript）運算是要在唯一值上操作的。一定是一對一的關係！

5:9:59

pair

pair是有著兩個公開資料成員的型別，分別是first和second。這型別也是個模板型別（template type），下定義時須帶入要作為first與second的型別才行。

strict weak ordering

strict weak ordering嚴格的弱次序：有序的關聯式容器（即有序容器）用來決定鍵值次序的大原則。符合這樣的次序是：任兩個值，必須要能判斷出它們固定的先後次序；而若無法判斷時，此二值就必定相等。

strict weak ordering Relationship among the keys used in an associative container. In a strict weak ordering, it is possible to compare any two values and determine which of the two is less than the other. If neither value is less than the other, then the two values are considered equal.

strict weak ordering（嚴格弱次序）關聯式容器中所用的鍵值之間的關係。

無序容器（unordered container）並不需要嚴格的弱次序啊！這裡漏掉了！ 無序容器需要的是「嚴格的元素型別的相等值」，此相等值是用來傳入雜湊函數（hash function），藉雜湊算出來的雜湊值（hash value）來評估各元素要置放的位置。（相等的盡量放在一塊。愈能做到如此，就表示其雜湊函數的品質（quality）愈高！）

5:18:40

unordered container

unordered container（無序容器） 無序容器是用hash（雜湊）來判定其鍵值之歸屬，而非依照嚴格的弱次序的比較運算來決定元素放置的位置。無序容器的效能端看（depends on）雜湊函數（hash function）的效能（quality）如何。

4:35:00 5:21:20忘了錄的就看臉書直播第502集約45分鐘前 https://www.facebook.com/oscarsun72/videos/2566688803442238/

unordered container Associative containers that use hashing rather than a comparison operation on keys to store and access elements. The performance of these containers depends on the quality of the hash function.

這些容器的效能取決hash function的品質。也就是說，hash函式不要設計不良

對鍵值是用hash而不是用comparison operation來存放和取用元素

store（存放）就是讓元素歸類（先歸類，再排序）【歸類就是我們前面說的群組化！】

5:23:20

4:40:00英文版這裡講unordered_multimap與unordered_multiset完全忘了無序（unordered）二字！這樣與前面沒有「unordered」的解釋有何不同？

value_type

value_type即關聯式容器的元素型別；是由關聯式容器這類容器定義的型別成員。對set的容器來說，就是key_type。而在map容器下，value_type就是pair這樣的型別；這個pair的first型別就是一個常值的key_type，而second的型別就是mapped_type。

*運算子

*運算子（解參考運算子）。解參考（dereference）map,set,multimap,multiset的迭代器，其結果會是一個value_type的物件。用在map迭代器上，則會是一個pair。

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

下標運算子。因為在關聯式容器下標就會插入新元素，所以只能用在非常值的map和unordered_map上，也只有這兩種容器有定義下標運算子。在這裡用來下標的型別就是鍵值型別（key_type）或與鍵值型別有相容關係的型別。下標取得的型別，則是mapped_type。因為以鍵值下標就是為了取得其對應的「值」，而set「值」就是鍵值，當然就不必再多此一舉、下標才能取得「值」了。

只對非常值（nonconst）map、unordered_map有效：

[ ] operator Subscript operator. Defined only for nonconst obejcts of type map and unordered_map. For the map types, [] takes an index that must be a key_type (or type that can be converted to key_type). Yields a mapped_type value.