今天是第5天的学习， 第4章看完了。 先谈谈Deque的设计吧。
Deque的概念是挺简单的： 它是一种双向开口的连续的线性空间。 双向意味着， deque可以进行头尾两端的插入， 这弥补了 vector的不足； 线性连续意味着， deque的iterator是random的， 这又弥补了list的不足。 看起来， deque很好啊。 不过， 其代价就是复杂的iterator 的设计。
书中的定义是： deque 是由一段一段的定量连续空间构成， 一旦有必要在deque的前端或尾端增加新空间， 变配置一段定量连续空间， 串接在整个deque的头端或尾端。
Deque的主要结构是： 定义了一个map, 其实质是一个指针数组， 每一element 在这个数组中都指向一个buffer， 对于这个指针数组， 又维护了两个指针start和finish，分别指向头buffer和尾buffer。
对于每个buffer来说， 其实质就是个data 数组，对于这个数组， 又有四个指针，分别是cur， first， last， 和node。 其中 node 指向的是map, 就是整个deque的中央控制器， cur， first， last，分别对应这个数组当前位置， 起始位置， 结束位置。
结构明白了， 那么deque的操作也就大致清楚了： 就是指针的变化， 和memory copy. 不过， 相对于vector和list， 我们需要考虑的边际条件就增加了一些。 因为， 一旦遇到buffer的边缘， 我们就需要新创建一个buffer或跳的一个buffer中， 这又伴随着一系列的指针操作和memory的移动。
理解了这些， 那么实际的实现就很简单了。 我原以为要看上4个小时， 结果1个多小时就全看完了。 很舒服。
对于heap和priority_queue就没什么多说了， 就是一个heap算法的问题， CLRS 中讲的很清楚， 不重复了。 感叹一下： 看看这里的实现， 再想想CLRS中的分析， 真是很有拨开云雾见天日的感觉， 一切都是那么的自然， 同时也觉得generic design很不错。
花了五天， 把侯捷的书的前4章都看完了， 感触最深的就是指针的操作和memory 的管理， 不过对于何时该采用合适的容器还是心有疑虑。
明天， 开始比较艰难的一章了， 继续坚持。
12:26:14 PM Thursday, May 14, 2009
测评一下：
图一， push_back（）， times： 10 -- 10000000， the results of vector is baseline. （所化时间的比较）
图二， insert at beginning, times： 10 -- 10000， the results of vector is baseline. （所化时间的比较）
图三 insert at the end, times： 10 -- 10000， the results of vector is baseline. （所化时间的比较）
图四 pop_back(), times： 10 -- 10000， the results of vector is baseline. （所化时间的比较）
测试了一下， 很惊讶的发现， deque 在这几种情况下， 都表现的很好， 除了pop_back（）。 vector表现的最好的就是pop_back()了， 这也是符合它design spec的。 依次谈谈结果：
1. push_back(): 在没做实验前， 我想的是 performance 比较是： vector 和 deque 相接近， 但大于 list。 不过， 结果是deque 远好于 vector。 其原因应该是deque减少了malloc的次数， 虽然vector也一次allocate两倍于old vector的memory， 但是， deque 表现的更好。
2. insert at the beginning: 我的想法是， vector 表现的最差， list最好。 不过， 结果是deque最好。 不过， 想一想就明白了， deque的设计也是允许头插入的啊。
3. insert at the end: 情况跟2差不多。 原来还想做一做， insert middle 的情况， 不过时间不多了， 以后再做。
4. pop_back： 这个结果， 又让我楞了一下， 为什么现在vector又优于deque呢？ 想来一下， 自己的答案是， vector 就是简单把数据移除， 并没有什么额外的memory操作， 当然是好过deque和lsit了。
现在， 看起来， 如果，插入、移除次数小的话， deque还是很有优势的啊。 不过， 还有些实验要做， 如find, sort， erase， 等， 有时间在做吧。
另外， 自己还是要确认一下自己的答案是否正确。
3:18:37 PM Thursday, May 14, 2009