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

頁443

11.4. The Unordered Containers

11.4無序容器

C++11的新標準定義了4種無序的關聯式容器。這4種容器並不是利用元素間比較的運算來組織它們的元素，而是用雜湊函數（hash function）和鍵值型別的等於運算子「==」來組織元素的。無序容器最大的用途在於當鍵值型別的物件並沒有明確大小順序的時候。【即不具備嚴格的弱次序（strict weak ordering）】在沒有必要維持鍵值順序、或維持其順序的成本大到無法負擔的時候，無序容器也是很有用的。

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

The new standard defines four unordered associative containers . Rather than using a comparison operation to organize their elements, these containers use a hash function and the key type’s == operator.

無序容器的元素是用hash函式和鍵值型別的等號運算子來組織它的元素

雜湊函數（hash function）

comparison operation就是前面提到的以函式指標（function pointer）的方式將函式當作引數傳遞給關聯式容器的建構子，據此組織其內元素之次第；故為有序容器。

第96集

26:44 中文版翻成這樣，您看得懂嗎？

無序容器最有用的時機是，當我們有一種鍵值型別，其元素之間沒有明顯的順序關係。這些容器對於維護元素順序的成本令人望而卻步的應用來說，也很實用。

也就是在不需要、沒有必要，或者沒有、乃至無法排序元素的狀況下，都是使用無序容器的時機。改中文版作文：

雖然在理論上，hashing（雜湊）在平均的效能上，也有不錯的表現；但想在實際實務中達到令人滿意的結果，通常都必須做上許多的效能測試與調整，才能有望。因此一般而言，使用有序容器還比較容易得多（且經常也會得到較佳的效能）。

雖然理論上或原則上，無序容器使用hashing在效能上一般都會有所提升，然而這種效能的取得往往須付出一定的代價，比如說不斷地測試與調整；也因此，有序容器在某些時候，反而凌駕其上。

頁444

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

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

2.性能測試反應出（或出現）的問題是可以用雜湊函式來應付的

中文版翻成這樣：

tip:如果鍵值型別本質上就是無序的，或者效能測試之下，顯示出有hashing可以解決的問題，就使用無序容器。

使用無序容器（unordered container）的時機與應有的考量

Using an Unordered Container

使用無序容器

除了提供了管理雜湊（hashing）的運算，無序容器和有序容器也一樣定義了諸如find、insert這樣的運算。因此，用在map和set上的運算，也可以套用在unordered_map和unordered_set上。同樣的，無序的multi容器也適用。因此，在實務上，我們通常都會在無序容器與有序容器之間交替使用。只是因為無序容器其元素排列畢竟是無序的，【Howerve,because the elements are not stored in order,守真按：前面我有測試無序版本的，雖元素間不排序，但相同鍵值，在multi類型的容器，依然會放在一起】1:44:00 2:20:00放在一起不表示有排序！拜託！邏輯別混亂了。總結：應該說，無序容器有群組化的功能，無排序的性質。2:27:00所以當我們將其內元素一一印出時，無序與有序的結果，可能就會有所不同了。

the output of a program that uses an unordered container will(ordinarily) differ from the same program using an ordered container.

比如說，我們可以試著用unordered_map來改寫前面§11.1（頁421）的字頻計算程式：

//計算各個字彙出現的頻率，但是這些字彙並不會按照字母順序來排列

unordered_map＜string, size_t＞ word_count;

string word;

while (cin ＞＞ word)

++word_count[word]; //提取並遞增word的字頻數

for (const auto &w : word_count) //將map中的每個元素印出來

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



// count occurrences, but the words won't be in alphabetical order

unordered_map＜string, size_t＞ word_count;

string word;

while (cin ＞＞ word)

++word_count[word]; // fetch and increment the counter for word

for (const auto &w : word_count) // for each element in the map

// print the results

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

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

這裡只有word_count的型別改了，其他都沒有變！如果我們用給之前那個程式用的資料導入給這個程式，那麼得出的結果就會是像這樣：

