stack_queue：三个关键注意事项解析

一、stack与容器

template<class T, class Container>
class stack
{
private:
    Container _con;
};

Container 为容器，在实例化创建对象时，我们可以传 vector<T> 或 list<T> 等作为栈的底层。

举例：

int main()
{
  stack<int, vector<int>> st1;
  stack<int, list<int>> st2;

  return 0;
}

二、queue 和 priority_queue 的底层封装

• queue 不支持用 vector 封装

queue 的原则是先进先出，使用过程中存在大量“头删”——pop_front()，用 vector 进行封装效率太低，故通常借助 list 进行模拟实现。

• priority_queue 不支持用 list 封装

queue 的原则是先进先出，使用过程中存在大量“头删”——pop_front()，用 vector 进行封装效率太低，故通常借助 list 进行模拟实现。

• priority_queue 不支持用 list 封装

优先队列 priority_queue 的本质是“堆”（默认建大堆），在插入和删除时，通常会涉及向上调整建堆和向下调整建堆的方法——大量 [] 重载的使用。

list 不支持 [] 的重载，故 priority_queue 不支持底层使用 list。

三、仿函数

在C++中，仿函数通常是一个类或结构体，在类中通过重载 operator() 实现，其实例化对象可以像函数一样被调用。

less<T> 就是一个仿函数——从根往叶子节点看，数值/优先级 越来越小，因此默认为大堆；如果我们传 greater<T> —— 从根往叶子节点看，数值/优先级 越来大，则建小堆。

  template<class T>
  class less
  {
  public:
    bool operator()(const T& a, const T& b)
    {
      return a > b;
    }
  };

  template<class T>
  class greater
  {
  public:
    bool operator()(const T& a, const T& b)
    {
      return a < b;
    }
  };

因为要建大堆，当子节点的数值/优先级比父节点大时——_con[child] > _con[parent]，要将子节点向上调整。