C++自修入門實境秀、C++ Primer 5版研讀秀 69/ ~ v11關聯式容器 Chapter 11~11.1. Using an As...
頁420
Associative containers support efficient lookup and retrieval by a key.
The two primary associative-container types are map and set .
The elements in a map are key–value pairs:
一個map中的元素是鍵值與值對組（key-value pairs）:
對組，還真是文言文呢！→加個「的」就白話點了：鍵值與值的對組 第69集1:20
The key serves as當作 an index into the map , and the value represents the data associated with that index.
第69集 3:00這裡用「into」就像迭代器也用這個介係詞，就知道index(key)是一樣或類似的東西了 不見題目只見關鍵字value就是類似解參考迭代器之後的元素值
A set element contains only a key; a set supports efficient queries as to whether a given key is present.
A dictionary would be a good use for a map : The word would be the key, and its definition would be the value.
字典（dictionary）會是map的好用處：字詞會是鍵值，而其定義則是值。
→ 第69集 7:00 如果要編字典，map就應該would委婉、推測、假設派得上用場
字典就是map應用的一個範例
∵ 模範生就是好榜樣 ∴ 得上、好→範
此句應翻成：如果說would假設、比況，字典是map應用的一個絕佳示範，那麼字典中的字詞，就如map的鍵值（key），而該字詞的定義，就是那個值（value）。
17:40
程式庫提供了8個關聯式容器，見表11.1
這8個又可以從以下3個面向來作區別：
（1）它們是set還是map？
（2）鍵值是否重複？是否有重複（multiple,can appear multiple times 59:20）的鍵值，或不可重複（i.e.唯一、絕對的鍵值）
（3）鍵值可有排序？元素的儲存(從上下文來看，鍵值與元素應是同步的)是有序的還是無序的
These eight differ along three dimensions:
這八種之間的差異可用三個維度描述
多重鍵值（multiple keys）
25:20
若允許多重鍵值（重複鍵值？）的容器，會包括關鍵字「multi」
鍵值是無序的則會在其容器前冠上「unordered」（未經排序的）字樣（i.e.關鍵字）
31:30
就好像前面演算法的命名規則naming convention（10.5.3. Algorithm Naming Conventions）
關聯式容器也有其命名規則：
Hence an unordered_multi_set is a set that allows multiple keys whose elements are not stored in order, whereas(=however) a set has unique keys that are stored in order.
一個unordered_multi_set就是允許多重鍵值，而且元素並沒有依序儲存的集合（set)，而一個set則是只具有唯一鍵值，而且這些鍵值是依序儲存的。
中文版「unordered_multi_set」誤作「unordered_multiset」
這是拿unordered_multi_set 和set （i.e.沒有前綴字的plain或ordinary的set）來對比。謂若一個set是只有唯一鍵值且是有序的。
無序的容器是用hash函式來組織它們的元素，在11.4（頁443）再詳述。
hash function（雜湊函數）
map和multimap是定義在map標頭檔
set和multiset是定義在set標頭檔
無序容器則分別在unordered_set和unordered_map標頭檔中
53:30
Table 11.1. Associative Container Types
表11.1:關聯式容器型別
元素以鍵值排序
map 關聯式陣列；存放鍵值與值對組(key-value pairs)
set 鍵值就是值的容器the key is the value
multimap 一個鍵值能在其中出現多次的map
multiset 一個鏈值能在其中出現多次的set
無序群集
unordered_map 以一個hash(雜湊）函數組織的map
unordered_set 以一個hash函數組織的set
unordered_multimap 經雜湊（hashed)的map ;鍵值能夠出現多次
unordered_multiset 經雜湊的set ;鏈值能夠出現多次
11.1. Using an Associative Container
1:2:59
群集（collection）
each pair might contain a person’s name as a key and a phone number as its value. We speak of such a data structure as “mapping names to phone numbers.”
人名好像地圖，而電話號碼好像地物、地點，由人名找到對應到電話號碼就如依地圖找到地點、地圖一樣
map通常被叫作關聯式陣列（associative array）
map 型別常被稱作關聯式陣列（associative array）。
頁421
關聯式陣列（associative array）就如一般的陣列，只是它的索引值不必是整數！對其做下標（subscript）運算時不必傳遞整數。
一個map 中的值是以一個鍵值找到，而非藉由它們的位置。
Given a map of names to phone numbers, we’d use a person’s name as a subscript to fetch that person’s phone number.
給定名字對電話號碼的一個map
names to 對應、對映、映射到phone numbers
Given a map of names to phone numbers如果有一個由人名可以找到電話號碼的map
bad checks 空頭支票 開空頭支票，「開」用 write
1:24:40
Using a map
仰仗關聯式陣列（associative array）的典型範例就是一個像word-counting這樣的程式：
仰賴關聯式陣列的一個經典範例是字詞計數程式：
字頻詞頻程式
藉由字找到該字的頻率（count）所以字是地圖（map）而頻率是地點、地物
from地圖to地點
// count the number of times each word occurs in the input
map＜string, size_t＞ word_count; // empty map from string to size_t
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;
first就是key，second就是value 這樣的一對（pair）對組
1:38:20
Like the sequential containers, the associative containers are templates (§ 3.3 , p. 96 ). To define a map , we must specify both the key and value types.
是模板（templates）的，在使用時定義一個關聯式容器（associative container）時都要加上角括弧＜＞來指定用來組建的型別
map＜string, size_t＞
這裡string就是key的型別，而size_t就是value的型別
當我們對map物件下標（subscript）時，我們傳遞的是這裡的stirng：
When we subscript word_count , we use a string as the subscript, and we get back the size_t counter associated with that string .
所以才叫關聯式陣列（associative array）或關聯式容器（associative container）
If word is not already in the map , the subscript operator creates a new element whose key is word and whose value is 0 .
第一個傳入的word，這個word鍵值key對應的關聯的值value就會是0。是由下標運算子（[]運算子,subscript operator）來建立的元素
我們可以取巧將對組（pair）一對呼之戲稱為老伴、牽手（value就是key的另一伴。）
因此，這句就可以翻成，下標運算子會締結促成一對佳偶，男的就是key，目前有word的值；而他的另一伴就是value，目前的值則是0。
可以說map的元素值是一種複合的值，聚合了鍵值索引值——key，MS Access資料庫中就叫索引值與值、記錄的複合、結合的值。
2:3:00 原來pair還是一種型別：
When we fetch an element from a map , we get an object of type pair , which we’ll describe in § 11.2.3 (p. 426 ). Briefly, a pair is a template type （模板型別）that holds two ( public ) data elements named first and second .
2:26:00
#include＜iostream＞
#include＜iterator＞
#include＜map＞
using namespace std;
int main() {
istream_iterator＜string＞in(cin), end;
map＜string, string::size_type＞m;
while (in != end)
{
++m[*in];
++in;
}
//ostream_iterator＜int＞out(cout, ",");//無法用，因map元素為pair型別
for(auto var : m)
cout＜＜var.first ＜＜ " " ＜＜var.second＜＜ endl;
}
頁422
Using a set
2:31:09
set可翻成「些」或「組」
2:48:00
// count the number of times each word occurs in the input
map＜string, size_t＞ word_count; // empty map from string to size_t
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
if (exclude.find(word) == exclude.end())
++word_count[word]; // fetch and increment the counter for 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;
}
2:49:33
set也是模板（template）
關聯式容器（associative container）也可以串列初始化（list initialization）：
As with the sequential containers, we can list initialize (§ 9.2.4 , p. 336 ) the elements of an associative container.
set的find()的成員函式
練習11.1
3:6:30 map和vector加入元素的方式好像一樣。然而map的每個元素有一「對組（pair）」值，而vector沒有。插入新元素須分別指定這對組值各個成員的值；尋找亦須由鍵值（key，即對組值的first成員）來找，不能用位置來下標（subscript）。
練習11.2
3:8:40
如果要隨機存取，須具備隨機存取迭代器（random-access iterator）的容器（container）
如果要從尾端插入新元素，則vector、deque、list都能用。若要隨機插入，用插入迭代器（insert iterator）也都能用，效率可能也差不多。首端插入則deque、list應該才好。
list在排序等演算法中，應用其成員函式的演算法會更有效率。
set主要是用在儲存一個需要檢查、調閱用的串列
map主要是用在已知一個元素鍵值想來查找它對應的值的地方。而map既然有關聯式陣列（associative array）的美名，則應該會與一般陣列（內建型別（builtin type）陣列）一樣有效率。
Give an example of when each of list, vector, deque,map, and set might be most useful.
an example
對獎
排班、行事曆
訂位系統
練習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;
}
4:10:50
練習11.4
複習前面
3.2.2. Operations on string s
3.2.3. Dealing with the Characters in a string
ispunct函式
5:25:20
5:40:10
Table 3.3. cctype Functions
6:24:00
#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;
}
6:31:10 6:42:00 6:49:00
改用泛用演算法來寫 6:50:40測試
失敗，再研究 7:24:00
Adding Literals and strings
第69集 4:29:00
The string library lets us convert both character literals and character string literals (§ 2.1.3, p. 39) to strings. Because we can use these literals where a string is expected, we can rewrite the previous program as follows:
string s1 = "hello", s2 = "world"; // no punctuation in s1 or s2
string s3 = s1 + ", " + s2 + '\n';
單引號的就是character literals 雙引號括起來的則是character string literals
頁90
When we mix strings and string or character literals, at least one operand to each + operator must be of string type:
這裡的「string」指的是character string literals，不是string
字串字面值（string literal）和程式庫型別（library type）string 是不同的型別！
string s4 = s1 + ", "; // ok: adding a string and a literal
string s5 = "hello" + ", "; // error: no string operand
string s6 = s1 + ", " + "world"; // ok: each + has a string operand
string s7 = "hello" + ", " + s2; // error: can't add string literals
「s1 + ", " + "world"」是先評估左邊的「s1 + ", "」結果是string型別，再評估「string+ "world"」所以才可以。 第69集 4:37:10
同理「"hello" + ", " + s2;」則是先評估了左邊的「+」，這個「+」運算子兩邊都是字串字面值（string literal），並沒有string型別（程式庫型別）所以是錯的
3.2.3. Dealing with the Characters in a string
第69集 4:50:00
頁91
It turns out that the best way to deal with these cases involves different language and library facilities.
我們可以看到，應付這些情況的最佳方式涉及了不同的語言和程式庫機能。
這語言是人的語言，還會程式語言？⑧找對主詞 ⑨對錯問題,回到二作 當然是程式語言
一組程式庫函式……這些函式定義於cctype標頭
因為只是承繼自C語言的，所以刪除副檔名的.h，而再在檔名前冠上c來註明此標頭實是C語言的版本，不是C++的：
(C語言程式庫)這些標頭的C++版本則被命名為cname，移除了後綴的.h並在前面加了字母c。c代表的是此標頭為C程式庫的一部分。
因此， cctype與ctype.h有相同的內容，但存在的形式適用於C++。
特別是，定義在cname 標頭中的名稱是被定義在std命名空間內，而定義在.h版本中的那些則否。
第66集 5:0:18 也就是C++的版本會獨立在標頭檔.h中，而C語言的版本則是被定義在std命名空間中。
一般來說，C++程式應該使用cname版本的標頭，而非name.h版本的。
也就是要用C程式庫的，而不是C++程式庫的版本！？
如此一來，源自標準程式庫的名稱就能一致地於std命名空間中被找到。若使用.h標頭，就等於把責任放在程式設計師身上，要他們記得哪些程式庫名稱繼承字C，而哪些是C++獨有的。
字→自
因為C語言的被併到std中了，反而用C語言的版本，才能一致地於std命名空間中被找到
Processing Every Character? Use Range-Based for
Range for
for (declaration:expression)
statement
其中expression是型別代表一種序列的一個物件，
→其中expression是代表序列型別的一個物件。
where expression is an object of a type that represents a sequence,
第69集 5:17:00
一個string代表一個序列的字元，
程式庫string型別與字元的關係。序列就是後面提到的循序容器（sequential container）。
string s("expression");
for (auto c:s)
{
cout ＜＜ c ＜＜ endl;
}
這裡的auto判斷其實就是char
迴圈控制變數
即迴圈內定義的區域變數
第69集 5:21:40
頁92
ispunct函式
參見練習11.4
舉個稍微複雜一點的例子，我們會用一個範圍for和ispunct函式來計數一個string中的標點符號字元（punctuation characters）的數目：
string s("Hello World!!!") ；
// punct_cnt的型別與s.size回傳的相同，參閱§2.5.3（頁70）
decltype(s.size()) punct_cnt = 0; //計數s中的標點符號字元之數量
for (auto c : s) //對s中的每個字元
if (ispunct(c)) //如果該字元是一個標點符號
++punct_cnt; //遞增標點符號計數器
cout ＜＜ punct_cnt
＜＜ " punctuation characters in " ＜＜ s ＜＜ endl;
Table 3.3. cctype Functions
表 3.3 : cctype 函式
isalnum(c) 如果c是一個字母（letter）或數字（digit）就為true。
isalpha(c) 如果c是一個字母就為true。
iscntrl(c) 如果 c 是一個控制字元（control character）就為 true。
isdigit(c) 如果c是一個數字就為true。
isgraph(c) 如果c不是一個空格（space)但是可列印的（printable)就為true。
islower(c) 如果c是一個小寫（lowercase)字母就為true。
isprint(c) 如果c是一個可列印的字元（即一個空格或有可視表達形式的字元）就為 true 。
ispunct(c) 如果c是一個標點符號字元（punctuation character，即不是控制字元、數字、 字母或可印空白的字元）就為true。
isspace(c) 如果 c 是空白（whitespace，即一個 space、tab、vertical tab、return、 newline 或 form feed )就為 true 。
isupper(c) 如果c是一個大寫（uppercase)字母就為true。
isxdigit(c) 如果c是一個十六進位數字（hexadecimal digit)就為true。
tolower(c) 如果c是一個大寫字母，就回傳其小寫；否則原封不動地回傳c。
toupper(c) 如果c是一個小寫字母，就回傳其大寫；否則原封不動地回傳c。
用c表char（character） 第69集5:36:10
al：alphabet
graph：指圖表用的定位符號
頁93
Using a Range for to Change the Characters in a string
留言