containers.occurs 1 time

use occurs 1 time

can occurs 1 time

examples occurs 1 time

…

我們依然可以得到每個字正確的字頻，但輸出的結果卻不太可能會照著字母的順序來排列。

2:30:40 2:33:00

有序與無序容器常可交互運用的

2:34:20

Managing the Buckets

對於貯體(Buckets，桶；貯體；儲存區)的管理【貯體可以理解成元素的元素。無序容器是無序的，但貯體卻「似」有序，所以無序容器本身並無迭代器可用，但貯體卻有！因此對元素的存取，就落在貯體身上，而不是無序容器的本身。可說是無序容器授權貯體幫他（代理）元素的查找與組織工作】

無序容器是由一群貯體（a collection of buckets）來組成的管理它的元素的。每個貯體或有元素，或無。無序容器用雜湊函數來將元素映射（map）到貯體（bucket），使每個元素與其貯體相關聯。要存取一個元素，容器會先算出該元素的雜湊值（hash code），以便知道要在哪個貯體裡去找（search）到這個元素。容器會把它所有相同雜湊值（hash value）的元素都放在同一個貯體中。如果這個容器的鍵值是可以重複的，那麼所有相同鍵值的元素也都會被容器安排放在同一個貯體（bucket）中。因此，無序容器的性能就取決於它的雜湊函數（hash function）的效能、且也要看它所含有貯體（bucket）有多少以及其各個貯體的大小。

The unordered containers are organized as a collection of buckets, each of which holds zero or more elements. These containers use a hash function to map elements to buckets.

無序容器是藉由貯體（bucket）來存取元素的

其效能的優劣也取決於它貯體的多寡與大小（及雜湊函數的性能）。

To access an element, the container first computes the element’s hash code, which tells which bucket to search. The container puts all of its elements with a given hash value into the same bucket. If the container allows multiple elements with a given key, all the elements with the same key will be in the same bucket. As a result, the performance of an unordered container depends on the quality of its hash function and on the number and size of its buckets.

computes the element’s hash code應即是hash function的工作

藉由貯體來存取元素，在尋找時也是先找貯體再找其旗下的元素

「貯體」猶「部門、麾下」也

頁445

只要引數相同，雜湊函數運算出來的結果也應該要一樣。（也可翻成：當用同值引數呼叫雜湊函數時，其所產生的結果也當一致。）最理想的是，雜湊函數有能力將每個貯體賦與一個特定的對映值（map each particular value to a unique bucket）。2:51:25

The hash function must always yield the same result when called with the same argument. Ideally, the hash function also maps each particular value to a unique bucket.

3:3:55

類似將貯體（bucket）也標上索引

即便如此，雜湊函數還是可以將不同鍵值的元素放在同一個貯體（bucket）中。當一個貯體內已有元素，在其內尋找元素便是經由循序的方式來比對的。在一般情況下，算出元素的雜湊碼（hash code）及在此雜湊碼對應的貯體（bucket）內尋找元素的速度是很快的。然而若一個貯體（bucket）有了太多元素，因為需要更多的比對運算，在這貯體內尋找元素的時間自然就會拉長。

無序容器也提供了一些成員函式，詳表11.8中所列。這些成員函式都是操作（manage）貯體（bucket）用的。【可見無序容器是先操作貯體，才輪到元素的操作。沒有貯體，想對元素存取就會沒轍】它們讓我們得以了知容器的現狀，也可以（and）強制它重組重新組織成我們需要的樣子。（and force the container to reorganize itself as needed）

However, a hash function is allowed to map elements with differing keys to the same bucket.

When a bucket holds several elements, those elements are searched sequentially to find the one we want.

無序到頭、最後還是需要有序循序sequentially來尋找

Typically, computing an element’s hash code and finding its bucket is a fast operation. However, if the bucket has many elements, many comparisons may be needed to find a particular element.

