C++实践模拟（stack，queue & priority_queue，仿函数）

stack和queue的实现，不同于vector和list那般复杂，如果你经历过vector和list的洗礼，那么当你看到stack和queue的大致实现时，你可能会惊叹，怎么能这么简洁。其原因有很多方面的，比如stack和queue不需要实现迭代器，这就帮我们省了很大的力气，stack和queue所支持的成员函数就那么几个，但最主要的原因是stack和queue使用了适配器设计模式，通过调用接口，非常方便的实现我们想要的功能，提高代码的复用率

什么是适配器

适配器是C++stl标准库的六大件之一，stl库中的六大件分别是

1.容器（container)

2.迭代器（iterator）

3.适配器（adapter）

4.算法（algorithm）

5.空间配置器（allocator）

6.仿函数（functor）

当然，这里我们不会将这些内容讲完，也不可能讲完，如果对上面六大件感兴趣，可以阅读侯捷老师编写的《stl源码剖析》。我们这里挑一些本节的重点简单叙述一下，首先是容器，容器就是我们实现的各种数据结构，vector，list，stack，queue等。接着是迭代器，迭代器给我们提供了一种统一的形式去访问容器内的数据，且不会暴露这些容器底层的实现细节，迭代器同时是算法和容器之间的胶合剂，使得各种容器都能够使用编写好的标准算法程序，而不需要针对某个特定容器去编写特定的算法程序，造成代码的大量冗余。大家能够明白其作用和使用方法就差不多了，如果想系统性厘清这些概念，自行查阅专业书籍。

接下来就是我们本节的主角，适配器。适配器并不是特定的一段程序，而是一种设计模式，这种该种模式是将一个类的接口转换成我们希望的另外一个接口。以日常生活为例

现在我们的手机为了追求轻薄，估计都不配给3mm耳机插孔了，但是很多的耳机的接头是3mm的，怎么办，难道我们就要把大贵价钱买的耳机给扔了吗？这样显然是极大的浪费，那么我们该怎么解决呢？既然手机厂商不配耳机接口，那总得有充电接口吧，我们可以设计一种转接接口，这个转接口，一头可以插入3mm耳机接口，另一头可以插入到充电接口，这样通过转接口，我们的耳机就能够连接到手机上了

上面转接口的设计其实就体现出了适配器的设计思想，手机想要和耳机建立连接，但是手机的接口是充电接口，这不是我们想要的，我们想要的是3mm耳机接口，于是我们基于手机的充电接口，自己设计一种接口，满足我们的需求，那么这种设计模式就是适配器

说到这大家是不是对适配器的作用有点模糊的概念了呢？这就够了，适配器是一种设计模式，设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总

结。因此我们不要企图一下子就把适配器给玩明白了，那是不太可能的，起初我们只需要大概了解这种设计思想，后面再通过各种项目的设计去深入了解，本篇文章以stack和queue的设计为例，让大家感受适配器的作用

了解deque

deque是什么东西呢？其实和我们使用的vector，list，string类似，就是一种容器了。不过这种容器可不得了，为什么不得了呢？因为能逼笔者这个能不写就不累着的人写出来，当然不得了了，哈哈哈，不开玩笑了

回想一下，我们刚开始学习数据结构的时候，那个时候模拟实现stack和queue，我们使用的是数组和链表来实现的，但是各有优缺点，使用数组来实现stack的话，在复杂度的效果上还可以，因为插入和删除的复杂度都是O(1)，但是开辟数组空间是不精准的，可能会造成极大的内存空间的浪费。数组实现queue效果就不理想了，因为queue要求的是头删，使用数组的话，头删就要依次把数据向前挪动，复杂度是O(n)，我们可以使用双指针实现循环队列来解决复杂度的问题，但又导致了空间不能扩充的问题。

再来看看链表，用链表来实现stack倒是解决了空间开辟不精准的问题，每push一个元素就增加一个节点，不会造成内存空间的极大浪费，但是，stack的插入和删除都是在尾部进行，那么每次插入和删除，链表都要遍历到尾部，这个时间复杂度就是O(n)了，用链表来实现queue呢？因为queue是尾插头删，在删除时，不需要遍历链表，时间复杂度能够控制在O(1)，在每个节点中加入一个尾指针，也能将插入的时间复杂度降至O(1)，但是因为其空间是不连续的，会导致堆空间的碎片化，以及CPU的缓存命中率低，访问效率低

