C++ 利用容器适配器,仿函数实现栈,队列,优先级队列(堆),反向迭代器,deque的介绍与底层

C++ 利用容器适配器,仿函数实现栈,队列,优先级队列【堆】,反向迭代器,deque的介绍与底层

• 一.容器适配器的介绍
• 二.利用容器适配器实现栈和队列
• • 1.stack
  • 2.queue
  • 三.仿函数介绍
  • • 1.什么是仿函数
    • 2.仿函数的使用
    • 3.函数指针的使用
    • • 1.函数指针的用处
      • 2.利用函数指针完成回调
      • 3.利用仿函数完成回调
      • 4.仿函数的玩法
      • • 1.取出Key/Key-Value模型中的Key
        • 2.自定义排序
        • 四.利用容器适配器和仿函数实现优先级队列
        • 五.利用正向迭代器作为适配器实现反向迭代器
        • • 1.STL库里面的实现逻辑
          • • 1.rbegin和rend的实现
            • 2.反向迭代器的实现
            • 3.画图模拟反向迭代器具体的遍历流程
            • • 1.vector
              • 2.list
              • 4.具体实现
              • 5.对于list的适用
              • 6.对于vector的适用
              • 7.const_reverse_iterator的实现
              • 8.验证
              • • 1.list
                • 2.vector
                • 六.deque的介绍
                • 七.deque的底层原理

                  一.容器适配器的介绍

                  适配器是一种设计模式(所谓的设计模式就是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结,是很多大佬的编程的过程中总结下来的经验,类似于"武林秘籍"),

                  该种模式是将一个类的接口转换成客户希望的另外一个接口。

                  我们来看一下STL库中stack的源码,了解一下容器适配器模式到底是什么

                  

                  下面就让我们借助容器适配器来实现一下栈和队列吧

                  实现之后大家就会对容器适配器模式有更加深刻的理解

                  二.利用容器适配器实现栈和队列

                  1.stack

                  #pragma once
                  //容器适配器:vector可以,list可以,deque也可以,库里面默认使用deque
                  namespace wzs
                  {
                      template
                      class stack
                      {
                      public:
                          //直接使用编译器默认生成的默认成员函数即可
                          void push(const T& x)
                          {
                              _con.push_back(x);
                          }
                          void pop()
                          {
                              _con.pop_back();
                          }
                          T& top()
                          {
                              return _con.back();
                          }
                          const T& top()const
                          {
                              return _con.back();
                          }
                          size_t size()const
                          {
                              return _con.size();
                          }
                          bool empty()const
                          {
                              return _con.empty();
                          }
                      private:
                          Container _con;
                      };
                  }
                  

                  可见,非常的easy

                  就是容器的复用而已

                  对于stack而言

                  它的适配器必须满足:

                  push_back,pop_back,back,size,empty这几个接口

                  因此stack的适配器可以是

                  vector

                  list

                  deque中的任何一个

                  

                  验证完毕

                  2.queue

                  #pragma once
                  //容器适配器:list可以,deque也可以,库里面是deque,不过vector不可以,因为vector没有头删这个接口
                  namespace wzs
                  {
                      template
                      class queue
                      {
                      public:
                          //使用编译器默认生成的默认成员函数即可
                          void push(const T& x)
                          {
                              _con.push_back(x);
                          }
                          void pop()
                          {
                              _con.pop_front();
                          }
                          T& back()
                          {
                              return _con.back();
                          }
                          const T& back()const
                          {
                              return _con.back();
                          }
                          T& front()
                          {
                              return _con.front();
                          }
                          const T& front()const
                          {
                              return _con.front();
                          }
                          size_t size()const
                          {
                              return _con.size();
                          }
                          bool empty()const
                          {
                              return _con.empty();
                          }
                      private:
                          Container _con;
                      };
                  }
                  

                  可见,非常的easy

                  就是容器的复用而已

                  对于queue而言

                  它的适配器必须满足:

                  push_back,pop_front,back,front,size,empty这几个接口

                  因此stack的适配器可以是

                  list

                  deque中的任何一个

                  而vector因为没有pop_front这个接口,因此不能作为queue的适配器

                  

                  验证完毕

                  三.仿函数介绍

                  1.什么是仿函数

                  仿函数,又叫做函数对象,它是一个类

                  只不过这个类重载了operator()这个运算符,使得这个类实例化出的对象在调用operator()这个函数时使用起来特别像一个函数,

                  也就是说这个类实例化出的对象能够像函数一样调用,因此这个类被称为仿函数

                  下面给大家演示一下

                  这是比较两个T类型的大小

                  

                  只要一个类重载了operator(),这个类就是一个仿函数类

                  这个类实例化出的对象就能像函数一样进行调用

                  2.仿函数的使用

                  算法库里面的sort函数就使用了仿函数

                  

                  默认情况下sort是排升序的

                  如果我们想要排降序呢?

                  就要用到仿函数了

                  我们来演示一下,顺便学习一下仿函数的语法和特性

                  默认排升序

                  

                  排降序

                  

                  sort的第三个参数要求传入仿函数对象,所以可以这样做

                  

                  其实我们也可以自己实现一个仿函数

                  一般来说仿函数写出来就是为了给外界用的,所以定义成class的话要加public访问限定符调整成公有成员

                  不过也可以直接用struct定义这个类,毕竟struct定义的类的访问限定符默认就是public

                  template
                  struct greater
                  {
                      bool operator()(const T& a, const T& b)
                      {
                          return a > b;
                      }
                  };
                  

                  

                  其实也可以直接传匿名对象,省下起名字了

                  

                  3.函数指针的使用

                  1.函数指针的用处

                  可见仿函数是非常多功能的,那么它的用处是什么呢?

                  为什么C++创始人要设计仿函数这一语法呢?

                  仿函数是为了替代C语言当中的函数指针而出现的

                  我们知道函数指针是用来完成回调的,例如C语言库中的qsort函数

                  关于回调函数大家可以看我的这篇博客:征服C语言指针系列(3)

                  

                  这里的比较规则就是由cmp这个函数指针来完成的

                  在学习堆的时候,我们曾经借助于函数指针来完成回调函数,实现无需修改具体函数的实现细节来完成大小堆的切换

                  数据结构-堆的实现及应用(堆排序和TOP-K问题)

                  

                  2.利用函数指针完成回调

                  下面我们来演示一下使用函数指针完成回调

                  //返回a是否小于b
                  bool less1(int a, int b)
                  {
                  	return a