《C++ Primer》筆記 第11章 關聯容器

1. 型別map和multimap定義在頭檔案map中；set和multiset定義在頭檔案set中；無序容器則定義在頭檔案unordered_map和unordered_set中，

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

2. 關聯容器不支持順序容器的位置相關操作，例如push_front或push_back，原因是關聯容器中元素是根據關鍵字存盤的，這些操作對關聯容器沒有意義，關聯容器也不支持建構式或插入操作這些接受一個元素值和一個數量值的操作，

3. 關聯容器的迭代器都是雙向的，

4. 定義關聯容器，當初始化一個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. 傳遞給排序演算法的可呼叫物件必須滿足與關聯容器中關鍵字一樣的型別要求，

7. 可以向一個演算法提供我們自定義的比較操作，與之類似，也可以提供自己定義的操作來替代關鍵字上的<運算子，所提供的操作必須在關鍵字型別上定義一個嚴格弱序，可以將嚴格弱序看作“小于等于”，雖然實際定義的操作可能是一個復雜的函式，無論我們怎樣定義比較函式，它必須具備如下基本性質：

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

8. 在實際編程中，重要的是，如果一個型別定義了“行為正常”的<運算子，則它可以用作關鍵字型別，

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

   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保存兩個資料成員，當創建一個pair時，我們必須提供兩個型別名，pair的資料成員將具有對應的型別，兩個型別不要求一樣，

11. pair的默認建構式對資料成員進行值初始化，也可以為每個成員提供初始化器：

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

12. 與其他標準庫型別不同，pair的資料成員是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物件，包含一個關鍵字和一個關聯的值，由于我們不能改變一個元素的關鍵字，因此這些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. 當解參考一個關聯容器迭代器時，我們會得到一個型別為容器的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. 關聯容器的insert成員向容器中添加一個元素或一個元素范圍，由于map和set包含不重復的關鍵字，因此插入一個已存在的元素對容器沒有任何影響，

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

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函式，

22. set型別不支持下標，因為set中沒有與關鍵字相關聯的“值”，

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

24. 如果關鍵字并不在map中，會為它創建一個元素并插入到map中，關聯值將進行值初始化，

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); // 元素的數量
    auto iter = authors.find(search_item); // 此作者的第一本書
    // 用一個回圈查找此作者的所有著作
    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：此函式接受一個關鍵字，回傳一個迭代器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. 管理桶：無序容器在存盤上組織為一組桶，每個桶保存零個或多個元素，無序容器使用一個哈希函式將元素映射到桶，為了訪問一個元素，容器首先計算元素的哈希值，它指出應該搜索哪個桶，容器將具有一個特定哈希值的所有元素都保存在相同的桶中，如果容器允許重復關鍵字，所有具有相同關鍵字的元素也都會在同一個桶中，因此，無序容器的性能依賴于哈希函式的質量和桶的數量和大小，

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

35. 但是，我們不能直接定義關鍵字型別為自定義型別別的無序容器，我們需要提供函式來替代==運算子和哈希值計算函式，

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

36. 如果我們的類定義了==運算子，則可以只多載哈希函式，

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

37. 有序容器使用比較函式來比較關鍵字，從而將元素按順序存盤，默認情況下，比較操作是采用關鍵字型別的<運算子，無序容器使用關鍵字型別的==運算子和一個hash<key_type>型別的物件來組織元素，

標籤：C++

上一篇：C++面向物件：C++ 介面（抽象類）

下一篇：Qt update重繪之原始碼分析(一)