Boolan_STL与泛型编程_第三周笔记

本周课程重点讲解了容器deque、容器queue、容器rb_tree、容器set/multiset、容器map/multimap以及容器hashtable的源代码和使用方法，简单介绍了hash_set/hash_multiset、hash_map/hash_multimap以及容器unordered的概念。

1、容器deque

1.1 容器deque结构

容器deque内含有多个buffer（缓冲区），每个buffer中的iterator有4个指针，分别是cur、first、last和node。本小节主要讲解容器deque的结构以及如何插入一个元素。

总结本小节内容如下：

（1）每个buffer中iterator的4个指针：node指向buffer，first和last指向buffer的头和尾，cur指向buffer中某一个元素；

（2）进行插入元素之前，需判断是否走到buffer的边界，如果没有达到buffer边界，则直接插入元素，如果达到buffer边界，则通过node指向下一个buffer；

（3）deque中有4个数据成员：两个iterator分别指向deque的begin和finish，一个指向vector的指针（map，控制中心）和vector的大小（map_size），所以共16+16+4+4=40个字节（32位cpu）；

（4）deque的模板参数有3个，包括元素类型、分配器、BufSiz(默认是0，G4.9没有该参数)，__deque_buf_size用于计算buffer size，如果没有指定BufSiz，那么会根据元素的大小（sz）设置buffer size，如果一个元素的大小小于512，那么要用512除以元素的大小来计算buffer size. 如果大于等于512，buffer size会设置为1；

（5）deque<T>::insert()，指定一个位置放置新的元素，有2种情况：a、安插点在头或尾(position.cur是start.cur或finish.cur)，调用push_front(x)（安插点在最前端）或push_back(x)（安插点在最尾端）实现；b、如果不在头和尾，那么就要调用辅助函数insert_aux(position, x），insert_aux插入数据时会先判断插入点前后哪一边的元素少，取少的那一边全部元素向前移动一个位置，之后空出来的位置放入x，这样做是为了使得程序尽可能高效。

1.2 deque模拟连续空间

deque表示双向开口容器，它模拟了一个连续的存储空间，但实质上它是一个分段连续的容器。本小节主要讲解了deque如何模拟连续空间。

总结本小节内容如下：

（1）总的来说是依靠deque iterators实现分段连续的，实现源代码见上图；

（2）两个迭代器之间的距离（difference_type operartor-(const self& x) const {}）=中间完整缓冲区个数(node-x.node-1)*bufsiz+起始buffer的元素数量(x.last-x.cur)+结尾buffer的元素数量(cur-first)；

（3）移动一个位置：调用++时，先判断cur==last，如果是，则set_node(node+1)，移动到后一个buffer的第一个元素的位置；调用--时，先判断cur==first，如果是，那么set_node(node-1)切换到前一个buffer的最后一个元素的位置；

（4）移动多个位置：先判断是否会跨越缓冲区，如果是，那么再计算要跨越几个缓冲区，再移动node指针来跨越缓冲区，到达最后一个缓冲区，再计算要偏移几个元素，最后到达指定的位置，通过重载+=，-=，+，-运算符实现，其中operator-=相当于+= -n，所以-=是利用operator+=来实现，其他类似；

（5）容器deque中vector每次按照2倍大小进行扩充，扩充后，会将之前的元素拷贝到中段，前后都能留有空闲空间，便于前后扩展。

1.3 queue和stack

queue（先进先出）和stack（先进后出）均是通过调用deque来实现的，它们内部拥有一个deque，因此他们的各个函数都是调用的deque的函数。

queue和stack也可以选择list作为底部结构，但是默认是选择deque，选择deque作为底部支撑效率更高；stack可以选择vector作为底层结构，但queue不可以；queue和stack都不可以选择set或map作为底层结构。

queue和stack都不允许遍历，也不提供iterator，因为不允许中间插入/删除元素。

2、容器rb_tree

rb_tree(红黑树)是平衡二分搜索树中常被使用的一种，是关联式容器，查找和插入元素快。

总结本节内容如下：

（1）遍历时，++iter得到的元素是按照key排序的；

（2）rb_tree为set和map提供底部支撑，其中map允许改变data，不允许改变key；

（3）rb_tree提供两种insert操作：insert_unique()和insert_equal()，insert_unique()表示节点的key在整个树中是唯一的，insert_equal()表示节点的key可以重复；

（4）rb_tree的元素顺序：从左到右，从下到上；

（5）rb_tree的模板参数：key、value(key和data合成value)、KeyofValue（从value中取key的方法）、Compare(两个节点key比较大小的方法)、Alloc=alloc；

（6）rb_tree的大小： G2.9 中大小是12（两个指针和一个泛函数，4+4+1=9，对齐成4的倍数后是12），G2.9 中大小是24（3ptr+1color）。

3、容器set/multiset和容器map/multimap

（1）对于set/multiset来讲key就是value，不能改变元素值。

（2）set插入数据是调用的rb_tree的insert_unique(), multiset插入数据是调用的rb_tree的insert_equal()。

（3）set/multiset的iterator是rb_tree中的const_interator，防止修改iterator指向的元素。

（4）set的所有操作都是调用底层rb_tree的操作，所以set也未尝不是一个container adapter。

（1）对于map/multimap来说key是const类型，防止用户更改key。

（2）map/multimap的iterator就是rb_tree的iterator。

（3）容器map独特的operator[ ]，其内部实现iterator _i = lower_bound(_k)，如果map中没有_k, 那么会返回适合放置_k的位置，之后会调用insert插入到map中。

4、容器hashtable

hashtable底层实现是通过开链法来实现的，hashtable内的元素称为桶（bucket),而由桶所链接的元素称为节点（node),其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。hash_set、hash_map、hash_multiset、hash_multimap四个关联容器都是以hashtable为底层实现方法。

