第十一章 关联容器

• 关联容器基于关键字访问元素，顺序容器基于位置访问元素
• 关联容器类型

11.2 关联容器概述

• 关联容器的初始化可以使用直接初始化（圆括号初始化）、列表初始化、拷贝初始化、迭代器范围初始化（会对关键字自动去重）
• map类型通常被称为关联数组
• 对于有序容器，关键字类型必须定义元素比较的方法（即<），严格弱序
• pair类型
  • 定义在utility头文件
  • map中的每个元素都是一个pair类型的对象，pair是一个模板类型，保存两个名为first和second的共有数据成员，first保存关键字，second保存值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 定义一个重载键类型的类，重载()操作符
class MyCmp{
public:
  bool operator() (const string &a, const string &b) {return a.size() < b.size();}    
};
map<string, int, MyCmp> mp{{"a", 1}, {"ab", 2}, {"b", 3}};

bool cmp(const string &a, const string &b) {return a.size() < b.size();}
map<string, int, bool(*)(const string&, const string&)> mp2({{"a", 1}, {"b", 2}}, cmp); // 模板中传入函数类型，构造函数中传入函数指针

using CMP = bool(*)(const string&, const string&); 
map<string, int, CMP> mp3({{"a", 1}, {"b", 2}}, cmp); // 或者模板中传入函数类型的别名，构造函数中同样传入函数指针
map<string, int, decltype(cmp)*> mp4({{"a", 1}, {"b", 2}}, cmp); // 使用decltype获取函数指针

// 遍历
for(map<string, int, CMP>::iterator iter = mp3.begin(); iter != mp3.end(); ++iter) // 或者使用map<string, int>::iterator iter也可以
cout << iter->first >> " " >> iter->second >>endl;

11.3 关联容器操作

• 关联容器额外的类型别名：

• 解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。
  • map而言，value_type是pair类型（pair<const key_type, mapped_type>）
  • set而言，value_type是const key_type，普通迭代器和const迭代器都是只读的，不能修改值

添加元素：insert

• 向map添加元素（在参数列表中构建pair），例子：

  1 2 3 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));

• 相对于下标操作，多使用insert（因为有返回值）
  • 例子：wordcount

    1 2 3 4

    map<string, size_t> word_count; string word; while(cin >> word) ++word_count.insert({word, 0}).first->second;

删除元素：erase

• 注意遍历容器删除元素时，map与vector不同

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

map<int, int> m; 
for(auto iter = m.begin(); iter != m.end(); ){ 
    if(iter->second == 0) 
        m.erase(iter++);
    else 
        iter++; 
    } 

vector<int> v; 
for(auto iter = v.begin(); iter != v.end(); ){ 
    if(*iter == 0) 
        iter = v.erase(iter);
    else 
        iter++; 
}

下标操作

• 下标和at操作只适用于非const的map和unordered_map，即使访问操作也不行
• map的下标操作只能返回非常量引用，如果map本身是常量，则无法使用下标访问元素，只能使用at函数

查找元素

在一个关联容器中查找元素:

• lower_bound和upper_bound不适用于无序容器。
• 如果multimap或multiset中有多个元素有相同关键字，则这些元素在容器中会相邻存储

11.4 无序容器

• 有序容器使用比较运算符来组织元素；无序容器使用哈希函数和关键字类型的==运算符。
• 无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。无序容器首先计算元素的哈希值，找到应该搜索哪个桶（相同哈希值的元素保存到相同的桶中），再搜索桶。 无序容器管理操作：