C++自修入門實境秀、C++ Primer 5版研讀秀 92/ ~12.3.1. Design of the Query Program~練習1...
C++ Primer Fith Edition研讀秀第二篇第11章重譯
Word VBA 調整縮排 20:00
Sub indents()
Dim p As Paragraph
For Each p In ThisDocument.Paragraphs
If p.Range.ParagraphFormat.LeftIndent = 416 Then ' CentimetersToPoints(14.67) Then
p.Range.ParagraphFormat.LeftIndent = CentimetersToPoints(0)
End If
Next p
End Sub
Chapter 11. Associative Containers 關聯式容器
11.1 使用關聯式容器（associative container）
11.2 關聯式容器的概觀
11.3 關聯式容器的相關運算
11.4 無序的容器
本章大要
已觸及的詞彙（defined terms）
關聯式容器與循序容器（sequential container）根本的不同在於：關聯式容器的元素是藉由鍵值來存取的。而循序容器的元素則是藉由它們在容器中的位置依序（循序）地被存取。
即使關聯式容器與循序容器在許多方面仍是相似的，但它和循序容器最關鍵的不同就表現（reflect）在它用到了鍵值（key）這個東西，而循序容器沒有！
藉由鍵值的使用，關聯式容器得以進行極具效能的檢索工作。關聯式容器其實只有map和set這兩種型別。在map中的元素，其實質型別是一個鍵值與值的對偶（key-value pairs，鍵值與值對組）。鍵值就是map中的索引值，而值（value）則表示了這個鍵值關聯到的資料是什麼。（所以才叫做關聯式容器。）set內的元素則只是鍵值，它主要的用途是被用來作為檢查的機制，以查看一個指定的值是否存在於它之中。例如，在文字處理的工作上，我們可能會藉由set的這種特性（特別的性能）來存放一些我們想要忽略的字詞，以備在處理文字時，作為比對篩選的依據。而map的用途，我們可以想像一下我們常用到的詞典，它其實就是map得以應用的實例；在詞典中所收的詞彙就是map裡的鍵值（key），而這個詞彙的定義，就是它的值（value）。
C++程式庫雖然提供了多達8種的關聯式容器（詳見表11.1所列）。可是這8種型別其實只是為了下面3種不同的需求而作出的區別：
（1）是set或是map呢？ 第92集50:20 「a」翻「是」 翻譯學！1:14:20
（2）鍵值可否重複？
（3）鍵值元素是有順序的、還是無序的
若鍵值可以重複的話，那個關聯式容器在其類別名稱上就會多出「multi」這樣的字樣。若鍵值是未經排序的，則會在它們的類別名稱前冠上「unordered」這樣的字樣。因此，像「unordered_multi_set」 這個類別（名稱）就是表示它是一個無序的、鍵值可重複的set。而「set」（沒有任何「unordered」或「multi」字樣的）就只是一個鍵值不能重複，且鍵值元素是經過排序的set。57:10 1:21:59而若是鍵值元素未經排序的無序容器（unordered containers）其鍵值元素的存取，則須利用一個叫做「hash」的函式來處理。在後面的11.4（頁443），我們才會詳加說明，什麼叫做雜湊函數（hash function）。
Associative and sequential containers differ from one another in a fundamental way: Elements in an associative container are stored and retrieved by a key.
關聯式容器和循序容器有一個基本差異：關聯式容器中的元素是以一個鍵值（key）來儲存和 取回的。
In contrast, 而 elements in a sequential container are stored and accessed sequentially 依序存取by their position in the container.
這是position和key的對決
頁420
Table 11.1. Associative Container Types
表11.1:關聯式容器的各種型別
鍵值元素有序的
map 關聯式的容器（Associative array），裡面放的是（holds）鍵值與值對組（key-value pairs）型別的元素
set 這種容器（container）的鍵值就是其值（the key is the value）
Multimap 是個鍵值可以重複的map
Multiset 鍵值可以重複的set
無序容器（collections）
unordered_map 藉由雜湊函數（hash function）來管理的map
unordered_set 藉由雜湊函數來管理的set
unordered_multimap 由雜湊函數管理的map(Hashed map)，其鍵值可以重複
unordered_multiset 由雜湊函數管理的set(Hashed set)，其鍵值可以重複
map和multimap是定義在map標頭檔
set和multiset是定義在set標頭檔
無序容器則分別在unordered_set和unordered_map標頭檔中
11.1. Using an Associative Container
使用關聯式容器（關聯式容器的使用）
1:48:40 1:49:50 沒錄到的可看臉書直播第464集
雖然大部分的程式設計師對vector和list這樣的資料結構都已經非常熟悉了，但卻有許多還未曾用過關聯式容器這樣的資料結構。在我們繼續深入了解C++程式庫是如何支援這樣的資料類型前，如果能先用一個實際的例子來演示這些關聯式容器是如何地被利用的，對我們認識它們將會有莫大的助益。
map可以說就是一個裡頭裝了鍵值與值對組（key-value pairs）元素的容器（collection）。這樣的對組（pair），就好比由一個人名作為鍵值、而這個人的電話號碼則是其「值」（value）的組合。一般形容這樣的資料結構是由人名來映射（map，關聯）到他的電話號碼的。map這樣的容器也常被看作是關聯式的陣列（associative array）。關聯式陣列和一般的陣列（"normal" array)沒什麼不同，只是它的下標（subscript）運算接受的值並不限於正整數（integers）而已。在map中要找到的一個指定值(values)是藉由鍵值的值來找、而不是由其所在位置來決定的。若map裡的元素是一個人名對應到電話號碼型別的元素，那麼要擷取某人的電話號碼，就是利用這個人名作為下標（subscript）的依據（運算元）來擷取的。
相對的，set就只是一群鍵值的集合。set最常見的用法就是用來判斷一個值是否存在。比如在商業的應用上，我們可以利它，定義一個名叫bad_checks的set，用來存放曾經開過空頭支票的黑名單。當我們需要兌現一張支票時，就可以利用這個set來檢查看看，這張要兌現的支票，其開票人是否在這黑名單內。
頁421
1:59:10
Using a map
使用map（map的使用）
下列的字頻計算程式就是用到關聯式容器（associative arrays）的典型範例。此之所以用「array」是為了與下標運算子（[]運算子,subscript operator）來搭配。
//計算輸入的文字出現的次數
map＜string, size_t＞ word_count; //從string 對應到size_t的一個空的map容器
string word;
while (cin ＞＞ word)
++word_count[word]; //擷取輸入文字出現的次數，並遞增其值
for (const auto &w : word_count) //將map中的元素值一一列出出來。
cout ＜＜ w.first ＜＜ " occurs" ＜＜ w.second ＜＜ ((w.second ＞ 1) ? " times" : " time") ＜＜ endl;
以上程式會讀取標準輸入的內容中所含的文字，並列出這些文字它們各出現了幾次。
因為關聯式容器和循序容器都是模板（template，§3.3，頁96），所以要定義一個map，我們就必須同時帶入鍵值與值的型別。在以上程式中，這個map的元素是一對鍵值為string而值為size_t的對組（§3.5.2，頁116）。當我們要對這個map作下標，我們是用一個string型別的值來作為下標運算元帶入，而下標運算的結果則是傳回一個size_t型別的計數，這個計數就是帶入的這個string出現的次數。
while迴圈則負責讀取標準輸入的各個文字到程式中，它會用這個文字來對word_count這個map作下標運算。如果這個文字尚未出現在這個map裡，那麼這裡的下標運算子（[]運算子,subscript operator）就會在map中新增一個元素，這個元素的鍵值就是這個文字，而值，則是0（應是size_t的值初始化（value initialize））。【可見map類別中一定有對下標運算子作了以上行為的定義，即對此運算子定義了新增元素的運算！】此時，不論這個元素是不是新加入到map中的，我們都會對它的這個size_t的「值」作遞增計算。
一旦while迴圈讀完了標準輸入的所有文字，range for迴圈（§3.2.3，頁91。可見關聯式容器也可以用range for來存取）就接著對這個map作巡覽（iterates through），逐項地巡覽map中的元素，並列印出它們的鍵值與值出來；這個鍵值就是輸入的每個單字，而值就是這個單字的計數（出現頻率）。擷取map中的元素，得到的結果會是一個型別為pair的物件（東西），這種東西我們會在§11.2.3（頁426）中再詳述。簡單來說，pair這樣的型別是一個模板型別（template type），這種模板型別存放的是一對（two）公用的（public）資料（結構）成員【應該是data members，不是 data elements，英文版這裡應有筆誤！成員才能用到「點運算子」。下文也是作member!】，分別叫作first和second。而這裡map中的元素，其鍵值就是first，而值就是second。所以在以上程式碼所寫的輸出部分，就會把每個輸入的文字和它所對應到的計數值給列印出來。
如果我們將本節第一段的內容當作輸入條件來輸入到上述的程式，那麼我們就會得到以下的結果：
Although occurs 1 time
Before occurs 1 time
an occurs 1 time
and occurs 1 time
…
2:53:00
頁422
Using a set
使用set(如何使用set容器)
3:00:29 3:5:00 這個字頻計數程式若要擴充，可以考慮將一些常用的功能字彙省略掉，諸如"the"、"and"、"or"等字。因此可以利用set的功能來作這樣的計算，將我們想要忽略不計的字彙都存入set中，由此來只對那些我們不想忽略的字作統計，也就是不在set中的字。
// count the number of times each word occurs in the input
//將輸入的文字出現的次數一一作統計
map＜string, size_t＞ word_count; // empty map from string to size_t 空的map，它的元素是由string與size_t組成的對組（pair），且由string可以對應到（找到）size_t
//想要排除的字都放在名為exclude的set容器中//以下是用串列（list initialization）來拷貝初始化（copy initialize）
set＜string＞ exclude = {"The", "But", "And", "Or", "An", "A",
"the", "but", "and", "or", "an",
"a"};
string word;
while (cin ＞＞ word)
// count only words that are not in exclude//只對不在exclude容器中的字彙作計數
if (exclude.find(word) == exclude.end())//利用set的成員函式find來作檢查
++word_count[word]; // fetch and increment the counter for word擷取輸入文字word對應的計數，並遞增之。
#include＜iostream＞
#include＜iterator＞
#include＜map＞
#include＜set＞
using namespace std;
int main() {
set＜string＞st{ "the","an","and","or" ,"be","at","if","to","of"};
istream_iterator＜string＞in(cin), end;
map＜string, string::size_type＞m;
while (in != end)
{
if (st.find(*in) == st.cend())
{
++m[*in];
}
++in;
}
for (auto var : m)
cout ＜＜ var.first ＜＜ " " ＜＜ var.second ＜＜ endl;
}
3:12:20 3:23:40
和其他的容器一樣，set也是個模板（template），所以要定義set容器就必須指明它元素的型別是什麼。在以上程式中，這個型別是string。與循序容器（sequential container）一樣，關聯式容器也接受串列初始化（list initialization，§9.2.4，頁336）。上述程式碼中exclude這個set就存放了12個字彙來作為忽略不計的憑據。
上述程式和之前的不同在於：之前的程式對每個輸入的字彙都作計數，而這個則是在計數之前檢查看看要統計的字彙是否在要排除的清單之中。在if條件式中所寫的，就是這樣的判斷：
//只對不在exclude中的字彙作計數
if(exclude.find(word)==exclude.end())
對set的成員函式find的調用，會回傳一個迭代器。如果set中鍵值有符合我們要找的條件，那麼這個回傳回來的迭代器就會指向那個鍵值；如果要找的並不在set中，那麼find就會回傳一個尾端後迭代器（off-the-end iterator），表示沒有找到。在上述的程式中，我們只會對不在exclude這個set容器中的字彙進行字頻的計算。
因此，以同樣的輸入條件執行上述的程式，我們就會得到以下的輸出結果：
Although occurs 1 time
Before occurs 1 time
are occurs 1 time
as occurs 1 time
...
練習11.1
3:28:07
請描述map和vector有哪裡不同。
map是由鍵值存取，且其元素值為一個鍵值與值的對組型別。
map和vector加入元素的方式好像一樣。然而map的每個元素有一「對組（pair）」值，而vector沒有。插入新元素須分別指定這對組值各個成員的值；尋找亦須由鍵值（key，即對組值的first成員）來找，不能用位置來下標（subscript）。
練習11.2
3:30:01
請各舉一例來說明，使用list、vector、deque、map、set的正確時機。
如果要隨機存取，須具備隨機存取迭代器（random-access iterator）的容器（container）
如果要從尾端插入新元素，則vector、deque、list都能用。若要隨機插入，用插入迭代器（insert iterator）也都能用，效率可能也差不多。首端插入則deque、list應該才好。
list在排序等演算法中，應用其成員函式的演算法會更有效率。
set主要是用在儲存一個需要用以檢查、測試用的串列、清單。
map主要是用在已知一個元素鍵值想來據以查找它對應的值的地方。而map既然有關聯式陣列（associative array）之名，則應該會與一般陣列（內建型別（builtin type）陣列）一樣有效率。map所以暱稱陣列，應該主要是能對其進行下標運算的緣故，和陣列一樣。
對獎
排班、行事曆
訂位系統
練習11.3
請試著寫出您自己版本的字頻計算程式
文件詞頻
#include＜fstream＞
#include＜iterator＞
#include＜map＞
#include＜set＞
using namespace std;
int main() {
set＜string＞st{ "the","an","and","or" ,"be","at","if","to","of"};
ifstream fs("V:\\Programming\\C++\\Untitled-1.txt");
istream_iterator＜string＞in(fs), end;
map＜string, string::size_type＞m;
while (in != end)
{
if (st.find(*in) == st.cend())
{
++m[*in];
}
++in;
}
ofstream ofs("V:\\Programming\\C++\\out.txt");
for (auto var : m)
ofs ＜＜ var.first ＜＜ " " ＜＜ var.second ＜＜ endl;
}
練習11.4
擴充您的字頻程式來汰除大小寫與標點符號所導致的計數差異。如"example."、"example,"、"example"這三種應該都算是同一種，必須將它們的字頻的合併計算。
複習前面：3.2.2. Operations on string s、3.2.3. Dealing with the Characters in a string、ispunct函式、Table 3.3. cctype Functions
3:41:40
#include＜fstream＞
#include＜iterator＞
#include＜map＞
#include＜set＞
using namespace std;
int main() {
set＜string＞st{ "the","an","and","or" ,"be","at","if","to","of" };
ifstream fs("V:\\Programming\\C++\\Untitled-1.txt");
istream_iterator＜string＞in(fs), end;
map＜string, string::size_type＞m;
while (in != end)
{
string s(*in);
for (decltype(s.size()) i = 0; i != s.size(); ++i)
{
if (ispunct(s[i]))
{
s.erase(i, 1);
--i;
}
else
s[i] = tolower(s[i]);//st都是小寫，所以改成小寫，以供st.find(s)比對
}
if (st.find(s) == st.cend())
{
++m[s];
}
++in;
}
ofstream ofs("V:\\Programming\\C++\\out.txt");
for (auto var : m)
ofs ＜＜ var.first ＜＜ " " ＜＜ var.second ＜＜ endl;
}
3:46:55
頁423
11.2. Overview of the Associative Containers
關聯式容器概觀
不論是有序或無序的關聯式容器都支援在§9.2（頁328）談到與在表9.2（頁330）所列出的容器運算，只是關聯式容器並不支援循序容器特有的由位置指定方式來存取的運算，如push_front和back等等。因為關聯式容器只會藉由鍵值來作其元素的存取，所以有關元素位置的運算對它來說並沒有什麼意義。甚至關聯式容器也不支援那種帶了一個元素值與其數量作為引數的建構器和insert運算。
而除了和循序容器共通的運算外，關聯式容器還提供了一些運算（表11.7，頁438）和型別別名（type alias，表11.3，頁429），這些都是循序容器所沒有的。此外，無序的關聯式容器還提供了調整它們hash性能的運算，這個我們會在§11.4（頁444）再來討論。
關聯式容器的迭代器是可以雙向移動的（§10.5.1，頁410）
4:6:29關聯式容器，不管是有序無序的都能做一般容器的運算，如9.2. Container Library Overview 所示及Table 9.2. Container Operations所列
關聯式容器的迭代器是雙向迭代器（bidirectional iterator）
就是不能隨機存取（因為隨機存取與位置有關）而已
11.2.1. Defining an Associative Container
11.2.1定義關聯式容器
留言