今天开始了算法的学习， 收获比较大， 尤其是排序算法那一节。
对于copy算法， 没有什么好多说的， 更多的是一些技巧上的应用， 如function overloading, type traits, and partial specialization。 其中要注意的是两个case，
第一， 输出区的终点与输入区重合。 在这一情况下， 不用担心， 该函数保证了copy结果的正确。
第二， 输出区的起点与输入区重合。 在这一情况下， 就需要十分的注意了， 因为， 输出的结果不一定正确。 因为， 输入区间的元素可能会在没有copy前被重写， 而如果copy算法根据其所收到的iterator调用memmove的话， 将没有这样的问题。
书中， 用来deque的例子来说明。
关于排序， SGI STL 中的几个函数都非常好， 在我眼里， 要比CLRS中相关的算法， 表达的更清楚， 逻辑性跟强。 不过，如果要把STL 中相关的算法提取出来， 相应的工作还是要做的， 否则， 错误将满天飞。 把自己改的代码贴一下（quicksort算法）， 做为记录。
1 int* partition(int* first, int* last, int pivot);
2
3 void my_qsort(int* first, int* last) {
4
5 int* q;
6
7 if ( last - first > 0 ) {
8
9 q = partition(first, last, *first);
10 my_qsort(first, q);
11 my_qsort(q+1, last);
12 }
13 }
14
15
16 int* partition(int* first, int* last, int pivot) {
17
18 int tmp;
19 int* old = first;
20
21 while (1) {
22
23 first++;
24 while ( *first < pivot ) {
25 first++;
26 }
27
28 last--;
29 while ( pivot < *last ) {
30 last--;
31 }
32
33 if ( !(first < last) ) {
34 *old = *last;
35 *last = pivot;
36 return last;
37 }
38
39 tmp = *first;
40 *first = *last;
41 *last = tmp;
42 }
43 }
10:06:11 AM Monday, May 18, 2009