可见，在C语言中无论是用链表还是用数组去实现stack和queue或多或少都有一些缺点，那么在C++中有没有一种容器，能够克服用vector或list（这里我们就简单将数组和链表等同于vector和list了）来实现stack和queue的缺点呢？

还真有，这个容器就是deque，我们简单了解一下deque的大致组成，为什么它就能克服list和vector带来的一些缺点呢？

提醒一下：deque的设计是比较复杂的，如果不想看是不影响后序内容的，只需要知道deque在实现stack和queue容器时，插入删除以及对成员访问等操作是vector和list优点的结合就可以了。

了解deque的底层实现

接下来咱们看看deque的底层的实现机制，deque的实现是比较复杂的，所以接下来咱们将整个过程简化一下。deque中的元素是存放在数组中的，但是这个数组不是完全连续的，随着元素的不断增多，由多段不连续的数组共同组成，然后再通过设计，造成是在同一个数组中的假象。我们称其中任一个数组为buffer数组，也就说数据是存放在buffer数组中的，这些buffer数组统一由一个指针数组来管理，这个指针数组叫中控数组，在创建deque时首先会开辟一个指针数组，也就是中控数组

是不是稍稍有些懵，看来概念今天依然发挥稳点，接下来通过不断插入元素的例子，大概讲讲deque的构建过程

我们要创建一个deque，那么首先会开辟中控数组，如下图

好的，现在开始，我们要插入元素了，为了方便，这里我们就规定，一个buffer数组中只能存放三个元素，真正实现肯定不是这样哈，这里只是为了方便演示。我们就尾插元素10和11 ，那么就会创建一个buffer数组，用来存放10和11，为了方便，我们就叫这个buffer数组为buffer_1，这里就要注意了，buffer_1被中控数组的中间元素指向，可不是被中控数组的第一个元素指向

好的，接下来，我们接着尾插元素12和13，那么此时，buffer_1只能放得下12了，所以我们要再开辟一个数组buffer_2

好的，没什么毛病，接着，我们不再尾插了，而是改为头插，我们要头插元素9和8，如果是普通数组，此时是不是已经头疼了， 因为头插意味着10 11 12 13都要向后挪动两位，但是这是deque

那么deque是如何操作的呢？首先会开辟buffer_3，然后元素会依次从后往前在buffer数组中插入  

这样基本就把deque的工作原理给讲的差不多了，接着头插或者尾插元素，都是在重复上述过程，大家自己推算一下就行了，接下来我们要分析一下deque的优缺点

优点： deque的优点就是避免了一般数组头插头删元素的难题，一般数组头插或头删元素时都会将已有的元素向后或者向前挪动，但这样的代价就比较大了，而deque能够将头插头删元素的时间复杂度降至O(1)

相比于链表，deque能够做到像数组一样随机访问元素，同时也解决了普通链表尾插元素要遍历整个链表的痛点

缺点： 先看看deque是如何实现随机访问元素的，就拿我们上图中的deque举例，我们要访问上图中的第五个元素，也就是下标为4的元素，那么此时，deque底层算法就会根据下标来判断要找的这个元素在哪个buffer数组中？如果找到了，那么还要计算在该buffer数组中的具体位置，最后返回结果

我们上面假设的是一个buffer数组中只能存放3个元素，于是我们要将要找的元素的下标值除以3，那么4/3，商就是1，说明该元素在中控数组下标为1的buffer数组中（这个下标为1是相对中控数组中已存在的位置来衡量的，deque底层有自己的算法来控制，我们不需要操心，如果感兴趣可以去查具体的底层实现细节），接着将该元素对3取模，那么4%3，结果就是1，说明该元素在已指定的buffer数组下标为1的位置，我们看这个元素是11，那么对于真个deque来说，下标为4的元素确实是11

这个过程由deque的迭代器来维护，相比于vector，deque的迭代器的设计就要复杂的多，我们看看deque迭代器的设计图

deque的底层由两个迭代器来维护，分别是起始迭代器start，和末尾迭代器finish

迭代器分别指向中控数组中第一个元素（相对已存在的元素），接着再分别指向这个buffer数组起始位置，末尾位置以及当前位置，起始和末尾很容易理解，就是buffer数组中起始和末尾位置，当前位置就是指这个buffer数组中已插入元素的下一个位置，尾插就用finish迭代器，头插就用start迭代器

如此以来，我们可以发现deque想要做到随机访问，中间还是要经过几层计算的，这相比于vector整个数组的随机访问，效率是要慢那么一些的， 也就是说随机访问不如vector做得极致。

