associative container

顺序容器支持元素的顺序访问. 连续存储的顺序容器支持随机访问

关联容器和顺序容器有着根本的不同: 通过关键字添加/访问元素

关联容器支持高效的关键字查找和访问

关联容器也是模板类型

关联容器有3个维度:

1. 基于set或map
   
   • set: 由关键字组成的集合, 关键字即值
     
   • map: 由键值对组成的集合, 键值对形如<关键字, 值>
     
2. 是否允许关键字重复
   
   如果允许关键字重复, 使用multi标识
   
   • multiset: 允许关键字/值多次出现
     
   • multimap: 允许多个关键字对应同一个值
     
3. 是否有序
   
   如果使用哈希函数组织元素, 使用unordered_前缀
   
   • unordered_set
     
   • unordered_map
     
   • unordered_multiset
     
   • unordered_multimap
     

一共有8种关联容器

关联容器	元素: 关键字	元素: 键值对	允许关键字重复	元素按关键字有序排序	使用哈希函数组织元素
set	O	-	X	O	-
map	-	O	X	O	-
multiset	O	-	O	O	-
multimap	-	O	O	O	-
unordered_set	O	-	X	-	O
unordered_map	-	O	X	-	O
unordered_multiset	O	-	O	-	O
unordered_multimap	-	O	O	-	O

set, multiset, map, multimap按关键字顺序排列元素: 要求关键字类型重载了小于运算符 < , 或者提供了元素的比较方法

有序关联容器和无序关联容器都要求关键字类型支持小于运算符和相等运算符, 或者提供用来代替的可调用对象

无序容器还要求关键字类型被哈希模板所支持, 或者提供来代替的可调用对象

map

也称作关联数组 associative array

存在映射: 关键字到值

可以像使用内置数组一样使用map; 使用关键字作为下标, 而不是索引

一个简单的使用场景: 为每个联系人记录一个电话号码. 使用联系人姓名作为关键字, 查询map可获得电话号码

键值对

map的元素类型, 也是模板类型

set

由关键字组成的简单集合

可以查询某个关键字是否存在于集合中

简单的使用场景:

1. 将开过空头支票的人的姓名加入黑名单. 每次接受支票之前, 在黑名单中查询顾客的名字
   
2. 统计单词出现次数时, 用来存放需要忽略的单词
   

multiset

一个简单的使用场景: 统计一篇文章中某个单词的出现次数

multimap

简单的使用场景:

1. 词典里, 每个单词有多个释义
   
2. 作家有多个作品; 作者到所著书籍的映射, 作者姓名作为关键字, 书籍名称作为值
   

头文件

1. map和multimap
   

   Copy1#include <map>

2. set和multiset
   

   Copy1#include <set>

3. unordered_map和unordered_multimap
   

   Copy1#include <unordered_map>

4. unordered_set和unordered_multiset
   

   Copy1#include <unordered_set>

类型成员

类型别名

set系列容器

-	类型别名
关键字类型	key_type
元素(值)类型	value_type

set系列容器的元素存放关键字, 关键字亦是值, 关键字/元素/值相同; key_type和value_type是同一类型

示例

Copy1set<string>::value_type v1;        // string
2set<string>::key_type v2;          // string

map系列容器

-	类型别名
关键字类型	key_type
元素类型	value_type
值类型	mapped_type

map系列容器的元素存放成对的关键字和值, 保存二者关系

元素类型为pair, 由关键字类型和值类型组合而成

pair<const key_type, mapped_type>

关联容器的值类型别名mapped_type, 为map系列独有

示例

Copy1map<string, int>::value_type v3;    // pair<const string, int>
2map<string, int>::key_type v4;      // string
3map<string, int>::mapped_type v5;   // int

定义关联容器对象

1. 每个关联容器都有默认构造函数，创建一个给定类型的空容器
   

   Copy1C c;

2. 可以对关联容器进行列表初始化
   
3. 可以使用同类型容器初始化关联容器
   
4. 可以使用迭代器范围初始化关联容器，要求这些值可以转换为容器元素相容类型
   
5. 关联容器支持值初始化
   

示例

使用迭代器范围初始化set和multiset

