12,set、map、multiset、multimap底层均以红黑树实现。红黑树是一种平衡二叉搜索树,平衡二叉搜索树比失去平衡的二叉搜索树来说插入和删除的时间长,但是查找速度快,红黑树相对普通平衡二叉搜索树来说据说统计性能比较好。红色树的迭代器内含一个节点的指针,按照一定的规则来移动,是双向迭代器。跟list一样,每个都是个节点,所以插入不会导致其他迭代器失效,内存也是随用随申请和释放。
13,二叉搜索树具有对数平均时间的表现,但是这样的表现构造在输入数据具有足够随机性的假设上。hashtable的数据结构在插入、删除、搜索等操作上也具有常数平均时间的表现,而且这种表现是以统计为基础,不需要依赖输入数据的随机性。
14,SGI STL的hashtable采用开链法来实现hashtable,用一个vector来存放bucket,bucket内含一个链表来存放元素。与红黑树实现的容器不同的是,hashtable内的元素并不是有序的。hashtable的迭代器内含容器的指针,和当前元素的指针,依照一定的规则向前移动,注意,这是一个前向迭代器,不能向前移动。还是节点型的老规矩,插入不会导致迭代器失效,节点的内存随用随申请和释放,但是存放bucket的vector的内存不会变小和释放。
15,hashtable存放无法处理基本类型外的数据,用户需要自己定义hash fuction。
16,STL只规范复杂度与接口,并不规范实现方法。
17,hash_set、hash_map、hash_multiset、hash_multimap均以hashtable来实现。