1. 類型map和multimap定義在頭文件map中；set和multiset定義在頭文件set中；無(wú)序容器則定義在頭文件unordered_map和unordered_set中。

   // 統(tǒng)計(jì)輸入中每個(gè)單詞出現(xiàn)的次數(shù)
   map<string, size_t> word_count; // string到size_t的空map
   set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
   string word;
   while(cin >> word)
   // 只統(tǒng)計(jì)不在exclude中的單詞
   if (exclude.find(word) == exclude.end())
   ++word_count[word]; // 獲取并遞增word的計(jì)數(shù)器
   

2. 關(guān)聯(lián)容器不支持順序容器的位置相關(guān)操作，例如push_front或push_back。原因是關(guān)聯(lián)容器中元素是根據(jù)關(guān)鍵字存儲(chǔ)的，這些操作對(duì)關(guān)聯(lián)容器沒有意義。關(guān)聯(lián)容器也不支持構(gòu)造函數(shù)或插入操作這些接受一個(gè)元素值和一個(gè)數(shù)量值的操作。

3. 關(guān)聯(lián)容器的迭代器都是雙向的。

4. 定義關(guān)聯(lián)容器。當(dāng)初始化一個(gè)map時(shí)，必須提供關(guān)鍵字類型和值類型。我們將每個(gè)關(guān)鍵字-值對(duì)包圍在花括號(hào)中：{key, value}來(lái)指出它們一起構(gòu)成了map中的一個(gè)元素。在每個(gè)花括號(hào)中，關(guān)鍵字是第一個(gè)元素，值是第二個(gè)。

   map<string, size_t> word_count; // 空容器
   // 列表初始化
   set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
   // 三個(gè)元素；authors將姓映射為名
   map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"} };
   // 定義一個(gè)有20個(gè)元素的vector
   vector<int> ivec = {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9};
   // iset包含來(lái)自ivec的不重復(fù)的10個(gè)元素；miset包含所有20個(gè)元素
   set<int> iset(ivec.cbegin(), ivec.cend());
   multiset<int> miset(ivec.cbegin(), ivec.cend());
   

5. 對(duì)有序容器——map、multimap、set以及multiset，關(guān)鍵字類型必須定義元素比較的方法。默認(rèn)情況下，標(biāo)準(zhǔn)庫(kù)使用關(guān)鍵字類型的<運(yùn)算符來(lái)比較兩個(gè)關(guān)鍵字。在集合類型中，關(guān)鍵字類型就是元素類型；在映射類型中，關(guān)鍵字類型是元素的第一部分的類型。

6. 傳遞給排序算法的可調(diào)用對(duì)象必須滿足與關(guān)聯(lián)容器中關(guān)鍵字一樣的類型要求。

7. 可以向一個(gè)算法提供我們自定義的比較操作，與之類似，也可以提供自己定義的操作來(lái)替代關(guān)鍵字上的<運(yùn)算符。所提供的操作必須在關(guān)鍵字類型上定義一個(gè)嚴(yán)格弱序。可以將嚴(yán)格弱序看作“小于等于”，雖然實(shí)際定義的操作可能是一個(gè)復(fù)雜的函數(shù)。無(wú)論我們?cè)鯓佣x比較函數(shù)，它必須具備如下基本性質(zhì)：

   • 兩個(gè)關(guān)鍵字不能同時(shí)“小于等于”對(duì)方；如果k1“小于等于”k2，那么k2絕對(duì)不能“小于等于”k1。
   • 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必須“小于等于”k3。
   • 如果存在兩個(gè)關(guān)鍵字，任何一個(gè)都不“小于等于”另一個(gè)，那么我們稱這兩個(gè)關(guān)鍵字是“等價(jià)”的。如果k1“等價(jià)于”k2，且k2“等價(jià)于”k3，那么k1必須“等價(jià)于”k3。

8. 在實(shí)際編程中，重要的是，如果一個(gè)類型定義了“行為正常”的<運(yùn)算符，則它可以用作關(guān)鍵字類型。

9. 用來(lái)組織一個(gè)容器中元素的操作的類型也是該容器類型的一部分。為了指定使用自定義的操作，必須在定義關(guān)聯(lián)容器類型時(shí)提供此操作的類型。

   bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
   {
   return lhs.isbn() < rhs.isbn();
   }
   
   // bookstore中多條記錄可以相同的ISBN
   // 用compareIsbn來(lái)初始化bookstore對(duì)象，這表示我們向bookstore添加元素時(shí)，通過調(diào)用compareIsbn來(lái)為這些元素排序
   // 即，bookstore中的元素以ISBN的順序進(jìn)行排列
   multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
   