常見的情況下，計算一個元素的hash code並找出它的貯體會是一種快速的運算。然而，如果那個貯體有很多元素，就可能需要進行許多比較才得以找到一個特定的元素。（中文版翻譯）

Typically一般的情形、狀況是→一般說來

3:27:14

Table 11.8. Unordered Container Management Operations 對無序容器的操作 無序容器的管理 無序容器的運算 4:13:50

Sub 說解_在標題樣式中尋找字串()VBA程序修改4:17:30 4:36:50 5:8:17 成功



表11.8 :無序容器的運算



貯體的介面函式（Bucket Interface）貯體的接口函式

c.bucket_count() 使用中的貯體數。【已配置的貯體數】

c.max_bucket_count() c容器可容納的貯體（bucket）數。【守真按：此數會非常大！可能是size_t的上限。參見程式碼測試】第96集9:33:55【可配置的貯體數】



c.bucket_size(n) 在第n個貯體的大小（即其中的元素量）。【第n+1這個貯體內的元素多少（個數）。n均從0開始，且小於bucket_count()。】

c.bucket(k) 找到元素鍵值為k的貯體。【守真按：回傳的值是size_t型別，表第n+1個貯體（bucket）】

巡覽貯體內元素用的機制（Bucket Iteration）

local_iterator 存取貯體內元素用的迭代器（非常值（nonconst）的貯體迭代器）

【此乃c型別容器的型別成員（type member）】

const_local_iterator 常值的貯體迭代器

c.begin(n)、c.end(n) 回傳一個指向貯體n的第一個元素和最末元素後一個位置的迭代器。

c.cbegin(n)、c.cend(n) 回傳的是常值的貯體迭代器（const_local_iterator）

雜湊布局用的函式（Hash Palicy）布排布置雜湊用的函式。設置雜湊之方式

以雜湊組織無序容器的相關運算

c.load_factor() 回傳一個float，表示各貯體中元素量的平均數。

（即貯體的平均元素數是多少。load表乘載量）

【這裡用factor是為了與element有所區隔；所以在貯體中的元素element就叫factor】

c.max_load_factor() 傳回一個float，表示c容器試著維持的平均貯體大小。c容器藉由增加貯體來保持load_factor＜=max_load_factor。【就是實際承載量要不大於它這個容器的理想貯體所能承載的量】

c.rehash(n) 重組重新安排（組織）儲存區，以便bucket_count＞=n而且bucket_count＞size/max_load_factor。size是c此容器的size成員函式。【守真按：經測試，boucket_count一定是2的次方。】

c.reserve(n) 重新調整（reorganize，重組）c，使得它可在不經由rehash的前提下來放得下n個元素。【可見rehash類似refresh、recalc、requery，一切歸零、從頭來。】【守真按：懷疑此elements（元素）是buckets（貯體）之訛。因為這裡的「n」都和貯體（bucket）有關。經測試當是貯體（bucket）才對！第96集9:33:00。可見英文版又錯了！這是要在不rehash，重新配置容得下n個貯體的貯體量。即bucket_count＞=n；boucket_count一定是2的次方。可能：哪些元素配置到哪些貯體，這是rehash的工作；而不重新配置元素到貯體，僅僅是重新配置貯體數，就用reserve，reserve（保留）的意思就是不動到元素與貯體的關聯性。但實際測試又不盡然】



4:5:50 4:9:00

無序容器（unordered container）就有點像多維陣列（陣列的陣列），它是容器(即bucket)的容器

。因為無序容器本身沒有迭代器（iterator），但它內部的貯體（bucket）卻有！



Requirements on Key Type for Unordered Containers

無序容器鍵值型別的必備條件

5:18:20

