《C++ Primer》学习笔记（十一）：关联容器

偏执的太偏执、 2023-03-14 10:48 13阅读 0赞

### 《C++ Primer》学习笔记（十一）：关联容器 ###

*  使用关联容器
 *  定义关联容器
 *  关键字类型的要求
 *  pair类型
 *  关联容器迭代器
 *  添加元素
 *  删除元素
 *  map的下标操作
 *  访问元素
 *  无序容器
 *  练习

关联容器中的元素是按关键字来保存和访问的。

*  `map`中保存的是键值对(`key-value`)，关键字起索引所用，值则保存相应的数据。
 *  `set`中的每个元素只包含一个关键字，支持高效的关键字查询操作。

`map`和`multimap`定义在头文件`map`中，`set`和`multiset`定义在头文件`set`中。无序容器定义在`unordered_map`和`unordered_set`中，无序容器使用哈希函数来组织元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 1]

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

# 使用关联容器 #

**`map`的典型用法：**

// 统计每个单词在输入中出现的次数
    map<string, size_t> word_count;     // string到size_t的空map
    string word;
    while (cin >> word)
        ++word_count[word];     		// 提取word的计数器并将其加1
    for (const auto &w : word_count)    // 对map中的每个元素
        // 打印结果
        cout << w.first << " occurs " << w.second
            << ((w.second > 1) ? " times" : " time") << endl;

当从`map`中提取一个元素时，会得到一个`pair`类型的对象，该对象的`first`成员保存的是关键字，`second`成员保存的是对应的值。

**`set`的典型用法：**

// 统计输入中每个单词出现的次数
    map<string, size_t> word_count;
    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];

# 定义关联容器 #

map<string, size_t> word_count;   // 空容器
    // 列表初始化
    set<string> exclude = {
         "the", "but", "and" };
    // 三个元素; authors将姓映射为名
    map<string, string> authors =
    {
        
        {
        "Joyce", "James"},
        {
        "Austen", "Jane"},
        {
        "Dickens", "Charles"}
    };
    
    /* ************** */
    
    // 定义一个有20个元素的vector，保存0到9每个整数的两个拷贝
    vector<int> ivec;
    for (vector<int>::size_type i = 0; i != 10; ++i) {
        
    	ivec.push_back(i);
    	ivec.push_back(i); // 每个数重复保存一次
    }
    // iset包含来自ivec的不重复的元素; miset包含所有20个元素
    set<int> iset(ivec.cbegin(), ivec.cend());
    multiset<int> miset(ivec.cbegin(), ivec.cend());
    cout << ivec.size() << endl; 	// 打印出20
    cout << iset.size() << endl;	// 打印出10
    cout << miset.size() << endl;	// 打印出20

# 关键字类型的要求 #

对于有序容器——`map`、`multimap`、`set` 和 `multiset`，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的 `<`运算符来进行比较操作。

如果需要使用自定义的比较操作，则必须在定义关联容器类型时提供此操作的类型。操作类型在尖括号中紧跟着元素类型给出。

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
    {
        
        return lhs.isbn() < rhs.isbn();
    }
    
    // bookstore中多条记录可以有相同的ISBN
    // bookstore中的元素以ISBN的顺序进行排列
    multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

# pair类型 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 2]

pair<string, int> process(vector<string> &v)
    {
        
        // 处理v
        if (!v.empty())
            // 列表初始化
            return {
         v.back(), v.back().size() };
        else
            // 隐式构造返回值
            return pair<string, int>();
    }

# 关联容器迭代器 #

// 获得指向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;               // 正确·我们可以通过迭代器改变元素

**注意**：一个`map`的`value_type`是一个`pair`，我们可以改变`pair`的值，但是不能改变关键字成员的值。

虽然 `set` 同时定义了 `iterator` 和 `const_iterator` 类型，但两种迭代器都只允许**只读访问** `set` 中的元素。与不能改变一个`map`元素的关键字一样，一个`set`中的关键字也是`const`的。

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;    // 正确：可以读关键字
    }

