关联容器type
status
date
slug
summary
tags
category
icon
password
Property
根据应用场景的不同，STL实现了两种不同结构的关联式容器：树型结构和哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（红黑树）作为其底层结构，容器中的元素是一个有序的序列。
pair类模板
关联式容器存储的是“键值对”形式的数据，例如：
<“penny”,“leonard”>。这个键值对第一个元素作为键（key），第二个元素作为值（value）。考虑到 “键值对” 并不是普通类型的数据，C++ STL标准库提供了
pair类模板 ，其专门用来将2个普通元素first和second创建成一个新元素<first, second>。pair类模板定义在#include<utility>头文件中：pair 支持的操作：
在创建
pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同在定义时进行成员初始化：
如果定义多个相同的
pair类型对象，可以使用typedef简化声明：set和multiset
set的底层是用平衡搜索二叉树（红黑树）实现的，是按照一定次序存储元素的容器。在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格若排序准则进行排序在
set中，元素的value也表示key，并且每个value(key)必须是唯一的。map中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。set中插入元素时，只需要插入value即可，不需要构造键值对。set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。set中的元素不可以重复（因此可以使用set进行去重）set中的元素不允许修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
set的模板参数列表
T: set中存放元素的类型，实际在底层存储<value, value>的键值对Compare：set中元素默认按照小于来比较Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理set的构造
set的迭代器
成员方法 | 功能 |
begin() | 返回指向容器中第一个（已排好序的第一个）元素的双向迭代器。如果 set 容器用const限定，则该方法返回的是const类型的双向迭代器 |
end() | 返回指向容器最后一个元素（是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器 |
rbegin() | 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器 |
rend() | 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器 |
cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值 |
cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值 |
crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值 |
crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值 |
set的增删查
成员方法 | 功能 |
find(val) | 在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
lower_bound(val) | 返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(val) | 返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
equal_range(val) | 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。 |
empty() | 若容器为空，则返回 true；否则 false。 |
size() | 返回当前 set 容器中存有元素的个数。 |
max_size() | 返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。 |
insert() | 向 set 容器中插入元素。 |
erase() | 删除 set 容器中存储的元素。 |
swap() | 交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。 |
clear() | 清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。 |
emplace() | 在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。 |
emplace_hint() | 在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。 |
count(val) | 在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。 |
multiset的使用
multiset和set的接口近乎一致，唯一不同于set的在于multiset允许键值冗余：正是
multiset允许了键值冗余，所以multiset的两个函数接口find和count与set的也是有区别的：成员函数count | 功能说明 |
set对象 | 值为val的元素存在则返回1，不存在则返回0 |
multiset对象 | 返回set中值为x的元素的个数 |
成员函数find | 功能说明 |
set对象 | 返回值为val的元素的迭代器位置 |
multiset对象 | 返回底层搜索树中序的第一个值为val的元素的迭代器 |
map和multismap
map通常被实现为红黑树，是关联容器，按照特定的次序（按照key来比较）存储由键值key和值value组合而成的元素。在
map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列）。map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。operator[]中实际进行插入查找。map中的key是唯一的，并且不能修改。key： 键值对中key的类型
T： 键值对中value的类型
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
map的构造
insert插入函数
insert函数声明：在
map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功。因此，在使用insert时，首先用key和value构造一个pair对象，再把pair对象作为参数传入insert函数。借助
pair构造函数：借助
pair构造匿名对象插入：调用
make_pair函数模板插入：使用
{}：在新标准下创建
pair 最简单的方式是使用括弧初始化于参数列表。[ ]运算符重载
[]运算符重载函数原型声明：[ ]运算符重载函数的具体源码实现如下：针对该返回值，其主要是进行了两大步骤：
- 首先调用
insert函数插入键值对返回迭代器ret
- 通过返回的迭代器
ret调用元素值value
[ ]运算符重载的好处，既可以遇到新
key像insert一样插入，又满足了insert未有的功能，查找并修改。统计水果出现次数：
map的迭代器
成员方法 | 功能 |
begin() | 返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
end() | 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
rbegin() | 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
rend() | 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
map的增删改查
成员方法 | 功能 |
find(key) | 在map容器中查找键为key的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和end()方法一样的迭代器。另外，如果 map容器用const限定，则该方法返回的是const类型的双向迭代器。 |
count(key) | 在当前map容器中，查找键为key的键值对的个数并返回。注意，由于map容器中各键值对的键的值是唯一的，因此返回值最大为1 |
lower_bound(key) | 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(key) | 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
equal_range(key) | 该方法返回一个pair对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。 |
empty() | 若容器为空，则返回 true；否则 false。 |
size() | 返回当前 map 容器中存有键值对的个数。 |
max_size() | 返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。 |
operator[] | map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。 |
at(key) | 找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。 |
insert() | 向 map 容器中插入键值对。 |
erase() | 删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。 |
swap() | 交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。 |
clear() | 清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。 |
emplace() | 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。 |
emplace_hint() | 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。 |
multimap的使用
multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。multimap中没有重载operator[]操作（因为multimap允许冗余，导致key和value面临一对多的关系）multimap允许冗余，这也就导致其内部的find和count函数和map中的有所区别，如下：成员函数count | 功能说明 |
map对象 | 值为key的元素存在则返回1，不存在则返回0 |
multimap对象 | 返回set中值为key的元素的个数 |
成员函数find | 功能说明 |
map对象 | 返回键值为key的元素的迭代器位置 |
multimap对象 | 返回底层搜索树中序的第一个值为key的元素的迭代器 |
unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个
unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构是哈希函数。这些容器不是使用比较运算符来组织元素，而是使用哈希函数（hash function） 和关键字类型的
== 运算符组织元素。map/set与unordered_map/unordered_set的区别
ㅤ | unordered_map / unordered_set | map / set |
底层数据结构 | 哈希表/散列表 | 红黑树 |
是否有序 | 无序 | 有序 |
查找的效率 | O(1) | O(logN) |
迭代器类型 | 单向迭代器 | 双向迭代器 |
头文件 | #include<unordered_map(set)> | #include<map(set)> |
在内部，
unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储，使用无序容器的程序输出一般会与有序容器的版本不同。
无序容器在存储上组织为一组桶，每个桶保存零或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此无序容器的性能依赖于哈希函数的质量和桶的数量及大小。
无序容器管理操作：
默认情况下，无序容器使用关键字类型的
==运算符比较元素，还使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值。标准库为内置类型和一些标准库类型提供了hash模板。因此可以直接定义关键字是这些类型的无序容器，而不能直接定义关键字类型为自定义类类型的无序容器，必须先提供对应的hash模板版本。除了使用默认的
hash 模板之外，还可以提供自己的相等比较函数和计算哈希值的函数：上面的代码同时指定了
hash 函数和相等性比较函数，如果我们的类有自己的 == 操作符，可以仅仅只覆盖哈希函数：