在預設情況下無序容器是用鍵值型別的等於運算子「==」來做元素間的比對工作。無序容器也會用hash＜key_type＞這樣的型別物件來為每一元素產生一個雜湊值（hash code）。【守真按：可見雜湊值的型別就是hash＜key_type＞！其實，無序容器根本上是元素無序時才用，而要管理無序的元素，故用雜湊值好像為之作有規則的歸納、索引。有序的容器既然可以依其鍵值排序，那麼無序的容器，就是藉由雜湊值來作為「鍵值」以利「排序」；可以說雜湊值就是為了「假排序」而設。應該是在取得元素的雜湊值以歸類放置於貯體後，再根據其鍵值的「==」等於運算子來作比對】程式庫為內建型別（built-in type）提供了各種適用的hash模板（template），包括指標型別（pointers）。程式庫也為程式庫型別定義了hash函式，這些程式庫型別包括了string、與在12章會談到的智慧指標（smart pointer）型別。因此我們可以直接對元素鍵值為內建型別（包括指標型別）、或string型別、甚至智慧指標型別的無序容器下定義。

當然我們並不能直接去定義那些以我們自己定義的類別為元素鍵值型別的無序容器。我們不能像無序容器那樣直接使用hash模板，我們只能提供自己的hash模板（template）。5:18:20 沒錄到的部分就請看臉書直播495集 https://www.facebook.com/oscarsun72/videos/2558392170938568/ 5:29:50 在§16.5（頁709）中我們會學到如何定義自己的hash模板（template）。

預設情況下，無序容器是用鍵值型別的等號運算子來作其元素間的比對操作

They also use an object of type hash＜key_type＞ to generate the hash code for each element.

無序容器也用上hash＜key_type＞ 這樣的型別物件來產生一個元素的雜湊碼（hash code）

The library supplies versions of the hash template for the built-in types, including pointers.

5:59:00程式庫為內建型別（builtin type）包括指標（pointer）提供了多種hash模板（template）

程式庫也為一些程式庫型別（library type）定義了一些hash ，包括string型別和在第12章要談到的智慧指標型別（smart pointer types）

6:0:30

但是我們自定義的類別型別（class type）就不能直接套用hash模板hash template（雜湊模板）來作為無序容器的鍵值型別了，而是要自己定義自己的hash模板（在頁709會再討論）

頁446

雖然不能用預設的hash模板，但我們仍可以用像對有序容器那樣自定義一個比較運算（函式）來取代預設的鍵值比對（即類別對等於運算子「==」的定義。§11.2.2，頁425），以便來處理無序容器。如若以Sales_data來作為無序容器元素的鍵值，我們就必須提供一個Sales_data自己的比較運算（這包括了自定義的等於運算子「==」及算出雜湊碼（hash code）的運算）來執行無序容器內元素的比對。因此在這裡我們會先把這些必要的運算給定義出來以函式的形式來表現出來：

要使用Sales_data作為鍵值，我們得提供函式來取代==運算子，並計算一個hash code。我們會先從定義這些函式開始：（中文版的翻譯）

第96集10:36:00

size_t hasher(const Sales_data &sd)

{

return hash＜string＞()(sd.isbn()); //【守真按：可見不能直接用，卻可間接用hash！()應是不具名函式，而其後為參數列（parameter list），其前為回傳型別；非也「()」為「hash＜string＞」定義的呼叫運算子（call operator：size_t operator()）而「size_t」是這個運算子回傳的值，「(sd.isbn())」則是要傳給這個運算子的引數！！10:43:30可見定義運算子只不過是在函式名稱上要用「operator」這個關鍵字，且其後緊接著一個運算子的符號，如「operator==」就是定義等於運算子「==」，而「operator()」就是定義呼叫運算子「()」

//因為isbn成員函式回傳的值型別也是string，所以要用hash＜string＞，要具轉型關係才行！也未必！因為這個isbn是作為「hash＜string＞」定義的呼叫運算子的引數的，故要符合其引數型別。】

}

// eqOp：equal Operator：這eqOp函式的功能就等於「==」的作用了！

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

{

return lhs.isbn() == rhs.isbn();//【守真按：兩個這樣型別(Sales_data)的元素的比對運算。】

}