使用迭代器遍历 `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; // 递均迭代器， 移动到下一个元素
    }

通常不对关联容器使用泛型算法。使用关联容器定义的`find`成员会比调用泛型`find`快得多。

# 添加元素 #

关联容器的 `insert`成员可以向关联容器中添加一个元素或一个元素范围。由于`map`和`set`（以及对应的无序类型）的关键字不重复，因此向 `map` 和 `set`（以及对应的无序类型）中添加已存在的元素对容器没有影响。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 3]

对一个`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));

# 删除元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 4]  
对于不包含重复关键字的容器，`erase` 的返回值总是`1`或`0`。若返回值为`0`，则表示想要删除的元素并不在容器中。

# map的下标操作 #

`map` 下标运算符接受一个关键字，获取与此关键字相关联的值。如果关键字不在容器中，下标运算符会向容器中添加该关键字，并值初始化关联值。由于下标运算符可能向容器中添加元素，所以只能对非 `const` 的 `map` 使用下标操作。不能对一个`multimap`或`unordered_multimap`进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 5]  
对 `map` 进行下标操作时，返回的是 `mapped_type` 类型的对象；解引用 `map`迭代器时，返回的是 `value_type` 类型的对象。

# 访问元素 #

![在这里插入图片描述][202005181132089.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 6]  
如果我们只是想知道一个给定的关键字是否在`map`中，而不想改变`map`。应该使用`find`而不是下标运算符，因为如果关键字不存在的话，下标运算符会插入一个新元素。

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

如果 `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;   // 记录已经打印了多少本书
    }

`lower_bound`和 `upper_bound` 操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，`lower_bound` 返回的迭代器会指向第一个匹配给定关键字的元素，而 `upper_bound` 返回的迭代器则指向最后一个匹配元素之后的位置。如果关键字不在 `multimap` 中，则`lower_bound` 和 `upper_bound` 会返回相等的迭代器，指向一个不影响排序的关键字插入位置。因此用相同的关键字调用 `lower_bound` 和 `upper_bound` 会得到一个迭代器范围，表示所有具有该关键字的元素范围。

`lower_bound`返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。如果关键字不在容器中，则 `lower_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;    // 打印每个题目

