C++语法·十伞

仿函数

1.定义

2.作用

3.实现

deque（双端队列）

优点：

缺点：

stack（栈）

1.使用

2.模拟实现

queue（队列）

1.使用

2.模拟实现

priority_queue（优先级队列）

介绍

使用

注意：

模拟实现

小知识

仿函数

1.定义

本质上是一个类，通过重载operator() ，使其对象可以像普通函数一样被调用。

2.作用

（1）提供比普通函数更加灵活的行为，仿函数可以携带状态

（2）支持动态行为。

（3）与STL算法紧密配合

3.实现

仿函数的实现较为简单，只需要在一个类中重载（）运算符即可，根据不同的场景有不同的实现，以下为一个例子：

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;
   }
};

deque（双端队列）

一种双开口的“连续”空间的数据结构，可以在头尾两段插入删除，且时间复杂度为O（1），“连续”指的是由一段段连续的小空间拼接而成，对于维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，所以迭代器设计较复杂。

优点：

1.与vector比较，deque的优势是头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

2.与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

缺点：

不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

stack（栈）

1.使用

stack() 构造空的栈
empty() 检测stack是否为空

size() 返回stack中元素的个数

top() 返回栈顶元素的引用

push() 将元素val压入stack中

pop() 将stack中尾部的元素弹出

2.模拟实现

#include <iostream>
#include <cstdbool>
#include <vector>

using namespace std;

namespace Stack
{
   template<class T>
   class stack
   {
       std::vector<T> _v;//这里使用了vector，标准库里使用的是deque
   public:
       stack()
       {}

       void push(const T& tmp)
       {
           _v.push_back(tmp);
       }

       void pop()
       {
           _v.pop_back();
       }

       T& top()
       {
           return _v.back();
       }

       const T& top() const
       {
           return _v.back();
       }

       size_t size() const
       {
           return _v.size();
       }

       bool empty() const
       {
           return _v.empty();
       }

   };
}

queue（队列）

1.使用

queue() 构造空的队列

empty() 检测队列是否为空，是返回true，否则返回false

size() 返回队列中有效元素的个数

front() 返回队头元素的引用

back() 返回队尾元素的引用

push() 在队尾将元素val入队列

pop() 将队头元素出队列

2.模拟实现

#include <iostream>
#include <cstdbool>
#include <list>

using namespace std;

namespace Queue
{
   template<class T>
   class queue
   {
       std::list<T> _l;//使用list实现,标准库使用deque实现
   public:
       queue()
       {}

       void push(const T& tmp)
       {
           _l.push_back(tmp);
       }

       void pop()
       {
           _l.pop_front();
       }

       T& back()
       {
           return _l.back();
       }

       const T& back() const
       {
           return _l.back();
       }

       T& front()
       {
           return _l.front();
       }

       const T& front() const
       {
           return _l.front();
       }

       size_t size() const
       {
           return _l.size();
       }

       bool empty() const
       {
           return _l.empty();
       }

   };

}

priority_queue（优先级队列）

介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空

size()：返回容器中有效元素个数

front()：返回容器中第一个元素的引用

push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

使用

priority_queue()/priority_queue(ﬁrst,last) 构造一个空的优先级队列
empty( ) 检测优先级队列是否为空，是返回true，否则返回false
top( ) 返回优先级队列中最大(最小元素)，即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素，即堆顶元素

注意：

1.默认情况下，priority_queue 是大堆

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重
载。

模拟实现

#include <iostream>
#include <cstdbool>
#include <vector>

using namespace std;

namespace Priority_queue
{
   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;
       }
   };

   template<class T,class container = std::vector<T>,class compare = less<T>>
   class priority_queue
   {
       container _c;
   public:
       priority_queue()
           :_c()
       {}

       template<class Iterator>
       priority_queue(Iterator first, Iterator last)
           :_c(first,last)
       {
           //建堆
           int root = (_c.size() - 2) / 2;
           for (; root >= 0; --root)
               Adjust_down(root);
       }

       void push(const T& tmp)
       {
           _c.push_back(tmp);
           Adjust_up(_c.size() - 1);
       }

       void pop()
       {
           if (!_c.empty())
               return;

           std::swap(_c.front(), _c.back());
           _c.pop_back();
           Adjust_down(0);
       }

       const T& top() const
       {
           return _c.front();
       }

       size_t size() const
       {
           return _c.size();
       }

       bool empty() const
       {
           return _c.empty();
       }

   private:
       void Adjust_up(int child)
       {
           int parent = (child - 1) / 2;

           while (child)
           {
               if (compare()(_c[child],_c[parent]))
               {
                   std::swap(_c[child], _c[parent]);
                   child = parent;
                   parent = (child - 1) / 2;
               }
               else
                   return;
           }
       }

       void Adjust_down(int parent)
       {
           size_t child = (parent << 1) + 1;

           while (child < _c.size())
           {
               if (child + 1 < _c.size() && compare()(_c[child + 1], _c[child]))
                   child += 1;

               if (compare()(_c[parent], _c[child]))
               {
                   std::swap(_c[parent], _c[child]);
                   parent = child;
                   child = parent * 2 + 1;
               }
               else
                   return;
           }
       }

   };

}