stack,queue,priority_queue学习知识点

容器适配器

在c++常用的容器中，有的是以容器迭代器为核心，而有的则以容器适配器为核心。较为常用的就包括queue和stack。接下来我将简单的以queue和stack的模拟实现介绍其特点。

在以下的模拟实现中，class Con就是我们的容器适配器，他用于传一个容器，默认为deque类模版，deque模版是一种奇妙的模版，他在头部插入和删除时，效率很高，扩容效率也高，但是其不适合遍历。当我们想要实现某个类，而刚好这个类可以用其他类的功能来直接实现，那么我们就可以将这个类用另一个类包装起来。

    template<class T, class Con = deque<T>>class stack{public :stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:Con _c;};template<class T, class Con = deque<T>>class queue{public:queue(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
}

仿函数

在学习priority_queue的时候，我们可以注意到他其中有一个参数是class Compare = std::less，那么，这个std::less是什么呢？经过查看，我们可以知道他是一个类，他内部包含了一个operator()，对()进行了一次运算符重载。再认真看priority_queue中Compare出现的地方，我们可以发现，他广泛的用于比较的地方。为何要如此定义？因为priority_queue本质上就是一个堆，后面的Comepare本质上就是决定他要建大堆还是小堆。而且在这还有一个反过来的地方，那就是如果你选的是less，那么他建的是大堆，即最大值在堆顶，这是和我们日常直觉不同的。

    template <class T>struct less{bool operator()(const T& left,const T& right){return left < right;}};template <class T>struct greater{bool operator()(const T& left, const T& right){return left > right;}};

接着让我们看看在具体代码中他的代码，第一句是他的一句代码，第二句是他的一个参数，comp是一个Compare类型的类对象。在第一句代码中我们直接用comp包住两个数据，这两个数据分别会被带入comp()符号的运算符重载的左右参数。因此就会直接返回仿函数的结果。

if (child + 1 < c.size() && comp(c[child], c[child + 1]))Compare comp;

 

仿函数