C++自修入門實境秀、C++ Primer 5版研讀秀 75/ ~ v11關聯式容器 圓滿
頁87
Using getline to Read an Entire Line
可用getline()取代 ＞＞輸入運算子：
有時候我們不想要忽略我們輸入中的空白。在這種情形中，我們可以使用getline函式，而非 ＞＞運算子
getline函式接受一個輸入資料流以及一個string。這個函式會讀取給定 的資料流，直到第一個newline，並包括這個newline，並將它所讀到的，但並不包括那個 newline，儲存到它的string引數。第75集29:00
就跟輸入運算子一樣，getline回傳其istream引數。
Note:導致getline回傳的newline會被丟棄，這個newline不會被儲存在string中。
11.3.6. A Word Transformation Map
11.3.6 一個字詞變換映射
第75集 6:55
頁441
The Word Transformation Program
transformation在此（中文語境）應譯為「取代字串」
hold可翻成「（交給它）保管」
13:50
void word_transform(ifstream &map_file, ifstream &input)
{
auto trans_map = buildMap(map_file); // store the transformations
string text; // hold each line from the input
while (getline(input, text))
{ // read a line of input
istringstream stream(text); // read each word
string word;
bool firstword = true; // controls whether a space is printed
while (stream ＞＞ word)
{
if (firstword)
firstword = false;
else
cout ＜＜ " "; // print a space between words
// transform returns its first argument or its transformation
cout ＜＜ transform(word, trans_map); // print the output
}
cout ＜＜ endl; // done with this line of input
}
}
頁442
18:50
Building the Transformation Map
建置變換映射
這裡map指的是map這個型別的容器，也不該翻出來
→用一個map 容器來配置取代用的資料
37:00
map＜string, string＞ buildMap(ifstream &map_file)
{
map＜string, string＞ trans_map; // holds the transformations
string key; // a word to transform
string value; // phrase to use instead
// read the first word into key and the rest of the line into value
while (map_file ＞＞ key && getline(map_file, value))
if (value.size() ＞ 1) // check that there is a transformation
trans_map[key] = value.substr(1); // skip leading space
else throw runtime_error("no rule for " + key);
return trans_map;
}
Note that we use the subscript operator to add the key–value pairs. Implicitly, we are ignoring what should happen if a word appears more than once in our transformation file. If a word does appear multiple times, our loops will put the last corresponding phrase into trans_map.
Implicitly,中文語境要翻成這樣→我們這麼做就是想要忽略……怎麼可以英文照，成了洋涇濱中文？
隱含地，我們忽略了一個字詞在我們的變換檔案中出現一次以上的情況。
要這樣翻，根本叫機器翻譯就好啦
Word VBA
插入點處理，顯示所在位置標題
OK 1:17:30 https://snipsave.com/oscarsun72/#/snippet/MYr5TxMRJoeWkps7bg
Generating a Transformation
1:18:59
頁443
const string & transform(const string &s, const map＜string, string＞ &m)
{
// the actual map work; this part is the heart of the program
auto map_it = m.find(s);
// if this word is in the transformation map
if (map_it != m.cend())
return map_it-＞second; // use the replacement word
else
return s; // otherwise return the original unchanged
}
1:42:54
we dereference the iterator, obtaining a pair that holds the key and value for that element (§ 11.3, p. 428).
We return the second member, which is the transformation to use in place of s.
獲取一個pair，其中放有該元素的鍵值與值（§11.3)。
holds這裡翻成「含有、包含了」才好
放有→放了、放著
練習11.33
參見練習11.38
1:49:14
Implement your own version of the word-transformation program.
實作你自己版本的字詞變換程式。
取代字串程式
#include＜iostream＞
#include＜fstream＞
#include＜iterator＞
#include＜map＞
using namespace std;
int main() {
map＜string, string＞mReplace;
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;
map＜string, string＞::const_iterator mIt;
string ocr;
while (input != e)
{
ocr = *input;
mIt = mReplace.find(ocr);
if (mIt != mReplace.cend())
cout ＜＜ mIt-＞second ＜＜ endl;
else
cout ＜＜ ocr ＜＜ endl;
++input;
}
}
2:37:55
練習11.34
如果用下標則會在找不到時，改變map大小，多加了一個元素進去
2:40:06
練習11.35
好像是一樣的吧。除非是說下標者，會改動已有key的value值，而插入insert()者不會（即若鍵值已存在，則不會再插入？）
練習11.36
2:51:00 最後一個元素便不是合法的元素值便不會被加入map
2:52:27
11.4. The Unordered Containers
11.4無序的容器
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）的方式將函式當作引數傳遞給建構子建構元素次第；故為有序容器
2:59:35
無序容器最有用的時機是，當我們有一種鍵值型別，其元素之間沒有明顯的順序關係。這些容器對於維護元素順序的成本令人望而卻步的應用來說，也很實用。
也就是在不需要、沒有必要，或者沒有、乃至無法排序元素的狀況下，都是使用無序容器的
雖然理論上或原則上，無序容器使用了hashing會在平均值上有整體效能上的提升，然而這種效能的取得往往必須付出一定的代價，比如說不斷測試與調整；也因此，反而有序容器在某些時候，反而凌駕其上
頁444
tip:如果鍵值型別本質上就是無序的，或者效能測試之下，顯示出有hashing可以解決的問題，就使用無序容器。
使用無序容器（unordered container）的時機與應有的考量
Using an Unordered Container
使用一個無序容器
除了提供對雜湊（hashing）的運算，無序容器也支援有序容器（循序容器）的運算
the operations we’ve used on map and set apply to unordered_map and unordered_set as well.
3:12:55
對於multi——允許重複鍵值的無序容器也是
也就是這樣，有序與無序容器常可交互運用的
// 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;
3:21:20
Managing the Buckets
管理貯體(Buckets)
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
3:35:55
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.
類似將貯體（bucket）也標上索引
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:42:44
Table 11.8. Unordered Container Management Operations
3:55:00
表11.8 :無序容器的管理運算
貯體介面（Bucket Interface)
c.bucket_count() 使用中的貯體數。
c.max_bucket_count() 這個容器能夠存放的最大貯體數。
c.bucket_size(n) 第n個貯體中的元素數。
c.bucket(k) 在其中可以找到具有鍵值k的元素的貯體。
貯體迭代（Bucket Iteration）
local_iterator 能夠存取一個貯體中元素的迭代器型別。
const_local_iterator 貯體迭代器的const版本。
c.begin(n) 、 c.end(n) 指向貯體n中第一個元素，以及超出最後一個元素一個位置處的迭代器。
c.cbegin(n) 、 c.cend(n) 回傳const_local_iterator。
雜湊策略
c.load_factor() 每個貯體的平均元素數。回傳float。
c.max_load_factor() c試著維持的平均貯體大小。c新增貯體來保持load_ factor ＜= max_load_factor。回傳float 。
c.rehash(n) 重新組織儲存區，讓bucket_count ＞= n而且bucket_ count ＞ size/max_load_factor。
c.reserve(n) 進行重組，讓c可以存放個元素，而不用進行rehash。
無序容器（unordered container）就有點像多維陣列（陣列的陣列），它是容器(即bucket)的容器
。因為無序容器沒有迭代器（iterator），但它內部的貯體（bucket）卻有！
Requirements on Key Type for Unordered Containers
無序容器的鍵值型別的要求條件
無序容器鍵值型別的必要條件、必備條件
鍵值型別，沒有生命，沒有靈識，怎麼會「要求」呢，就像說「自傳的目的」「遙控器的目的」一樣的荒唐與不合邏輯。
中文與語文、邏輯能力不好，就會如此
難怪無時無刻可以成了任何時刻
怎麼學程式語言的語言邏輯還這麼不敏銳呢？只有一個原因，漠視自己母語能力的結果，下場就是如此
預設情況下，無序容器是用鍵值型別的等號運算子來作其元素間的比對操作
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.
程式庫為內建型別（builtin type）包括指標（pointer）提供了多種hash模板（template）
程式庫也為一些程式庫型別（library type）定義了一些hash ，包括string型別和在第12章要談到的智慧指標型別（smart pointer types）
因此，我們可以直接定義鍵值是內建型別（包括指標型別）、string或智慧指標的無序容器。
4:21:00
但是我們自定義的類別型別（class type）就不能直接套用hash模板hash template（雜湊模板）來作為無序容器的鍵值型別了，而是要自己定義自己的hash模板（在頁709會再討論）
頁446
要使用Sales_data作為鍵值，我們得提供函式來取代==運算子，並計算一個hash code。我們會先從定義這些函式開始：
size_t hasher(const Sales_data &sd)
{
return hash＜string＞()(sd.isbn());//可見不能直接用，卻可間接用hash！()應是不具名函式，而其後為參數列（parameter list），其前為回傳型別
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() == rhs.isbn();
}
無序容器（unordered container）與其說是無序，倒不如說是先歸類、再排序的容器。
分類就是取得hash code（號碼牌）和歸入bucket的過程
有了上述的hash函式的定義及對==運算子的定義，我們就可以用Sales_data這個型別來定義一個無序容器的鍵值型別
using SD_multiset = unordered_multiset＜Sales_data,
decltype(hasher) *, decltype(eqOp) *＞;
// arguments are the bucket size and pointers to the hash function and equality operator
SD_multiset bookstore(42, hasher, eqOp);
hasher、eqOp函式名稱當引數傳遞時，預設就是轉作為函式指標（function pointer）型別來傳遞。
如果我們的類別有自己的==運算子，我們可以只覆寫hash function就行了 ：
//使用FooHash來產生hash code，Foo必須有一個==運算子
unordered_set＜Foo, decltype(FooHash) *＞ fooSet(10, FooHash);
4:55:30
練習11.37
無序容器與同版本的有序容器的優缺點
理論上無序容器效能較佳，但限制亦多。如前若要用自定型別作鍵值，必要定義自己的hash函式和等號運算子（或等於運算）
如果hash函式沒設計好或者貯體（bucket）配置不當，也會影響無序容器的效能
有序、無序，二者應是互補的關係
無序容器除了還有雜湊函數（hash function）等特定操作外，其他有序版本有的運算，它都支援，參下題改寫前例，都僅只換了型別便可知。優點是多此功能，缺點也是多此麻煩。
練習11.38
5:0:53
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;
}
}
5:20:40
頁447
Chapter Summary
關聯式容器和循序容器最大的不同就在於它們不是用位置來存取元素的，而是藉由鍵值
總共8種關聯式容器
所以有序容器不是天生有就序，它還是動用到一個比較用的函式才能對其內元素進行排序
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.
5:28:30 5:33:20
不論是有序還是無序的容器，有相同鍵值的元素的都會挨在一塊兒：
Elements with the same key are stored adjacent to one another in both the ordered and unordered containers.
Defined Terms
5:35:40
associative array
Array whose elements are indexed by key rather than positionally. We say that the array maps a key to its associated value.
hash
hash就是一個模板
hash Special library template that the unordered containers use to manage the position of their elements.
可見關聯式容器仍舊逃不掉元素「位置」的存取也！
hash function
把它想成「發號碼牌」就對了
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.
把某個指定型別的值，映射（map）到一個整數值
5:43:40
這種「Equal values must map to equal integers; unequal values should map to unequal integers where possible.」能力就是hash函式的好壞評準，所以決定不是亂雜湊的
map
5:49:00
關聯式容器與關聯式陣列的關係：
map Associative container type that defines an associative array.
map定義一個關聯式陣列的關聯式容器。
頁448
multimap
5:52:20
multimap does not support subscripting.
可見下標（subscript）運算是要在唯一值上操作的。
strict weak ordering
5:55:37
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
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（存放）就是讓元素歸類（先歸類，再排序）
6:9:10
下標運算子（[]運算子,subscript operator）
只對非常值（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.
頁87
Using getline to Read an Entire Line
可用getline()取代 ＞＞輸入運算子：
有時候我們不想要忽略我們輸入中的空白。在這種情形中，我們可以使用getline函式，而非 ＞＞運算子
getline函式接受一個輸入資料流以及一個string。這個函式會讀取給定 的資料流，直到第一個newline，並包括這個newline，並將它所讀到的，但並不包括那個 newline，儲存到它的string引數。第75集29:00
就跟輸入運算子一樣，getline回傳其istream引數。
Note:導致getline回傳的newline會被丟棄，這個newline不會被儲存在string中。
11.3.6. A Word Transformation Map
11.3.6 一個字詞變換映射
第75集 6:55
頁441
The Word Transformation Program
transformation在此（中文語境）應譯為「取代字串」
hold可翻成「（交給它）保管」
13:50
void word_transform(ifstream &map_file, ifstream &input)
{
auto trans_map = buildMap(map_file); // store the transformations
string text; // hold each line from the input
while (getline(input, text))
{ // read a line of input
istringstream stream(text); // read each word
string word;
bool firstword = true; // controls whether a space is printed
while (stream ＞＞ word)
{
if (firstword)
firstword = false;
else
cout ＜＜ " "; // print a space between words
// transform returns its first argument or its transformation
cout ＜＜ transform(word, trans_map); // print the output
}
cout ＜＜ endl; // done with this line of input
}
}
頁442
18:50
Building the Transformation Map
建置變換映射
這裡map指的是map這個型別的容器，也不該翻出來
→用一個map 容器來配置取代用的資料
37:00
map＜string, string＞ buildMap(ifstream &map_file)
{
map＜string, string＞ trans_map; // holds the transformations
string key; // a word to transform
string value; // phrase to use instead
// read the first word into key and the rest of the line into value
while (map_file ＞＞ key && getline(map_file, value))
if (value.size() ＞ 1) // check that there is a transformation
trans_map[key] = value.substr(1); // skip leading space
else throw runtime_error("no rule for " + key);
return trans_map;
}
Note that we use the subscript operator to add the key–value pairs. Implicitly, we are ignoring what should happen if a word appears more than once in our transformation file. If a word does appear multiple times, our loops will put the last corresponding phrase into trans_map.
Implicitly,中文語境要翻成這樣→我們這麼做就是想要忽略……怎麼可以英文照，成了洋涇濱中文？
隱含地，我們忽略了一個字詞在我們的變換檔案中出現一次以上的情況。
要這樣翻，根本叫機器翻譯就好啦
Word VBA
插入點處理，顯示所在位置標題
OK 1:17:30 https://snipsave.com/oscarsun72/#/snippet/MYr5TxMRJoeWkps7bg
Generating a Transformation
1:18:59
頁443
const string & transform(const string &s, const map＜string, string＞ &m)
{
// the actual map work; this part is the heart of the program
auto map_it = m.find(s);
// if this word is in the transformation map
if (map_it != m.cend())
return map_it-＞second; // use the replacement word
else
return s; // otherwise return the original unchanged
}
1:42:54
we dereference the iterator, obtaining a pair that holds the key and value for that element (§ 11.3, p. 428).
We return the second member, which is the transformation to use in place of s.
獲取一個pair，其中放有該元素的鍵值與值（§11.3)。
holds這裡翻成「含有、包含了」才好
放有→放了、放著
練習11.33
參見練習11.38
1:49:14
Implement your own version of the word-transformation program.
實作你自己版本的字詞變換程式。
取代字串程式
#include＜iostream＞
#include＜fstream＞
#include＜iterator＞
#include＜map＞
using namespace std;
int main() {
map＜string, string＞mReplace;
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;
map＜string, string＞::const_iterator mIt;
string ocr;
while (input != e)
{
ocr = *input;
mIt = mReplace.find(ocr);
if (mIt != mReplace.cend())
cout ＜＜ mIt-＞second ＜＜ endl;
else
cout ＜＜ ocr ＜＜ endl;
++input;
}
}
2:37:55
練習11.34
如果用下標則會在找不到時，改變map大小，多加了一個元素進去
2:40:06
練習11.35
好像是一樣的吧。除非是說下標者，會改動已有key的value值，而插入insert()者不會（即若鍵值已存在，則不會再插入？）
練習11.36
2:51:00 最後一個元素便不是合法的元素值便不會被加入map
2:52:27
11.4. The Unordered Containers
11.4無序的容器
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）的方式將函式當作引數傳遞給建構子建構元素次第；故為有序容器
2:59:35
無序容器最有用的時機是，當我們有一種鍵值型別，其元素之間沒有明顯的順序關係。這些容器對於維護元素順序的成本令人望而卻步的應用來說，也很實用。
也就是在不需要、沒有必要，或者沒有、乃至無法排序元素的狀況下，都是使用無序容器的
雖然理論上或原則上，無序容器使用了hashing會在平均值上有整體效能上的提升，然而這種效能的取得往往必須付出一定的代價，比如說不斷測試與調整；也因此，反而有序容器在某些時候，反而凌駕其上
頁444
tip:如果鍵值型別本質上就是無序的，或者效能測試之下，顯示出有hashing可以解決的問題，就使用無序容器。
使用無序容器（unordered container）的時機與應有的考量
Using an Unordered Container
使用一個無序容器
除了提供對雜湊（hashing）的運算，無序容器也支援有序容器（循序容器）的運算
the operations we’ve used on map and set apply to unordered_map and unordered_set as well.
3:12:55
對於multi——允許重複鍵值的無序容器也是
也就是這樣，有序與無序容器常可交互運用的
// 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;
3:21:20
Managing the Buckets
管理貯體(Buckets)
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
3:35:55
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.
類似將貯體（bucket）也標上索引
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:42:44
Table 11.8. Unordered Container Management Operations
3:55:00
表11.8 :無序容器的管理運算
貯體介面（Bucket Interface)
c.bucket_count() 使用中的貯體數。
c.max_bucket_count() 這個容器能夠存放的最大貯體數。
c.bucket_size(n) 第n個貯體中的元素數。
c.bucket(k) 在其中可以找到具有鍵值k的元素的貯體。
貯體迭代（Bucket Iteration）
local_iterator 能夠存取一個貯體中元素的迭代器型別。
const_local_iterator 貯體迭代器的const版本。
c.begin(n) 、 c.end(n) 指向貯體n中第一個元素，以及超出最後一個元素一個位置處的迭代器。
c.cbegin(n) 、 c.cend(n) 回傳const_local_iterator。
雜湊策略
c.load_factor() 每個貯體的平均元素數。回傳float。
c.max_load_factor() c試著維持的平均貯體大小。c新增貯體來保持load_ factor ＜= max_load_factor。回傳float 。
c.rehash(n) 重新組織儲存區，讓bucket_count ＞= n而且bucket_ count ＞ size/max_load_factor。
c.reserve(n) 進行重組，讓c可以存放個元素，而不用進行rehash。
無序容器（unordered container）就有點像多維陣列（陣列的陣列），它是容器(即bucket)的容器
。因為無序容器沒有迭代器（iterator），但它內部的貯體（bucket）卻有！
Requirements on Key Type for Unordered Containers
無序容器的鍵值型別的要求條件
無序容器鍵值型別的必要條件、必備條件
鍵值型別，沒有生命，沒有靈識，怎麼會「要求」呢，就像說「自傳的目的」「遙控器的目的」一樣的荒唐與不合邏輯。
中文與語文、邏輯能力不好，就會如此
難怪無時無刻可以成了任何時刻
怎麼學程式語言的語言邏輯還這麼不敏銳呢？只有一個原因，漠視自己母語能力的結果，下場就是如此
預設情況下，無序容器是用鍵值型別的等號運算子來作其元素間的比對操作
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.
程式庫為內建型別（builtin type）包括指標（pointer）提供了多種hash模板（template）
程式庫也為一些程式庫型別（library type）定義了一些hash ，包括string型別和在第12章要談到的智慧指標型別（smart pointer types）
因此，我們可以直接定義鍵值是內建型別（包括指標型別）、string或智慧指標的無序容器。
4:21:00
但是我們自定義的類別型別（class type）就不能直接套用hash模板hash template（雜湊模板）來作為無序容器的鍵值型別了，而是要自己定義自己的hash模板（在頁709會再討論）
頁446
要使用Sales_data作為鍵值，我們得提供函式來取代==運算子，並計算一個hash code。我們會先從定義這些函式開始：
size_t hasher(const Sales_data &sd)
{
return hash＜string＞()(sd.isbn());//可見不能直接用，卻可間接用hash！()應是不具名函式，而其後為參數列（parameter list），其前為回傳型別
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() == rhs.isbn();
}
無序容器（unordered container）與其說是無序，倒不如說是先歸類、再排序的容器。
分類就是取得hash code（號碼牌）和歸入bucket的過程
有了上述的hash函式的定義及對==運算子的定義，我們就可以用Sales_data這個型別來定義一個無序容器的鍵值型別
using SD_multiset = unordered_multiset＜Sales_data,
decltype(hasher) *, decltype(eqOp) *＞;
// arguments are the bucket size and pointers to the hash function and equality operator
SD_multiset bookstore(42, hasher, eqOp);
hasher、eqOp函式名稱當引數傳遞時，預設就是轉作為函式指標（function pointer）型別來傳遞。
如果我們的類別有自己的==運算子，我們可以只覆寫hash function就行了 ：
//使用FooHash來產生hash code，Foo必須有一個==運算子
unordered_set＜Foo, decltype(FooHash) *＞ fooSet(10, FooHash);
4:55:30
練習11.37
無序容器與同版本的有序容器的優缺點
理論上無序容器效能較佳，但限制亦多。如前若要用自定型別作鍵值，必要定義自己的hash函式和等號運算子（或等於運算）
如果hash函式沒設計好或者貯體（bucket）配置不當，也會影響無序容器的效能
有序、無序，二者應是互補的關係
無序容器除了還有雜湊函數（hash function）等特定操作外，其他有序版本有的運算，它都支援，參下題改寫前例，都僅只換了型別便可知。優點是多此功能，缺點也是多此麻煩。
練習11.38
5:0:53
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;
}
}
5:20:40
頁447
Chapter Summary
關聯式容器和循序容器最大的不同就在於它們不是用位置來存取元素的，而是藉由鍵值
總共8種關聯式容器
所以有序容器不是天生有就序，它還是動用到一個比較用的函式才能對其內元素進行排序
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.
5:28:30 5:33:20
不論是有序還是無序的容器，有相同鍵值的元素的都會挨在一塊兒：
Elements with the same key are stored adjacent to one another in both the ordered and unordered containers.
Defined Terms
5:35:40
associative array
Array whose elements are indexed by key rather than positionally. We say that the array maps a key to its associated value.
hash
hash就是一個模板
hash Special library template that the unordered containers use to manage the position of their elements.
可見關聯式容器仍舊逃不掉元素「位置」的存取也！
hash function
把它想成「發號碼牌」就對了
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.
把某個指定型別的值，映射（map）到一個整數值
5:43:40
這種「Equal values must map to equal integers; unequal values should map to unequal integers where possible.」能力就是hash函式的好壞評準，所以決定不是亂雜湊的
map
5:49:00
關聯式容器與關聯式陣列的關係：
map Associative container type that defines an associative array.
map定義一個關聯式陣列的關聯式容器。
頁448
multimap
5:52:20
multimap does not support subscripting.
可見下標（subscript）運算是要在唯一值上操作的。
strict weak ordering
5:55:37
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
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（存放）就是讓元素歸類（先歸類，再排序）
6:9:10
下標運算子（[]運算子,subscript operator）
只對非常值（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.
留言