Copy 1vector<int> ivec;
 2for (vector<int>::size_type i = 0; i != 10; ++i)
 3{
 4    ivec.push_back(i);
 5    ivec.push_back(i);
 6}
 7
 8set<int> iset(ivec.cbegin(), ivec.cend());
 9multiset<int> miset(ivec.cbegin(), ivec.cend());
10
11cout << ivec.size() << endl;            // 20
12cout << iset() << endl;                 // 10：无重复元素
13cout << miset.size() << endl;           // 20

关联容器迭代器

解引用一个关联容器迭代器时，会得到container::value_type类型对象的引用

	元素类型
set系列容器	value_type/key_type
map系列容器	value_type/pair<const key_type, mapped_type>

关键字不可更改

set系列容器的迭代器: 具有底层const

set类型同时定义了iterator和const_iterator类型，但两种类型都只有元素的读权限

Copy1set<int> ist = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
2set<int>::iterator set_it = iset.begin();
3
4if (set_it != iset.end())
5{
6    *set_it = 42;                        // 错误：只读
7    cout << *set_it << endl;
8}

map系列容器元素: pair的first成员具有顶层const

Copy 1 // <const key_type, mapped_type>
 2 // <const string, size_t>
 3
 4auto map_it = word_count.begin();
 5
 6cout << map_it->first;
 7cout << " " << map_it->second;
 8
 9map_it->first = "new key";            // 错误：元素关键字不可更改
10++map_it->second;

遍历关联容器

使用迭代器遍历关联容器

所有关联容器都支持begin和end操作

遍历有序关联容器时, 迭代器按关键字升序遍历元素: map, multimap, set, multiset

示例: map

Copy 1auto map_it = word_count.cbegin();        // 只进行读操作
 2
 3while (map_it != word_count.cend())
 4{
 5    // 输出每个记录的单词，以及其出现的次数
 6    cout << map_it->first << " occurs " << map_it->second << " times" << endl;
 7    ++map_it;
 8}
 9
10// 每个单词按字典顺序输出
11// 加入关联容器时, 会使用小于运算符; string的小于运算符为字典序

使用范围for

有序关联容器对关键字的要求

按关键字有序排序

要求关键字类型重载了小于运算符 < , 或者提供了元素的比较方法

如果关键字类型重载了小于运算符 < , 定义容器时给出元素类型即可; 需给出比较元素的函数指针

使用小于运算符比较关键字

1. 只使用小于运算符
   
2. 如果(key1 < key2)不成立，(key2 < key1)必成立
   

(key1 < key2)为真 <=> !(key2 < key1)为真

比较函数的实现

要求是严格弱序 strict weak ordering

如果关键字等价, 容器将它们视作相等

(k1 <= k2)为真 => (k2 <= k1)为假

(k1 <= k2 && k2 <= k3)为真 => (k1 <= k3)为真

(k1 <= k2 || k2 <= k1)为假 => (k1 == k2)为真; 如果(k1 == k2 && k2 == k3)为真 => (k1 == k3)为真

关键字查找

要求关键字类型重载了相等运算符 ==

示例: 提供元素比较方法

Sales_data类型没有重载小于运算符，但在初始化时指定了campareIsbn

使用decltype获得函数指针类型: 需要指示其为指针(加上 * )

Copy 1bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
 2{
 3    return lhs.isbn() < rhs.isbn();
 4}
 5
 6multiset<Sales_data, decltype(compareIsbn) *> bookstore(compareIsbn);
 7
 8// <=>
 9// multiset<Sales_data, decltype(compareIsbn) *> bookstore(&compareIsbn); 
10// 当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针

关联容器和泛型算法

1. 通常不对关联容器使用泛型算法: 重排算法和写容器元素算法都需要对元素执行写操作, 而关联容器的关键字不可更改; 只能在只读算法中使用关联容器
   
   set系列容器的关键字具有顶层const
   

   map系列容器键值对的first成员具有顶层const
   

2. 关联容器拥有成员函数find; 相比泛型算法find在遍历过程中进行查找, 更高效
   

3. 如果在只读算法中使用关联容器, 其常常作为输入序列, 或者输出序列
   

   • 如copy算法
     

   • 插入元素时, 使用插入迭代器