STL关联容器总结

一、关联式容器

STL 关联容器分为 set（集合）和 map（映射表）两大类，及其衍生体 multiset 和 multimap。这些容器的底层机制均以 RB-tree（红黑树）实现。RB-tree 也是一个独立容器，但并不开放使用。

SGI STL 还提供一个不在标准规格的关联式容器 hash_table（散列表），以及以 hash_table 为底层机制而完成的 hash_set散列集合、hash_map散列映射表、hash_multiset散列多键集合、hash_multimap散列多键映射表。

关联容器，类似关联式数据库，每个元素都有一个键值key和一个实值value。关联式容器的内部结构是一个平衡二叉树，包括 AVL-tree、RB-tree、AA-tree，STl 中运用的是 RB-tree红黑树。

二、红黑树 RB-tree

1. 基本性质

• RB-tree 是一个二叉搜索树。
• 每个节点只能是红色或黑色（图中深色代表黑色，浅色代表红色）。
• 根节点为黑色。
• 红色节点的子节点必须为黑。
• 任一节点至NULL（树的尾端）的任何路径，包含黑色节点数相同。

三、set

1. 基本性质

• set 元素的键值就是实值，实值就是键值。
• set 不允许两个元素有相同的键值。
• 不可以通过 set 的迭代器改变其元素值，即 set iterator 是一种 constant iterators。
• 当对 set 进行插入删除操作后，原有的迭代器依然有效，被删除元素的迭代器除外。

2. STL 提供一组 set / multiset 相关算法，详见算法部分笔记。

四、map

1. 基本性质

• map 的所有元素都是 pair，同时拥有实值value和键值key。pair 的第一元素为键值，第二元素为实值。
• map 不允许两个元素拥有相同的键值。
• 不可以通过 map 的迭代器改变其元素的键值，可以修改元素的实值。
• 当对 map 元素进行增加或删除操作后，原有的迭代器依然有效，被删除的元素的迭代器除外。

五、multiset、multimap

multiset 和 multimap 的特性及用法与 set 和 map 完全相同，唯一差别在于允许键值重复。