10. pair的標(biāo)準(zhǔn)庫(kù)類型，定義在頭文件utility中。一個(gè)pair保存兩個(gè)數(shù)據(jù)成員。當(dāng)創(chuàng)建一個(gè)pair時(shí)，我們必須提供兩個(gè)類型名，pair的數(shù)據(jù)成員將具有對(duì)應(yīng)的類型。兩個(gè)類型不要求一樣。

11. pair的默認(rèn)構(gòu)造函數(shù)對(duì)數(shù)據(jù)成員進(jìn)行值初始化。也可以為每個(gè)成員提供初始化器：

    pair<string, string> anon; // anon是一個(gè)包含兩個(gè)空string的pair
    pair<string, string> author{"James", "Joyce"};
    

12. 與其他標(biāo)準(zhǔn)庫(kù)類型不同，pair的數(shù)據(jù)成員是public的，兩個(gè)成員分別命名為first和second。我們用普通的成員訪問符號(hào)來(lái)訪問他們。

13. map的元素是pair。

pair<string, int> process(vector<string> &v)
{
// 處理v
if (!v.empty())
return {v.back(), v.back().size()}; // 列表初始化，下述等價(jià)
    // return pair<string, int>(v.back(), v.back().size());
    // return make_pair(v.back(), v.back().size());
else
return pair<string, int>(); // 隱式構(gòu)造返回值
}

14. 對(duì)于set類型，key_type和value_type是一樣的；set中保存的值就是關(guān)鍵字。在一個(gè)map中，元素是關(guān)鍵字-值對(duì)。即，每個(gè)元素是一個(gè)pair對(duì)象，包含一個(gè)關(guān)鍵字和一個(gè)關(guān)聯(lián)的值。由于我們不能改變一個(gè)元素的關(guān)鍵字，因此這些pair的關(guān)鍵字部分是const的。

    set<string>::value_type v1; // v1是一個(gè)string
    set<string>::key_type v2; // v2是一個(gè)string
    map<string, int>::value_type v3; // v3是一個(gè)pair<const string, int>
    map<string, int>::key_type v4; // v4是一個(gè)string
    map<string, int>::mapped_type v5; // v5是一個(gè)int
    

15. 當(dāng)解引用一個(gè)關(guān)聯(lián)容器迭代器時(shí)，我們會(huì)得到一個(gè)類型為容器的value_type的值的引用。對(duì)map而言，value_type是一個(gè)pair類型，其first成員保存const的關(guān)鍵字，second成員保存值。

    // 獲得指向word_count中一個(gè)元素的迭代器
    auto map_it = word_count.begin();
    // *map_it是指向一個(gè)pair<const string, size_t>對(duì)象的引用
    cout << map_it->first; //打印此元素的關(guān)鍵字
    cout << " " << map_it->second; // 打印此元素的值
    map_it->first = "new key"; // 錯(cuò)誤：關(guān)鍵字是const的
    ++map_it->second; // 正確：我們可以通過迭代器改變?cè)?

16. 雖然set類型同時(shí)定義了iterator和const_iterator類型，但兩種類型都只允許只讀訪問set中的元素。與不能改變一個(gè)map元素的關(guān)鍵字一樣，一個(gè)set中的關(guān)鍵字也是const的?？梢杂靡粋€(gè)set迭代器來(lái)讀取元素的值，但不能修改：

    set<int> iset = {0,1,2,3,4,5,6,7,8,9};
    set<int>::iterator set_it = iset.begin();
    if (set_it != iset.end())
    {
    *set_it = 42; // 錯(cuò)誤：set中的關(guān)鍵字是只讀的
    cout << *set_it << endl; // 正確：可以讀關(guān)鍵字
    }
    

17. 當(dāng)使用一個(gè)迭代器遍歷一個(gè)map、multimap、set或multiset時(shí)，迭代器按關(guān)鍵字升序遍歷元素。

    // 獲得一個(gè)指向首元素的迭代器
    auto map_it = word_count.cbegin();
    // 比較當(dāng)前迭代器和尾后迭代器
    while (map_it != word_count.cend())
    {
    // 解引用迭代器，打印關(guān)鍵字-值對(duì)
    cout << map_it->first << " occurs " << map_it->second << " times" << endl;
    ++map_it; // 遞增迭代器，移動(dòng)到下一個(gè)元素
    }
    

18. 關(guān)聯(lián)容器的insert成員向容器中添加一個(gè)元素或一個(gè)元素范圍。由于map和set包含不重復(fù)的關(guān)鍵字，因此插入一個(gè)已存在的元素對(duì)容器沒有任何影響。

