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

   // 統(tǒng)計輸入中每個單詞出現(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)計不在exclude中的單詞
   if (exclude.find(word) == exclude.end())
   ++word_count[word]; // 獲取并遞增word的計數(shù)器
   

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

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

4. 定義關聯(lián)容器。當初始化一個map時，必須提供關鍵字類型和值類型。我們將每個關鍵字-值對包圍在花括號中：{key, value}來指出它們一起構成了map中的一個元素。在每個花括號中，關鍵字是第一個元素，值是第二個。

   map<string, size_t> word_count; // 空容器
   // 列表初始化
   set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
   // 三個元素；authors將姓映射為名
   map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"} };
   // 定義一個有20個元素的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包含來自ivec的不重復的10個元素；miset包含所有20個元素
   set<int> iset(ivec.cbegin(), ivec.cend());
   multiset<int> miset(ivec.cbegin(), ivec.cend());
   

5. 對有序容器——map、multimap、set以及multiset，關鍵字類型必須定義元素比較的方法。默認情況下，標準庫使用關鍵字類型的<運算符來比較兩個關鍵字。在集合類型中，關鍵字類型就是元素類型；在映射類型中，關鍵字類型是元素的第一部分的類型。

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

7. 可以向一個算法提供我們自定義的比較操作，與之類似，也可以提供自己定義的操作來替代關鍵字上的<運算符。所提供的操作必須在關鍵字類型上定義一個嚴格弱序?？梢詫栏袢跣蚩醋鳌靶∮诘扔凇?，雖然實際定義的操作可能是一個復雜的函數(shù)。無論我們怎樣定義比較函數(shù)，它必須具備如下基本性質：

   • 兩個關鍵字不能同時“小于等于”對方；如果k1“小于等于”k2，那么k2絕對不能“小于等于”k1。
   • 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必須“小于等于”k3。
   • 如果存在兩個關鍵字，任何一個都不“小于等于”另一個，那么我們稱這兩個關鍵字是“等價”的。如果k1“等價于”k2，且k2“等價于”k3，那么k1必須“等價于”k3。

8. 在實際編程中，重要的是，如果一個類型定義了“行為正?！钡?lt;運算符，則它可以用作關鍵字類型。

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

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

10. pair的標準庫類型，定義在頭文件utility中。一個pair保存兩個數(shù)據(jù)成員。當創(chuàng)建一個pair時，我們必須提供兩個類型名，pair的數(shù)據(jù)成員將具有對應的類型。兩個類型不要求一樣。

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

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

12. 與其他標準庫類型不同，pair的數(shù)據(jù)成員是public的，兩個成員分別命名為first和second。我們用普通的成員訪問符號來訪問他們。

13. map的元素是pair。

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

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

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

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

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

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

    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; // 錯誤：set中的關鍵字是只讀的
    cout << *set_it << endl; // 正確：可以讀關鍵字
    }
    

17. 當使用一個迭代器遍歷一個map、multimap、set或multiset時，迭代器按關鍵字升序遍歷元素。

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

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

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

20. 對一個map進行insert操作時，必須記住元素類型是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容器提供了下標運算符和一個對應的at函數(shù)。

22. set類型不支持下標，因為set中沒有與關鍵字相關聯(lián)的“值”。

23. 我們不能對一個multimap或一個unordered_multimap進行下標操作，因為這些容器中可能有多個值與一個關鍵字相關聯(lián)。

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

25. 由于下標運算符可能插入一個新元素，我們只可以對非const的map使用下標操作。

26. 通常情況下，解引用一個迭代器所返回的類型與下標運算符返回的類型是一樣的。但對map則不然：當對一個map進行下標操作時，會獲得一個mapped_type對象；但當解引用一個map迭代器時，會得到一個value_type對象。

27. 與其他下標運算符相同的是，map的下標運算符返回一個左值。

28. 另一方面，有時只是想知道一個元素是否已在map中，但在不存在時并不想添加元素。在這種情況下，就不能使用下標運算符，應該使用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); // 此作者的第一本書
    // 用一個循環(huán)查找此作者的所有著作
    while (entries)
    {
    cout << iter->second << endl; // 打印每個題目
    ++iter; // 前進到下一本書
    --entries; // 記錄已經打印了多少本書
    }
    // 當我們遍歷一個multimap或multiset時，保證可以得到序列中所有具有給定關鍵字的元素
    

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

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

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

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

32. 綜合應用（一個單詞轉換的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. 管理桶：無序容器在存儲上組織為一組桶，每個桶保存零個或多個元素。無序容器使用一個哈希函數(shù)將元素映射到桶。為了訪問一個元素，容器首先計算元素的哈希值，它指出應該搜索哪個桶。容器將具有一個特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復關鍵字，所有具有相同關鍵字的元素也都會在同一個桶中。因此，無序容器的性能依賴于哈希函數(shù)的質量和桶的數(shù)量和大小。

34. 默認情況下，無序容器使用關鍵字類型的==運算符來比較元素，它們還使用一個hash<key_type>類型的對象來生成每個元素的哈希值。標準庫為內置類型（包括指針）提供了hash模板。還為一些標準庫類型，包括string和智能指針類型定義了hash。因此，我們可以直接定義關鍵字是內置類型（包括指針類型）、string還是智能指針類型的無序容器。

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

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

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

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

37. 有序容器使用比較函數(shù)來比較關鍵字，從而將元素按順序存儲。默認情況下，比較操作是采用關鍵字類型的<運算符。無序容器使用關鍵字類型的==運算符和一個hash<key_type>類型的對象來組織元素。