总结本节内容如下：

（1）当空间足够时，编号为多少就放在相应位置，当空间不够时，H/M余数是多少就放置在相应位置，这样会发生碰撞，解决办法是使用链表；

（2）当元素个数比篮子的个数多的时候，会将hashtable打散，将篮子增加到大约是原有的2倍；

（3）hashtable有6个模板参数：value，key, class HashFcn(计算元素对应的编号), class ExtractKey(从元素中取出key), class EqualKey(计算key相等的方法), class Alloc=alloc；

（4）hashtable中iterator的设计，考虑到遍历完一个链表后，要能够回到hashtable, 再遍历下一个链表，所以iterator中除了有一个指向当前节点的指针外node* cur, 还有一个指向hashtable本身的指针hashtable* ht；

（5）hashtable的大小：1（HashFcn）+1（EqualKey）+1（ExtractKey）+12（vector buckects占12字节（内部有3个指针））+4（size_type num_elements占4个字节）=19，对齐后是20个字节。

5、容器unordered

c++11将hash_set,hash_multiset,hash_map,hash_multimap这4个名字改为unordered_set, unordered_multiset, unordered_map,unordered_multimap。

（1）容器unoerdered_set中元素不能重复；

（2）c.bucket_size(i)打印第i个篮子中元素的数量；

（3）总的bucket的个数一定大于总元素的个数。

6、课后补充学习

（一）红黑树与平衡二叉树

红黑树介绍：http://blog.csdn.net/eric491179912/article/details/6179908

平衡二叉树介绍：http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

红黑树十分复杂，只学习了一点，后续继续学习。

红黑树与平衡二叉树的区别：

1、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知；

2、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单；

3、红黑树就是平衡二叉树，只不过它的每个节点多加了一个标志属性，这个标志是在增加和删除节点时用的。对一个平衡二叉树做几次增加删除节点的操作，它就变成非平衡的了，这不利于查找。所以每次增加删除节点后都要进行调整，调整的算法就是按红黑树的规则“红节点的孩子不能是红节点”。对一个n个节点的红黑树做一次这样的调整最多需要log(n)步。

（二）stack的用法

详见：http://blog.csdn.net/wallwind/article/details/6858634

（三）#include <cstring>、#include<string>与#include<string.h>的区别

#include<string>是C++特化的字符容器，内含string类。

#include<string.h>是标准C提供的字符处理函数集，面向char *。

#include <cstring>是C++为兼容C提供的的C++版本，里面的主要改进有：将一些隐藏变量编入命名空间；修正一些C++编译器认为Bug的代码，其余没发现很多改变。