C++基础代码20余种数据结构和算法的实现

过年了，闲来无事，翻阅起以前写的代码，无意间找到了大学时写的一套C++工具集，主要是关于数据结构和算法、以及语言层面的工具类。过去好几年了，现在几乎已经回忆不起当年写代码时的情况，不过，通过文件头部注释里的日期，还是依稀想起了那些日子发生的一些事情，不禁感慨了一番。感概之余，随便翻阅了一下，发现当年的编程手法和现在相比，略显稚嫩，风格也相差的比较大了，明显受到当时读的一些经典C++书籍的影响。不过好在代码质量都算可以，都属于基础的语言层面以及数据结构的代码，操作指针比较小心，每个类也都有测试的样例，感觉对初学者应该会有用，于是拿到这里放出来，希望能对准备学习和正在学习C++语言编程的朋友有所裨益。

做了个表，看一下这个工具集里都有哪些C++类

　　基本上可以分为两大类，一种是关于数据结构和算法的（例如：RBtree，stack），另一种是关于C++语言本身层面的（例如：reference_count，Uncopyable）。这些类，可以在如今C++标准库或者其它C++库（如：boost）中找到类似的实现，实现它们的目的不是想自己造轮子，而是通过实现，来深入的理解到一些更本质的东西。很多时候，人们往往“知其然，不知其所以然”，当然，世界这么大，什么事情都想要“知其所以然”是不可能、也是不应该的，但是对于初学者而言，了解C++中常用的编程手法的本质，“知其所以然”，还是很必要的。

　　如果想在自己的项目中使用这些代码，有的地方还是需要注意和考虑一下的，比如Auto_ptr，它的原理仿照std::auto_ptr，当然，现在已经不推荐使用了，更应该使用std::unique_ptr或std::shared_ptr，而Uncopyable也可以通过更为方便的宏定义来实现，只需要在类定义private域中加入该宏即可。

1 #define DISABLE_COPY_AND_ASSIGN(type_name) \
2     type_name(const type_name&); \
3     type_name& operator=(const type_name&)

复制代码

　　这里我把其中的两个基础算法——sorting中的“插入排序”和“快速排序”贴出来，估计一些要参加笔试和面试的朋友可能会感兴趣。

 1 //-------------insertion sort-------------------------
 2 template<typename T>
 3 void insertion_sort(T a[], int n)
 4 {
 5     T tm;
 6     for (int i=0; i!=n; ++i) {
 7         tm = a[i];
 8         int k=i;
 9         for (; k>0; --k) {
10             if (tm >= a[k-1])
11                 break;
12             a[k] = a[k-1];
13         }
14         a[k] = tm;
15     }
16 }
17 //---------------------------------------------------

复制代码

 1 //------------------quick sort----------------------
 2 template<typename T>
 3 T median(T a[], int left, int right)
 4 {
 5     int center = (left + right) / 2;
 6     T tm;
 7     if (a[left] > a[center]) {
 8         tm = a[left];
 9         a[left] = a[center];
10         a[center] = tm;
11      }
12     if (a[left] > a[right]) {
13         tm = a[left];
14         a[left] = a[right];
15         a[right] = tm;
16     }
17     if (a[center] > a[right]) {
18         tm = a[center];
19         a[center] = a[right];
20         a[right] = tm;
21     }
22 
23     tm = a[center];
24     a[center] = a[right-1];
25     a[right-1] = tm;
26 
27     return a[right-1];
28 }
29 
30 template<typename T>
31 void q_sort(T a[], int left, int right)
32 {
33     // 如果剩余未排序的数组长度太小，使用插入排序算法进行剩余数组的排序
34     if (left+4 <= right) {
35         T pivot = median(a,left,right);
36         int i = left;
37         int j = right - 1;
38         while (true) {
39             while (a[++i] < a[pivot]);
40             while (a[--j] > a[pivot]);
41             if (i < j) {
42                 T tm = a[i];
43                 a[i] = a[j];
44                 a[j] = tm;
45             }
46             else
47                 break;
48         }//while
49         T tm = a[i];
50         a[i] = a[right-1];
51         a[right-1] = tm;
52 
53         q_sort(a,left,i-1);
54         q_sort(a,i+1,right);
55     }
56     else
57         insertion_sort(a+left,right-left+1);
58 }
59 
60 template<typename T>
61 void quicksort(T a[], int n)
62 {
63     q_sort(a,0,n-1);
64 }
65 //--------------------------------------------------