C++完整的范例: heapsort

　　Container简介请参考 heap1.cc范例程序并复习四个与memory allocation有关的特殊成员函数.

　　像vector, list, double ended queue, ...等等这类数据结构称为containers (容器?),专门用来把很多homogeneous (同质的)小数据结构(称之为element元素 )收集在一起.不同的containers用途在于提供给用户不同的存取元素方法,或针对不同的运算提升效率.

　　heap 数据结构: 有兴趣的读者请详阅数据结构书籍; 没有兴趣的读者可以忽略成员函数实作(演算法) 部分.

　　heap 是一种container, 方便用户随时加入新的元素, 及取出最小的元素. 适合用于处理"排队" 的场合, 但是其中参与排队的元素未必是先到先赢, 而是根据它的"优先顺序" (priority) 来决定.

　　储存规则: 把数组当做complete binary tree 来存放元素, 最小(优先顺序最高) 的元素放在第1 格(树根), 左右两棵子树的元素都比树根大, 但彼此之间没有关系.以下类顶. 第0 格不使用.

　　新增: 把新元素放在最后, 再往上浮; 删除: 把树根拔走, 最后一个元素移到树根, 再往下沉.

　　可用来排序. 所产生的排序法叫做heap sort, 排序时间保证在O(n log(n)) 之内.

　　Iterator简介请参考 heap2.cc

　　动机: 像vector, linked list, tree, ... 等等containers, 用户如何写程序"对里面的每个... 的元素做... 动作" ? 必须要有一个机制可以让用户把container 里面的所有元素逐一取出来看, 可是又不应该让用户操心container 实作的数据结构细节(例如tree 有letf pointer, right pointer, 甚至next pointer, parent pointer ...) 对于数组而言是很简单; 但是其他containers 呢?

　　常用的iterator 函数:

　　CONTAINER::iterator CONTAINER::begin() const;

　　指到某个container的"第一个"元素的"指针"

　　CONTAINER::iterator CONTAINER::end() const;

　　指到某个container的"比最后一个还要更后面"元素的"指针"

　　CONTAINER::iterator CONTAINER::iterator::operator++();

　　让指到某个container的某个元素的"指针"指到下一个元素

　　VALUE & CONTAINER::iterator::operator *();

　　取得某个"指针"所指到的元素(用以当做l-value或r-value)

　　Access Control简介(参考complex.cc )

　　public:区段为公开的接口,里面的成员可以供任何人使用; private: 区段为不公开的实作细节,只有implementor知道,也就是说,只有该类别本身的成员函数的作者可以使用private :区段的成员.

　　注意: access control 的目的不在保密或防止恶意写入(不够的!) 而在防止程序设计师的无心之失.

　　在一个类别C当中,把一个不属于C的函数f声明成 friend ,可以让f打破access control,使用到C的private区段部分的数据成员与成员函数.

　　在一个类别C当中,把另外一个类别F声明成 friend ,可以让F的所有成员函数打破access control,使用到C的private区段部分的数据成员与成员函数.

　　朋友关系未必满足对称律(即使F 是C 的朋友, C 也未必是F 的朋友), 也未必满足递移律(即使A 是B 的朋友, B 是C 的朋友, A 也未必是C 的朋友). 到底是谁对谁开诚布公? "我对朋友开诚布公".

　　类别中的类别(nested class):例如"台湾的国民党", "xx国的国民党"...连同外面的scope一起讲才算是完整的类别名称.作业:把 heap1.cc所有的成员函数定义成out-of-line functions.

　　作业: 试写出vector, list 与dequeue (double-ended queue) 等三个container 类别, 元素型别一律使用double 就好. 要把constructor, destructor, copy constructor, assignment operator 等实作出来. 要提供iterator .