关于为什么突然想写一个模板类？ 嗯。。主要是因为最近在翻看《STL源码剖析》，然后发现原来STL源码是如此的庞大且复杂，而又及其具有条理，而其中最难的就是各个组件的关系，而对外所展现的效果就是泛型编程，对我这个初入门菜鸟来说的话，我之前对模板仅仅停留在知道，但没用过的阶段🤣 由于STL库中对模板的骚操作一个接一个，没个模板的基础，根本就看不懂，所以我痛定思痛，一定要亲手用模板实现一个数据结构(之前用非模板实现过一些)。 好了，目标有了，用模板实现一个数据结构，那数据结构这么多，我到底实现哪个呢？要不就把堆给冲了？我一拍大腿，可行！👍 最后关于它的具体实现，我肯定不会像STL那样考虑的那么周到，组件分工齐全，毕竟STL是包含六大组件的！ 具体如下图： 对刚用模板的C++新手而言的几大坑点习惯性写.h和.cpp文件 对于对C++有一定掌握，但基本没用过模板的人而言，声明与定义早就烂熟于心的.h和.cpp文件。然而，当你使用模板的时候，再去吧声明和定义分开，将会产生一个错误！除非在.h文件末尾有包含.cpp文件。然而这样的操作是很多余的！ 所以在用模板实现类的时候，最好只写一个.h文件！对模板特化运用和理解很少我现在就处于这个状态，说不上来该怎么规范🤣我的Heap实现总览Heap类 这是我画的树状图，我设计的Heap一共分为以下三个部分：一、 成员变量 这部分没啥好说的，就用一个 nums 指针存储变量数据，length 记录当前的 nums 已经使用的长度，capacity 存储当前 nums 的最大容量。二、 静态成员函数 我将堆的基本操作封装为静态成员变量的初衷是方便，对外实现堆化的功能，即使使用外部数组也能实现堆。 下面简单的介绍一下这几个函数（后面再详解）：sift_down()：接受四个参数，依次是用于向下堆化的数组，起始的堆化位置，结束的堆化位置，以及一个仿函数(用于设定最大/最小堆)。static void sift_down(T &nums, size_t start, size_t len, _CMP cmp); sift_up()：向上堆化的操作，与上面的类似，少了结束信息，因为结束信息一般都是0.static void sift_up(T &nums, size_t start, _CMP cmp); heapify()：调用向下堆化函数，实现完全堆化，接收两个参数，待堆化数组和数组长度 static void heapify(T &nums, size_t len); print()：主要实现一个用于测试功能的泛型打印接口，接收的参数肯定就是数组和数组长度了。(略过，不重要)三、类的内部成员函数(放源代码详解)构造和析构函数：很简单的，我直接放源代码出来。Heap() : length(0), capacity(1) {//暂时没有对构造函数拓展的打算 nums = new _T[capacity]; } ~Heap(){ delete []nums; } push()：每次入队后进行一次向上堆化，这个简单，直接调上面的静态接口就行了。注意：我这里采用的是倍增的方式进行延伸内存，一旦出现capacity不够用的情况，就重新分配内存，其中数据拷贝方面用了copy函数。void push(_T val) { if (length >= capacity) {//两倍两倍的扩容 _T *t = nums; capacity *= 2; nums = new _T[capacity]; std::copy(t, t + length, nums); delete[] t; } nums[length] = val; sift_up(nums, length, _CMP()); length++; } pop()：这个操作是需要一点技巧的--为了不破坏整体堆化的结构，我们直接把根部与尾部元素进行交换，再从根部往下重新堆化一次(注意此时堆化的终点应该要比原来小1)。 还采取了C语言的断言方式，防止pop操作的时候，堆中已经没有元素。void pop() { if (length == 0) assert(0); length--; std::swap(nums[0], nums[length]);//实际上pop操作就相当于堆排的一次过程 sift_down(nums, 0, length, _CMP()); } top()：直接取根节点的值。_T top() { if (length == 0) assert(0); return nums[0]; } print()：用于打印内部数据的接口。void print() {//内部print方便测试 print(nums, length);//调用静态print } 关…