`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;  // 打印每个题目

# 无序容器 #

新标准库定义了4个 **无序关联容器**（unordered associative container），这些容器使用 **哈希函数**（hash function） 和关键字类型的 `==`运算符组织元素。

无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储，使用无序容器的程序输出一般会与有序容器的版本不同。

无序容器在存储上组织为一组桶，每个桶保存零或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此无序容器的性能依赖于哈希函数的质量和桶的数量及大小。

当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。但是如果一个桶中保存了很多元素，那么查找一个特定元素就会需要大量比较操作。

无序容器提供了一组管理桶的函数，这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 7]  
标准库为内置类型和一些标准库类型提供了`hash`模板。因此可以直接定义关键字是这些类型的无序容器，但**不能直接定义关键字类型为自定义类类型的无序容器，必须先提供对应的`hash`模板版本。**

size_t hasher(const Sales_data &sd)
    {
        
    	return hash<string>() (sd.isbn());
    }
    
    bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
    {
        
    	return lhs.isbn() == rhs.isbn();
    }
    
    using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
    
    //参数是桶大小，哈希函数指针和相等性判断运算符指针
    SD_multiset boolstore(42, hasher, eqOp);

如果自定义类已经定义了`==`运算符，则可以只重载哈希函数：

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

# 练习 #

1.  **可以定义一个 `vector<int>::iterator` 到 `int` 的 `map` 吗？`list<int>::iterator` 到 `int` 的`map` 呢？对于两种情况，如果不能，解释为什么。**

由于有序容器要求关键字类型必须支持比较操作 `<`，

*  因此 `map<vector<int>::iterator, int>m1`; 是可以的，因为 `vector`的迭代器支持比较操作。
 *  而 `map<list<int>::iterator, int>m2`; 是不行的，因为 `list` 的元素不是连续存储，其迭代器不支持比较操作。

1.  **编写程序，读入 `string` 和 `int` 的序列，将每个 `string` 和 `int`存入一个 `pair` 中，`pair`保存在一个 `vector` 中。**

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <utility>
    #include <vector>
    #include <fstream>          // file I/O support
    #include <cstdlib>          // support for exit()
    using namespace std;
    int main()
    {
        
    	char filename[20];
    	cout << "Enter name of data file: ";
    	cin.getline(filename, 20);
    	ifstream inFile;        // object for handling file input
    	inFile.open(filename);  // associate inFile with a file
    	if (!inFile.is_open())  // failed to open file
    	{
        
    		cout << "Could not open the file " << filename << endl;
    		cout << "Program terminating.\n";
    		exit(EXIT_FAILURE);
    	}
    	
    	vector<pair<string, int>> record;
    	string s;
    	int v;
    	while (inFile >> s && inFile >> v)
    	{
        
    		record.push_back(pair<string, int>(s, v));
    	}
    	for (const auto &d : record){
        
    		cout << d.first << " " << d.second << endl;
    	}
    	inFile.close();         // finished with the file
    
    	system("pause");
    	return 0;
    }

1.  **假定 `c` 是一个 `string` 的 `multiset`，`v` 是一个 `string` 的 `vector`，解释下面的调用。指出每个调用是否合法：**

copy(v.begin(), v.end(), inserter(c, c.end()));
    copy(v.begin(), v.end(), back_inserter(c));
    copy(c.begin(), c.end(), inserter(v, v.end()));
    copy(c.begin(), c.end(), back_inserter(v));

`back_inserter()`需要使用`push_back()`，而`set`不能够使用`push_back()`,因此`copy(v.begin(), v.end(), back_inserter(c));`不合法。另外三条语句均合法。

#include<iostream>  
    #include<vector>  
    #include<iterator>
    #include <set>
    #include <string>
    
    using namespace std;
    
     
    int main(int argc, char**argv)  
    {
          
    	string sarray[2] = {
        "eee", "fff"};
    
    	multiset<string> c(sarray, sarray+2);
    	vector<string> v{
        "abc", "def"};
    
    	copy(v.begin(), v.end(), inserter(c, c.end()));
    
    	for(auto iter = c.begin(); iter!=c.end(); ++iter){
        
    		cout << *iter << endl;
    	}
    
    	cout << "-------------------------"<<endl;
    
    	for(auto iter = v.begin(); iter!=v.end(); ++iter){
        
    		cout << *iter << endl;
    	}
    
    
    
    	cout << endl;
    
    	system("pause");
    	return 0;  
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 8]

1.  **给定一个 `map<string, vector<int>>`，对此容器的插入一个元素的 `insert`版本，写出其参数类型和返回类型。**

参数类型为：`pair<string, vector<int>>`  
返回类型为： `pair<map<string, vector<int>>::iterator, bool>`

1.  **在 `buildMap` 中，如果进行如下改写，会有什么效果？**

trans_map[key] = value.substr(1);
    //改为
    trans_map.insert({
        key, value.substr(1)});

当 `map`中没有给定关键字时，`insert`操作与 下标操作+赋值 操作的效果类似，都是将关键字和值的 `pair`添加到 `map` 中。

但当 `map`中已有给定关键字，也就是新的转换规则与一条已有规则要转换同一个单词时，两者的行为是不同的。

下标操作会获得具有该关键字的元素（也就是已有规则）的值，并将新读入的值赋予它，也就是用新读入的规则覆盖了容器中的已有规则。  
但 `insert` 操作遇到关键字已存在的情况，则不会改变容器内容，而是返回一个值指出插入失败。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70]: /images/20230312/0b4e43a0a3d3401b903e66d4f24b0161.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 1]: /images/20230312/cfa8aaaa5e864d6f917ba6703da5deb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 2]: /images/20230312/91bb9419508947718c82ac575504f0d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 3]: /images/20230312/516fa52aa6dd4214adc220b9beb1f2a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 4]: /images/20230312/d56186ccf7f64cb59d602743daf23f9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 5]: /images/20230312/6fe3aad6b9fb47cda0316417b81e7e40.png
[202005181132089.png]: /images/20230312/4ab4fafc0738438483902799402967aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 6]: /images/20230312/d3a2f19f106244feb4e64e9790b29dbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 7]: /images/20230312/43ecc118ee1e42fb83a6c273022c6f64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 8]: /images/20230312/82c2851c3b4f4f53b5385941bf7bd228.png