其次，相比于list，大家应该也发现了其中的比较大的问题，deque是解决了头插头删，尾插尾删效率低的问题，但是没有解决往中间插入元素的难题，如果往中间插入元素，那么deque仍然会像数组那样挪动，效率也是O(n)，可见在中间插入元素这方面，效率是比不上list的，不到list极致

deque看着样样在行，但都不够极致，这也就导致了deque实际的运用场景并不多，但是对于stack和queue来说，这简直就是量身定做的呀，我stack和queue又不需要随机访问，并且不需要中间位置插入元素，完美避开了deque的缺点

用容器deque实现stack和queue

终于，完成了对适配器和deque的了解，接下来，就将两者结合起来，来实现stack和deque，经过上面的了解，我们都知道了stack和queue是由deque来实现的，我们可以先查阅一下deque的设计接口

这不对劲呀，stack和queue的接口只需要push和pop，你这deque整出来push_back，push_front，这接口不是stack和queue想要的， 但是我要实现的功能又要基于你提供的接口，怎么办？这个时候就是适配器出场了，还记得我们手机和耳机那个例子吗？既然你的接口我不想要，那么我们就基于你的接口，自己重新设计一个接口，设计过程也是相当简单，就没有什么叙述的必要了，接下来，我们具体代码留下，大家自行阅读

                              /* stack_define.h */
#include<deque>
#include<iostream>
#include<vector>
using namespace std;
namespace my_stack {
  template<class T, class Container = deque<T>>
  class stack {
  public: 
    /*member function*/
    T& top(){
            if(_con.size() > 0)
         return _con[_con.size()-1];
    }
    void push(const T& val){  
      _con.push_back(val);
    }
    void pop(){ 
      _con.pop_back();
    }
    bool empty(){     
      return _con.empty();
    }
    void swap(stack& x){
      _con.swap(x._con);
    }
    size_t size() {
      return _con.size();
    }
  private:
    Container _con;
  };
}

这里提一嘴，我们可以不用为stack和queue设计构造和析构函数，因为是基于deque设计的，编译器会自动调用deque的构造和析构函数，如果想实现某些特殊功能，那就自便了

                                /* queue_define.h  */
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
namespace my_queue {
  template<class T, class Container = deque<T>>
  class queue {
  public:
    T& front(){
      return _con.front();
    }
    T& back() {
      return _con.back();
    }
    void pop() {    
      _con.pop_front();
    }
    void push(const T& val) {
      _con.push_back(val);
    }
    bool empty() {
      return _con.empty();
    }
    size_t size() {
      return _con.size();
    }
  private:
    Container _con;
  };
}

priority_queue的实现

priority_queue，即优先级队列，优先队列根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的

priority_queue默认存储数据的容器用的是vector，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此可以将priority_queue看成是堆，所有需要用到堆的位置，都可以考虑使用priority_queue  注意：默认情况下priority_queue是大堆。

因为priority_queue是在vector基础上，对堆的算法接口make_heap、push_heap和pop_heap等进行封装，实现新的接口模式，可见priority_queue也是适配器模式。至于如何实现堆，可在笔者数据结构二叉树那篇博客中查阅，这里就不赘述了，下面是实现代码，需要注意的是，我的代码不是直接调用c++提供的堆的算法接口，而是直接实现了一遍堆，所以并没有体现出对接口进行封装这一过程，主要是方便忘记堆算法的同学及时复习

#include<vector>
#include<iostream>
using namespace std;
namespace my_priority_queue {
  template<class T>
  class less {
  public:
    bool operator()(const T& value_1, const T& value_2) {
      return value_1 < value_2;
    }
  };
  template<class T>
  class greater {
  public:
    bool operator()(const T& value_1, const T& value_2) {
      return value_1 > value_2;
    }
  };
  template<class T, class Sequence = vector<T>, class Compare = less<T>>
  class Priority_queue {
  public:
    Priority_queue() {}
    template<class Iterator>
    Priority_queue(Iterator begin, Iterator end)
      :_con(begin, end)
    {
      for (int i = (_con.size() - 1 - 1) / 2; i > 0; i++) {
        adjust_up(i);
      }
    }
    void adjust_up(size_t child) {
      size_t parent = (_con.size() - 1 - 1) / 2;
      Compare com;
      while (child > 0) {
        if (com(_con[parent], _con[child])) {
          swap(_con[child], _con[parent]);
          child = parent;
          parent = (parent - 1) / 2;
        }
        else {
          break;
        }
      }
    }
    void push(const T& value) {
      _con.push_back(value);        
      adjust_up(_con.size()-1); //向上调整建堆
    }
    void adjust_down(size_t parent = 0) {
      size_t child = 2 * parent + 1;
      Compare com;
      while (child < _con.size()) {
        if (child + 1 < _con.size() && com(_con[child], _con[child+1])) {
          child++;
        }
        if (com(_con[parent], _con[child])) {
          swap(_con[child], _con[parent]);
          parent = child;
          child = 2 * parent + 1;
        }
        else {
          break;
        }
      }
    }
    void pop() {
      swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down();//向下调整建堆
    }
    const T& top()const {
      return _con[0];
    }
    size_t size() {
      return _con.size();
    }
    bool empty() {
      return _con.empty();
    }
  private:
    Sequence _con;
  };
}