19. insert有兩個(gè)版本，分別接受一對(duì)迭代器，或是一個(gè)初始化器列表，這兩個(gè)版本的行為類似對(duì)應(yīng)的構(gòu)造函數(shù)（對(duì)于一個(gè)給定的關(guān)鍵字，只有第一個(gè)帶此關(guān)鍵字的元素才被插入到容器中）。

20. 對(duì)一個(gè)map進(jìn)行insert操作時(shí)，必須記住元素類型是pair：

    // 向word_count插入word的4種方法
    word_count.insert({word, 1});
    word_count.insert(make_pair(word, 1));
    word_count.insert(pair<string, size_t>(word, 1));
    word_count.insert(map<string, size_t>::value_type(word, 1));
    

21. map和unordered_map容器提供了下標(biāo)運(yùn)算符和一個(gè)對(duì)應(yīng)的at函數(shù)。

22. set類型不支持下標(biāo)，因?yàn)閟et中沒有與關(guān)鍵字相關(guān)聯(lián)的“值”。

23. 我們不能對(duì)一個(gè)multimap或一個(gè)unordered_multimap進(jìn)行下標(biāo)操作，因?yàn)檫@些容器中可能有多個(gè)值與一個(gè)關(guān)鍵字相關(guān)聯(lián)。

24. 如果關(guān)鍵字并不在map中，會(huì)為它創(chuàng)建一個(gè)元素并插入到map中，關(guān)聯(lián)值將進(jìn)行值初始化。

25. 由于下標(biāo)運(yùn)算符可能插入一個(gè)新元素，我們只可以對(duì)非const的map使用下標(biāo)操作。

26. 通常情況下，解引用一個(gè)迭代器所返回的類型與下標(biāo)運(yùn)算符返回的類型是一樣的。但對(duì)map則不然：當(dāng)對(duì)一個(gè)map進(jìn)行下標(biāo)操作時(shí)，會(huì)獲得一個(gè)mapped_type對(duì)象；但當(dāng)解引用一個(gè)map迭代器時(shí)，會(huì)得到一個(gè)value_type對(duì)象。

27. 與其他下標(biāo)運(yùn)算符相同的是，map的下標(biāo)運(yùn)算符返回一個(gè)左值。

28. 另一方面，有時(shí)只是想知道一個(gè)元素是否已在map中，但在不存在時(shí)并不想添加元素。在這種情況下，就不能使用下標(biāo)運(yùn)算符，應(yīng)該使用find：

    if (word_count.find("foobar") == word_count.end())
    cout << "foobar is not in the map" << endl;
    

29. 在multimap或multiset中查找元素：

    string search_item("Alain de Botton"); // 要查找的作者
    auto entries = authors.count(search_item); // 元素的數(shù)量
    auto iter = authors.find(search_item); // 此作者的第一本書
    // 用一個(gè)循環(huán)查找此作者的所有著作
    while (entries)
    {
    cout << iter->second << endl; // 打印每個(gè)題目
    ++iter; // 前進(jìn)到下一本書
    --entries; // 記錄已經(jīng)打印了多少本書
    }
    // 當(dāng)我們遍歷一個(gè)multimap或multiset時(shí)，保證可以得到序列中所有具有給定關(guān)鍵字的元素
    

30. 用相同的關(guān)鍵字調(diào)用lower_bound和upper_bound會(huì)得到一個(gè)迭代器范圍，表示所有具有該關(guān)鍵字的元素的范圍。如果關(guān)鍵字在容器中，lower_bound返回的迭代器將指向第一個(gè)具有給定關(guān)鍵字的元素，而upper_bound返回的迭代器則指向最后一個(gè)匹配給定關(guān)鍵字的元素之后的位置。如果元素不在multimap或multiset中，則lower_bound和upper_bound會(huì)返回相等的迭代器——指向一個(gè)不影響排序的關(guān)鍵字插入位置。

    // authors和search_item的定義，與前面的程序一樣
    // beg和end表示對(duì)應(yīng)此作者的元素的范圍
    for (auto beg = authors.lower_bound(search_item), 
         end = authors.upper_bound(search_item); 
         beg != end; 
         ++beg)
    cout << beg->second << endl; // 打印每個(gè)題目
    // lower_bound返回的迭代器可能指向一個(gè)具有給定關(guān)鍵字的元素，但也可能不指向。
    // 如果關(guān)鍵字不在容器中，則lower_bound會(huì)返回關(guān)鍵字的第一個(gè)安全插入點(diǎn)——不影響容器中元素順序的插入位置。
    

