今天，继续学习， 不过收获看起来比前两天要少啊。 对于这章中的stack，queue， slist， 侯捷表现的让我失望啊， 不过， 作为基本知识回顾一下， 还是挺好的。
先谈谈List， 这部分写的挺好的， 很清楚， 其中list中的member function, 可以提取出来，充实自己的代码库， 毕竟list 的操作用的太广了， 自己猛然写一下， 出错的概率还是很大的。 闲话不多说了， 来看看list 中transfer的实现， 我是很喜欢这个function的， 逻辑清楚， 表达简单。
这个function所作的是：将一连续范围的elements搬移到指定position的前面， 实现上主要是指针的移动。 其次， 这个函数是list中一些函数的核心， 如splice, sort, merge. 这个函数有如下7个步骤：
输入： position, a range [first, last)
1. last_node->prev->next = position_node
2. first_node->prev->next = last_node
3. position_node->prev->next = first_node
4. tmp_node = position_node->prev
注意：前3步的操作都是: update the "next" field of the previous node of last_node, first_node, and position_node, respectively.
后3步， 那当然就是： update the "prev" field
5. position_node -> prev = last_node->prev
6. last_node-> prev = first_node->prev
7. first_node -> prev = tmp.
还有值得一提的是list自己提供了sort函数， 没有用STL algorithm sort(). 其原因是 sort（） 需要 randomAccessIterator. (哦， 侯捷在这里有个拼写错误， p142: RamdonAccessIterator --> RandomAccessIterator). list->sort()核心是qsort(), 今天不研究了， 等看算法的时候， 一并再看。
对于stack, queue, 侯捷没有花很多篇幅讲， 只是简单描述了一下， 不过就其本身来讲， 确实挺简单。 但还是可以多讲讲， 他们的应用。 什么时侯用他们合适， 毕竟现在大多数情况下， 我们并不是没有足够的方法去解决一个问题， 而是我们往往不知道该如何决定一个最佳方案， 这可能更多的是要靠经验的积累。 说多了。
slist 是一个挺奇怪的东西， 从semantic上来说比list简单， 但是从architecture上来说， 又比list复杂。 看了半天， 不知道何时该使用它， 但但为了效率使用它吗？
明天希望把deque看完， 应该不会失望吧。
11:16:14 AM Wednesday, May 13, 2009
补充一下：
为了比较 list 和 slist 的性能， 做了个实验。 不做不知道啊， 原来slist 已经不被ISO C++ 支持了， 现在只能 include <slist.h> , 而不是 include <slist>.
测试了一下 insert 的时间
|
1000 |
10000 |
100000 |
1000000 |
10000000 |
| list |
0.255973 ms |
1.68788 ms |
16.6021 ms |
163.434 ms |
1705.28 ms |
| slist |
1.54889 ms |
153.791 ms |
42899.8 ms |
|
|
当insert 次数大于10000时， slist 就表现的很差劲了， 不过这是由于slist并没有提供backward interator 的操作， 可以理解。 本来还想测一下， slist.insert_after(), 不过， 发现每次调用这个函数， 竟然会有segment fault, 算了， 也不去管它， 毕竟ISO C++ 都不支持它了， 以后也不会用它。
2:53:03 PM Wednesday, May 13, 2009