大家可能会疑惑，对上面代码的一些部分不理解，比如class less 和 class greater是什么？为什么这两个类中只重载了一个（），如果你因此而看不懂上面代码，那么就看完下面的内容，然后回过头来再阅读一遍应该就明了了

仿函数

什么是仿函数？为什么要有仿函数呢？要回答这个问题，我们就要从C语言中的函数指针来讲起，函数指针是个好东西，能够高效弹性的调用函数，但是缺点也是很明显，那就是函数指针的定义非常的复杂，如果函数的参数在多点，那更是痛不欲生

int add(int x, int y) {
  return x + y;
}
int main() {
    //函数名就是函数地址，这里在赋值时，用add或者&add都是可以的
  int (*p)(int, int) = &add;
    //同理，这里对函数的引用，加不加解引用符号都一样
  cout << p(1, 3) << endl;
  cout << (*p)(1, 3) << endl;
  return 0;
}

接下来，我们把场景切换到冒泡排序中

void bubble(int* arr, int size) {
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int arr[] = { 7,3,9,6,5,2,8,1 };
  bubble(arr, sizeof(arr) / sizeof(arr[0]));
  for (auto e : arr) {
    cout << e << " ";
  }
  return 0;
}

在这个过程中，默认排升序，但是此时提高要求，不一定要排升序，可能要升序也可能要降序，那我们的解决办法就是加一个函数，用函数来控制到底排升序还是降序，我们一般会写一个com函数，然后把com函数作为参数给冒泡排序传递过去

bool com(int x, int y) {
  if (x > y)
    return true;
  else
    return false;
}
void bubble(int* arr, int size, bool(*com)(int, int)) {
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1 - i; j++) {
      if (com(arr[j],arr[j+1])) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int arr[] = { 7,3,9,6,5,2,8,1 };
  bubble(arr, sizeof(arr) / sizeof(arr[0]), com);
  for (auto e : arr) {
    cout << e << " ";
  }
  return 0;
}

可见，传递函数指针还是挺复杂的，而且com函数还只是传递两个参数，如果参数再多点，那就相当的复杂了，仿函数就是为了解决这个痛点而生的，那么仿函数是如何做的呢？

仿函数其实是一个类，这个类中只重载运算符 "()" ，也就是我们平时调用函数用到的  "()"，这意味着如果实例化一个该类的对象，那么这个对象就能够当函数来使用

struct com {
  bool operator()(int x, int y) {   
    if (x > y)
      return true;
    else
      return false;
  }
};
int main() {
  com test;
  cout << test(1, 2) << endl; //等价于 test.operator()(1, 2)
  //也就是说我们完全可以把这个类当成函数来使用
  return 0;
}

这有什么用呢？接着看，我们把这个仿函数用到刚才的冒泡排序中

struct com {
  bool operator()(int x, int y) {
    if (x > y)
      return true;
    else
      return false;
  }
};
template<class function = com>
void bubble(int* arr, int size, function test) {
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1 - i; j++) {
      if (test(arr[j],arr[j+1])) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  com test;
  int arr[] = { 7,3,9,6,5,2,8,1 };
  bubble(arr, sizeof(arr) / sizeof(arr[0]), test);
  for (auto e : arr) {
    cout << e << " ";
  }
  return 0;
}

怎么样，我们利用模板将com类作为参数传给冒泡函数，然后使用com类的"()"重载其实就是在调用com函数，在这个过程中，我们终于摆脱了函数指针那非常复杂的写法

其实这只是仿函数其中一个用途，仿函数的用处还是不少了，后面我们会逐渐发掘，现在回过头，你应该就能懂priority_queue中的class less 和 class greater是什么意思了吧？其实就是两个仿函数，分别用来控制是建大堆还是建小堆