31. 直接調(diào)用equal_range：此函數(shù)接受一個(gè)關(guān)鍵字，返回一個(gè)迭代器pair。若關(guān)鍵字存在，則第一個(gè)迭代器指向第一個(gè)與關(guān)鍵字匹配的元素，第二個(gè)迭代器指向最后一個(gè)匹配元素之后的位置。若未找到匹配元素，則兩個(gè)迭代器都指向關(guān)鍵字可以插入的位置。

    // authors和search_item的定義，與前面的程序一樣
    // pos保存迭代器對(duì)，表示與關(guān)鍵字匹配的元素范圍
    for (auto pos = authors.equal_range(search_item); 
         pos.first != pos.second; 
         ++pos.first)
    cout << pos.first->second << endl; // 打印每個(gè)題目
    // 此程序本質(zhì)上與前一個(gè)使用upper_bound和lower_bound的程序是一樣的。
    

32. 綜合應(yīng)用（一個(gè)單詞轉(zhuǎn)換的map）：

#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include <sstream>

using std::cout;
using std::endl;
using std::getline;
using std::ifstream;
using std::istringstream;
using std::map;
using std::runtime_error;
using std::string;
using std::vector;

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;
}

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
    }
}

// first argument is the transformations file;
// second is file to transform
void word_transform(ifstream &map_file, ifstream &input)
{
    auto trans_map = buildMap(map_file); // store the transformations

    // for debugging purposes print the map after its built
    cout << "Here is our transformation map: \n\n";
    for (auto entry : trans_map)
    {
        cout << "key: " << entry.first << "\tvalue: " << entry.second << endl;
    }
    cout << "\n\n";

    // do the transformation of the given text
    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
    }
}

int main(int argc, char **argv)
{
    // open and check both files
    if (argc != 3)
    {
        throw runtime_error("wrong number of arguments");
    }

    ifstream map_file(argv[1]); // open transformation file
    if (!map_file)              // check that open succeeded
    {
        throw runtime_error("no transformation file");
    }

    ifstream input(argv[2]); // open file of text to transform
    if (!input)              // check that open succeeded
    {
        throw runtime_error("no input file");
    }

    word_transform(map_file, input);

    return 0; // exiting main will automatically close the files
}

33. 管理桶：無(wú)序容器在存儲(chǔ)上組織為一組桶，每個(gè)桶保存零個(gè)或多個(gè)元素。無(wú)序容器使用一個(gè)哈希函數(shù)將元素映射到桶。為了訪問一個(gè)元素，容器首先計(jì)算元素的哈希值，它指出應(yīng)該搜索哪個(gè)桶。容器將具有一個(gè)特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復(fù)關(guān)鍵字，所有具有相同關(guān)鍵字的元素也都會(huì)在同一個(gè)桶中。因此，無(wú)序容器的性能依賴于哈希函數(shù)的質(zhì)量和桶的數(shù)量和大小。

34. 默認(rèn)情況下，無(wú)序容器使用關(guān)鍵字類型的==運(yùn)算符來(lái)比較元素，它們還使用一個(gè)hash<key_type>類型的對(duì)象來(lái)生成每個(gè)元素的哈希值。標(biāo)準(zhǔn)庫(kù)為內(nèi)置類型（包括指針）提供了hash模板。還為一些標(biāo)準(zhǔn)庫(kù)類型，包括string和智能指針類型定義了hash。因此，我們可以直接定義關(guān)鍵字是內(nèi)置類型（包括指針類型）、string還是智能指針類型的無(wú)序容器。

35. 但是，我們不能直接定義關(guān)鍵字類型為自定義類類型的無(wú)序容器。我們需要提供函數(shù)來(lái)替代==運(yùn)算符和哈希值計(jì)算函數(shù)。

    size_t hasher(const Sales_data &sd)
    {
        // 我們的hasher函數(shù)使用一個(gè)標(biāo)準(zhǔn)庫(kù)hash類型對(duì)象來(lái)計(jì)算ISBN成員的哈希值
        // 該hash類型建立在string類型之上
    return hash<string>()(sd.isbn());
    }
    bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
    {
        // eqOp函數(shù)通過比較ISBN號(hào)來(lái)比較兩個(gè)Sales_data
    return lhs.isbn() == rhs.isbn();
    }
    
    using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
    // 參數(shù)是桶大小、哈希函數(shù)指針和相等性判斷運(yùn)算符指針
    SD_multiset bookstore(42, hasher, eqOp);
    

36. 如果我們的類定義了==運(yùn)算符，則可以只重載哈希函數(shù)。

    // 使用FooHash生成哈希值；Foo必須有==運(yùn)算符
    unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);
    

37. 有序容器使用比較函數(shù)來(lái)比較關(guān)鍵字，從而將元素按順序存儲(chǔ)。默認(rèn)情況下，比較操作是采用關(guān)鍵字類型的<運(yùn)算符。無(wú)序容器使用關(guān)鍵字類型的==運(yùn)算符和一個(gè)hash<key_type>類型的對(duì)象來(lái)組織元素。