顺序容器与关联容器根本的不同: 顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,而关联容器中的元素是按关键字来保存和访问的
关联容器支持高效的关键字查找和访问
关联容器类型
两个主要的关联容器 map set
标准库提供8个关联容器,其不同主要在三个方面:
- 是基于
set或是map - 关键字是否重复,允许重复的前缀都有
multi - 容器是否有序 不按按顺序保存的都以
unordered开头
Eg. Unordered_multiset 就是一个无序的允许关键字重复的集合
Set 则是有序的不允许关键字重复的集合
在无序容器中 使用哈希函数来组织元素
当从map中提取元素时 会得到一个pair类的对象
简单来说pair类就是一个模板类 保存两个名为first和second的公有数据成员, 在这分别保存了关键字和对应值
Map<string,size_t> wc;
For(const atuo &w: wc){
cout<<w.first<<w.second<<endl;
}
当初始化map时，必须提供关键字类型和值类型，并将每个关键字-值对用{}括起来
对于有序关联容器，定义的类型必须包含比较操作，若未定义< 也可以提供自己定义的操作来代替
Mutliset<sales_data, decltype(compareISBN)*> bookstore(compareISBN);
对于set而言 key_type 和value_type相同
对于map而言 value_type为对应的pair类型 而key_type和mapped_type是关键字和映射的类型
Set<string>:: value_type v1;
Set<string>:: key_type_type v2; // v1 v2都为string
Map<string, int>:: value_type v3;
Map<string, int>:: key_type v4;
Map<string, int>:: mapped_type v5;
// v3, v4, v5分别为pair<string, int> string 和 int
对关联容器解引用时 会得到类型为容器value_type类型的值引用
关联容器中的迭代器都是const的 即不能通过迭代器改变关键字 但是map类型可以改变映射值的内容
关联容器操作
类似顺序容器 使用.insert()或.empalce()可以向关联容器中插入元素 可以是范围 也可以是{}的值列表
向map中插入元素时 既可以是{}键值对方式 也可以使用make_pair显式构造一个pair对象作为输入
insert返回值为pair类型对象
其first成员是一个迭代器 指向插入的元素
second成员是一个bool值 指示插入成功还是已存在
同样 使用.erase()来删除一个元素或一个范围的元素 返回值为void
关联容器还额外提供了一个版本的erase 接受key_type类型的参数
删除所有匹配给定关键字的元素 返回删除元素的数量
map容器也提供下标运算符和对应at函数 但不同之处在于
- 如果该关键字不在map中 会自动为它创建一个元素并插入到map 对应关联值将进行初始化
- 其返回为映射 即类型为
mapped_type与 解引用得到的不同
Map<string, int> word; word["hello"] = 3;
//插入了一个关键字为hello的元素 关联值进行值初始化 然后将3赋予它
关联容器可以通过.find()查找元素 .count()为某个元素计数
.lower_bound(k)/.upper_bound(k) 返回一个迭代器 指向第一个关键字不小于/不大于k的元素
.equal_range(k) 返回一个pair 两个成员分别为指向第一个匹配k的 和最后一个匹配k的迭代器 等价于同时使用lower_bound 和upper_bound确定范围
无序容器在储存上组织为一组桶 每个桶保存0个或多个元素
无序容器使用一个哈希函数将元素映射到桶
访问元素时 容器通过计算元素哈希值来确定访问哪个桶 容器将所有具有相同哈希值的元素放在一个桶内
因此 无序容器的性能依赖于哈希函数的质量和桶的数量和大小
将不同关键字的元素映射到同一个桶也是允许的
当一个桶保存多个元素时 需要顺序搜索元素
当一个桶中有大量元素时 查找一个特定元素就需要大量比较操作
无序容器通过hash<key_type>类型的对象来生成每个元素的哈希值 由于标准库为内置类型和string等定义了hash模板 因此我们可以直接定义对应的无序容器
但是 不能直接定义关键字类型为自定义类类型的无序容器
必须提供对应的哈希函数和判定相等函数==
Unordered_mutliset<sales_data, decltype(hasher)*, decltype(equaler)*> booker(42, hasher, equaler);
如果类定义了==运算符 则可以只重载哈希函数
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，再具体一点是红黑树 所以map、set的增删操作时间时间复杂度是log n
而unordered_map、unordered_set底层实现是哈希表。
红黑树
红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：
- 节点是红色或黑色
- 根节点是黑色
- 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），
null节点的父节点在红黑树里不将其看作叶子节点 - 红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。
红黑树的优点就是对有序数据的查询操作不会慢到O(N)的时间复杂度。
将节点左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。
性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点。
更详细的部分参照这篇博客红黑树详解