3.3 关联式容器
3.3.0 RB-Tree
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树 BST（AVL 是另一种）
rb-tree 提供遍历操作和 iterators，按中序遍历遍历，便可以得到排序状态
不能用 iterator 去改变元素的 key（其有严谨的排列规则）
rb-tree 提供两种 insertion 操作：
insert_unique()和insert_equal()，前者表示 key 独一无二，后者表示 key 可重复
GCC2.9下：
template<class Key, // key的类型class Value, // Value里包含key和dateclass KeyOfValue, // 从Value中取出key的仿函数class Compare, // 比较key大小的仿函数class Alloc = alloc>
class rb_tree
{
protected:typedef __rb_tree_node<Value> rb_tree_node;...
public:typedef rb_tree_node* link_type;...
protected:size_type node_count; // rb-tree节点数量，大小4link_type header; // 头指针，大小4Compare Key_compare; // key比大小的仿函数，大小1// sizeof: 9 ——> 12(填充到4的倍数)...
};
GCC4.9下：
_M_color 是 “枚举”（Enumeration）
3.3.1 set / multiset
测试
void test_multiset(long& value)
{cout << "\ntest_multiset().......... \n";multiset<string> c; // 创建一个multiset char buf[10]; clock_t timeStart = clock(); // 记录起始时间 for(long i=0; i< value; ++i) // 添加元素到multiset中{try {snprintf(buf, 10, "%d", rand()); // 将随机数转换为字符串格式c.insert(string(buf)); // 将字符串插入multiset中 }catch(exception& p) { // 捕获可能的异常cout << "i=" << i << " " << p.what() << endl; // 输出异常信息abort(); // 终止程序}}cout << "毫秒数 : " << (clock()-timeStart) << endl; // 输出时间差，计算插入时间 cout << "multiset.size()= " << c.size() << endl; // 输出multiset大小 cout << "multiset.max_size()= " << c.max_size() << endl; // 输出multiset的最大容量string target = get_a_target_string(); {timeStart = clock();auto pItem = find(c.begin(), c.end(), target); // 在multiset中使用 std::find(...) 查找目标字符串cout << "std::find()，毫秒数 : " << (clock()-timeStart) << endl; ...}{timeStart = clock(); auto pItem = c.find(target); // 在multiset中使用 c.find(...) 查找目标字符串cout << "c.find()，毫秒数 : " << (clock()-timeStart) << endl; ...} c.clear(); // 清空multiset
}安插元素是使用
insert()，其位置由红黑树决定
容器自己有
c.find()，其会比全局的::find()快
运行结果：
随机数据填充容器：6609ms（其在填充的时候就进行排序了）；直接搜索 ::find()：203ms；c.find()：0ms
深度探索
以 rb-tree 为底层结构，因此有——元素自动排序，key 与 value 和一
set / multiset 提供遍历操作和 iterators，按中序遍历遍历，便可以得到排序状态
禁止用 iterator 去改变元素的值（其有严谨的排列规则）
set的key 独一无二，其
insert()操作用的 rb-tree 的：insert_unique()multiset 的 key 可以重复，其
insert()操作用的 rb-tree 的：insert_equal()
GCC2.9下：
// set
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set
{
public:typedef Key key_type;typedef Key value_type;typedef Compare key_compare;typedef Compare value_compare;
private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;rep_type t; // 采用红黑树作为底层机制
public:typedef typename rep_type::const_iterator iterator;// 注意：这里是const_iterator，所以不能用iterator改元素...
};
3.3.2 map / multimap
测试
void test_multimap(long& value)
{...multimap<long, string> c; // 创建一个multimap，key 为 long 类型，value 为 string 类型 char buf[10];clock_t timeStart = clock(); // 记录起始时间 for(long i=0; i< value; ++i) // 添加元素到multimap中{try {snprintf(buf, 10, "%d", rand()); // 将随机数转换为字符串格式并复制到缓冲区// multimap 不可使用 [] 做 insertion c.insert(pair<long, string>(i, buf)); // 将元素插入multimap中 }catch(exception& p) { // 捕获可能的异常cout << "i=" << i << " " << p.what() << endl; // 输出异常信息abort(); // 终止程序}}cout << "毫秒数 : " << (clock()-timeStart) << endl; // 输出时间差，计算插入时间 cout << "multimap.size()= " << c.size() << endl; // 输出multimap大小cout << "multimap.max_size()= " << c.max_size() << endl; // 输出multimap的最大容量long target = get_a_target_long(); timeStart = clock(); auto pItem = c.find(target); // 在multimap中查找目标 key cout << "c.find()，毫秒数 : " << (clock()-timeStart) << endl; if (pItem != c.end())cout << "找到，value=" << (*pItem).second << endl; // 如果找到，输出找到的值elsecout << "未找到！" << endl; // 如果未找到，输出未找到的信息 c.clear(); // 清空multimap
}
c.insert(pair<long, string>(i, buf));中 key 是从1~1000000，value 是随机取的，将其组合为 pair 插入
运行结果：
随机数据填充容器：4812ms（其在填充的时候就进行排序了）；c.find()：0ms
深度探索
以 rb-tree 为底层结构，因此有——元素自动排序
map/ multimap 提供遍历操作和 iterators，按中序遍历遍历，便可以得到排序状态
不能用 iterator 去改变元素的key（其有严谨的排列规则），但可以用 iterator 去改变元素的 data
因此 map / multimap 将 user 指定的 key_type 设定成
const
map的key 独一无二，其
insert()操作用的 rb-tree 的：insert_unique()multimap 的 key 可以重复，其
insert()操作用的 rb-tree 的：insert_equal()
GCC2.9下：
template <class Key, // key的类型class T, // data的类型class Compare = less<Key>, class Alloc = alloc>
class map
{
public:typedef Key key_type;typedef T data_type;typedef T mapped_type;typedef pair<const Key, T> value_type;// 注意：这里是const Key ———— 防止改keytypedef Compare key_compare;
private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t; // 采用红黑树作为底层机制
public:typedef typename rep_type::iterator iterator;...
};
map 的插入元素有特殊写法：
c[i] = string(buf)，其中i就是 key；multimap没有map 的
[]功能：访问元素： 如果指定的键存在于映射中，
map[key]将返回与该键关联的 data；如果键不存在，map[key]将自动创建一个新的键值对，key 为指定的 key，data 为默认 data，并返回这个默认 data
3.3.3 HashTable
-
元素的位置 = key % bucket大小
-
bucket vector 的大小为质数
-
当元素个数大于 bucket 的总数时，bucket vector 扩充并重新打散放在新计算的 bucket 中（rehashing 很花时间）—— bucket 一定比元素多
在扩充时，按 vector 扩充为2倍大小，但会选择靠进这个数的一个质数做新的大小
GCC2.9下：
template <class Value, // Value里包含key和dateclass Key, // key的类型class HashFcn, // hash函数class ExtractKey, // 从Value中取出key的方法class EqualKey, // 判断key相等的函数class Alloc>
class hashtable
{
public:typedef HashFcn hasher; typedef EqualKey key_equal; // 判断key相等的函数typedef size_t size_type;
private:// 3个函数对象，大小一共3（应该是0，因为一些因素）hasher hash;key_equal equals;ExtractKey get_key;typedef __hashtable_node<Value> node;vector<node*, Alloc> buckets; // vector里3个指针，大小12size_type num_elements; // 大小4// 一共19 ——> 20（调整为4的倍数）
public:size_type bucket_count() const { return buckets.size(); }
};
Hash函数：
偏特化写不同类型的 hash 函数，下图都是数值类型，直接返回就可以
下图对 c 风格的字符串做了处理（也可以自己设计），来生成 hash code
注意：老版本STL没有提供现成的 string 类型的 hash 函数
3.3.4 unordered容器
测试
void test_unordered_multiset(long& value)
{cout << "\ntest_unordered_multiset().......... \n";unordered_multiset<string> c; // 创建一个 unordered_multiset char buf[10];clock_t timeStart = clock(); // 记录起始时间 for(long i=0; i< value; ++i) // 添加元素到 unordered_multiset 中{try {snprintf(buf, 10, "%d", rand()); // 将随机数转换为字符串格式c.insert(string(buf)); // 将字符串插入 unordered_multiset 中 }catch(exception& p) { // 捕获可能的异常cout << "i=" << i << " " << p.what() << endl; // 输出异常信息abort(); // 终止程序}}cout << "毫秒数 : " << (clock()-timeStart) << endl; // 输出时间差，计算插入时间 cout << "unordered_multiset.size()= " << c.size() << endl; // 输出 unordered_multiset 大小cout << "unordered_multiset.max_size()= " << c.max_size() << endl; // 输出 unordered_multiset 的最大容量cout << "unordered_multiset.bucket_count()= " << c.bucket_count() << endl; // 输出 unordered_multiset 的桶数量cout << "unordered_multiset.load_factor()= " << c.load_factor() << endl; // 输出 unordered_multiset 的负载因子cout << "unordered_multiset.max_load_factor()= " << c.max_load_factor() << endl; // 输出 unordered_multiset 的最大负载因子cout << "unordered_multiset.max_bucket_count()= " << c.max_bucket_count() << endl; // 输出 unordered_multiset 的最大桶数量for (unsigned i=0; i< 20; ++i) {cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n"; // 输出前20个桶中的元素数量} string target = get_a_target_string(); {timeStart = clock();auto pItem = find(c.begin(), c.end(), target); // 在 unordered_multiset 中使用 std::find(...) 查找目标字符串cout << "std::find()，毫秒数 : " << (clock()-timeStart) << endl; if (pItem != c.end())cout << "found, " << *pItem << endl; // 如果找到，输出找到的元素elsecout << "not found! " << endl; // 如果未找到，输出未找到的信息 }{timeStart = clock(); auto pItem = c.find(target); // 在 unordered_multiset 中使用 c.find(...) 查找目标字符串cout << "c.find()，毫秒数 : " << (clock()-timeStart) << endl; if (pItem != c.end())cout << "found, " << *pItem << endl; // 如果找到，输出找到的元素elsecout << "not found! " << endl; // 如果未找到，输出未找到的信息 } c.clear(); // 清空unordered_multiset
} 运行结果：
随机数据填充容器：4406ms；直接搜索 ::find()：109ms；c.find()：0ms；前二十个 bucket 中只有一个有24个元素
深度探索