我們這個hasher函式利用了一個程式庫對string的hash型別物件來從ISBN資料成員產生一個雜湊碼（hash code）。同樣地，eqOp函式也藉由比對兩個Sales_data間的ISBN值來定義「eqOp」的意義是什麼要做什麼。【守真按：因為isbn成員函式回傳的仍是string，這eqOp也是借用string的等於運算子「==」來進行自己的運算】

有了上開兩個自定義的運算，我們就可以據此創建一個具有Sales_data鍵值的無序容器unordered_multiset了：

無序容器（unordered container）與其說是無序，倒不如說是先歸類、再排序的容器。

分類就是取得hash code（號碼牌）和歸入bucket的過程

有了上述的hash函式的定義及對==運算子的定義，我們就可以用Sales_data這個型別來定義一個無序容器的鍵值型別

using SD_multiset = unordered_multiset＜Sales_data, decltype(hasher) *, decltype(eqOp) *＞;

//這樣定義的型別其引數是：1貯體（bucket）的大小，2對hash函式的指標，3等於運算子//arguments are the bucket size and pointers to the hash function and equality operator也就是這種自定義類別為鍵值的無序容器是沒有預設建構器，一定都要傳入這樣的引數才行(這裡還有許多重載，詳第96集 11:55:00

SD_multiset bookstore(42, hasher, eqOp);

hasher、eqOp函式名稱當引數傳遞時，預設就是轉作為函式指標（function pointer）型別來傳遞

為了要簡潔對bookstore這個unordered_multiset容器的定義，所以我們在一開頭就定義了這樣的型別別名（§2.5.1，頁67）SD_multiset。它的雜湊與等於運算是有著和我們所定義的hasher以及eqOp函式一樣的型別。用了這樣的型別，我們就可以定義（創建）一個bookstore這樣的unordered_multiset無序容器，並用它所需要的函式指針來傳給它作為引數。【守真按：至於unordered_map的型別寫法，則如：

typedef unordered_map＜Sales_data,size_t, decltype(hasher)*, bool(*)(const Sales_data & lhs, const Sales_data rhs)＞ um;因為map除了鍵值還有「值」，所以這裡型別定義中前面兩個就是「鍵值與值對組」，後面接的和unordered_set是一樣的】

如果我們的類別已有它自己定義的等於運算子「==」，那麼我們就可以只覆寫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:50:00

練習11.37

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

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

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

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

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

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

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

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

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

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

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

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

頁438

表11.7 :尋找關聯式容器元素的運算

對無序容器而言，並沒有lower_bound 和upper_bound運算。

下標和at函式也只能用在非常值的map與unordered_map上。

c.find(k) 回傳一個指向（第一個）k鍵值的元素，當k並不存在於容器中，就回傳一個尾端後迭代器（off-the-end iterator）。

c.count(k) 回傳在容器c中鍵值為k元素的數目。對鍵值不可重複的容器來說，回傳的值永遠是0或1。

c.lower_bound(k) 傳回一個迭代器，指向第一個鍵值不小於k的元素。

這個運算應該只能在有嚴格的弱次序上才能用，應是利用此次序來定位的。下upper_bound同，所以在無序容器中是不能用的。無序容器只有群組化能力，沒有排序的功能。第96集2:32:00

c.upper_bound(k) 傳回一個迭代器，指向第一個鍵值大於k的元素。

c.equal_range(k)

傳回一個由2個迭代器組成的對組（pair）物件，來指出所有鍵值是k的元素。如果容器c中並沒有這樣的鍵值，那麼回傳的pair，其2個迭代器都會是c.end()【即尾端後迭代器】。

Returns a pair of iterators denoting the elements with key k. If k is

not present, both members are c.end().【經測試後，這個pair的first即lower_bound回傳的，而secend即upper_bound回傳的，但在無序容器中，只有equal_range運算，卻沒有lower_bound與upper_bound運算；因此若有需要在無序容器中取得這二個運算的傳回值，就可以用equal_range來取代】