从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（上）-阿里云开发者社区

1. priority_queue的模拟实现

默认情况下的priority_queue是大堆，我们先不考虑用仿函数去实现兼容大堆小堆排列问题，

我们先实现大堆，把基本的功能实现好，带着讲解完仿函数后再去进行优化实现。

优先级队列相较于普通的队列，其区别主要是在 push 和 pop 上，

即需要在插入 / 删除数据的同时，增添调整的功能，其也是对适配器的封装，

push 和 pop 需要堆上调和下调操作，我们不可避免地需要实现堆上调和下调的算法。

我们这里暂时写死，设计成大堆的 adjust_up 和 adjust_down：

对堆调整算法不熟悉的可以看这里；

数据结构与算法⑪(第四章_中)堆的分步构建_GR C的博客-CSDN博客

1.1 未完全的priority_queue

入队时将数据插入后，从最后一个元素开始进行上调。

出队时采用堆的删除手法，将根元素（即队头）和最后一个元素进行交换，并调用尾删掉队头。

既然用了头尾交换法，我们就不得不对队列重新调整，所以从根位置进行下调，即可完成出队。

除了插入和删除，其它接口和queue差不多，PriorityQueue.h:

#pragma once
#include <iostream>
#include <vector> 
#include <algorithm>
#include <functional> // greater和less的头文件
using namespace std;
 
namespace rtx
{
  template<class T, class Container = vector<T>>
  class priority_queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
 
    void adjust_up(size_t child)
    {
      size_t father = (child - 1) / 2;
      while (child > 0)
      {
        if (_con[father] < _con[child])
        {
          swap(_con[father], _con[child]);
          child = father;// 交换后向上走
          father = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
 
    void pop()
    {
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
 
      adjust_down(0);
    }
 
    void adjust_down(size_t father)
    {
      size_t child = father * 2 + 1;// 默认左孩子大
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && _con[child] < _con[child + 1])//先考虑右孩子是否存在
        {
          child += 1;
        }
        if (_con[child] > _con[father])
        {
          swap(_con[child], _con[father]);
          father = child;
          child = father * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
 
    const T& top()
    {
      return _con[0];
    }
 
    bool empty()  const
    {
      return _con.empty();
    }
 
    size_t size() const
    {
      return _con.size();
    }
 
  private:
    Container _con;
  };
}

测试一下，Test.c:

#include "PriorityQueue.h"
 
void test_priority_queue()
{
  rtx::priority_queue<int> pq;
 
  pq.push(3);
  pq.push(1);
  pq.push(2);
  pq.push(5);
  pq.push(0);
  pq.push(8);
  pq.push(1);
 
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
}
 
int main()
{
   test_priority_queue();
    
    return 0;
}

1.2 迭代器区间构造和无参构造

前面没写无参构造代码也跑出来了，先写下迭代器区间构造，和以前一样;

但这里不要直接push，push的时间是O（N*logN），建堆的时间是logN：

    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
      :_con(first,last) // 初始化列表初始化代替下面被注释的
    {
      //while (first != last)
      //{
      //  _con.push_back(*first);
      //  ++first;
      //}
      for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i)
      {
        adjust_down(i);
      }
    }

这样的话运行代码就发现前面的无参构造报错了：没有默认的构造函数使用。

所以我们还要写上无参构造，但实际里面什么都不用写:

    priority_queue()
    {}

测试一下，Test.c:

#include "PriorityQueue.h"
 
void test_priority_queue()
{
  rtx::priority_queue<int> pq;
 
  pq.push(3);
  pq.push(1);
  pq.push(2);
  pq.push(5);
  pq.push(0);
  pq.push(8);
  pq.push(1);
 
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
 
  int arr[] = { 0,3,2,1,6,5,4,9,8,7 };
  rtx::priority_queue<int> heap(arr, arr + sizeof(arr) / sizeof(arr[0]));
  while (!heap.empty())
  {
    cout << heap.top() << " ";
    heap.pop();
  }
  cout << endl;
}
 
int main()
{
   test_priority_queue();
    
    return 0;
}

我们写死的最大问题是 —— 如果想按升序排列，就没办法排了。

我们这里写的用来排降序的大堆，如果想排升序我们需要写小堆，

C++ 有一种叫仿函数的东西，可以控制这些东西，下面先来介绍一下仿函数。

1.3 仿函数的介绍和使用

概念：使一个类的使用看上去像一个函数。可以像函数一样使用的对象，称为函数对象。

实现就是在类中重载 operator()，使得该类具备类似函数的行为，就是一个仿函数类了。

C语言优先级，() 圆括号使用形式为表达式或 "作为函数形参列表的括号"

写一个最简单的仿函数：

#include<iostream>
using namespace std;
 
namespace rtx
{
  struct less
  {
    bool operator()(const int& left, const int& right) const
    {
      return left < right;
    }
  };
}
 
int main()
{
  int a = 10, b = 20;
 
  rtx::less lessCmp;
 
  cout << lessCmp(a, b) << endl;
 
  return 0;
}

仿函数（函数对象）：对象可以像调用函数一样去使用，

我们还可以使其能够支持泛型，我们加一个 template 模板，加一个 greater 仿函数：

#include<iostream>
using namespace std;
 
namespace rtx
{
  template<class T>
  struct less
  {
    bool operator()(const T& left, const T& right) const
    {
      return left < right;
    }
  };
 
  template<class T>
  struct greater
  {
    bool operator()(const T& left, const T& right) const
    {
      return left > right;
    }
  };
}
 
int main()
{
  int a = 10, b = 20;
 
  rtx::less<int> lessCmp;
  cout << lessCmp(a, b) << endl;
 
  rtx::greater<int> gtCmp;
  cout << gtCmp(a, b) << endl;
 
  return 0;
}

一个对象能像函数一样用，看上去很神奇，实际上调用的只是我们重载的 operator() 而已。

我们在C阶段不是学过函数指针么，用函数指针不行吗？

函数指针确实可以做到这些功能。但是在这里函数指针跟仿函数比，一点都方便。

在 C++ 里其实是非常不喜欢使用函数指针的，函数的指针在一些地方用起来非常复杂。

所以巨佬才发明了仿函数等，代替函数指针。

1.4 完整priority_queue代码：

我们现在传仿函数去比较那些数据(在模板再加一个参数)，这样就不会写死了。

直接用库的less，PriorityQueue.h:

#pragma once
#include <iostream>
#include <vector> 
#include <algorithm>
#include <functional> // greater和less的头文件
using namespace std;
 
namespace rtx
{
  // Compare进行比较的仿函数 less->大堆
  // Compare进行比较的仿函数 greater->小堆
  template<class T, class Container = vector<T>,class Compare = less<T>>
  class priority_queue
  {
  public:
    priority_queue()
    {}
 
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
      :_con(first,last) // 初始化列表初始化代替下面被注释的
    {
      //while (first != last)
      //{
      //  _con.push_back(*first);
      //  ++first;
      //}
      for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i)
      {
        adjust_down(i);
      }
    }
 
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
 
    void adjust_up(size_t child)
    {
      Compare cmp;
 
      size_t father = (child - 1) / 2;
      while (child > 0)
      {
        //if (_con[father] < _con[child])
        if (cmp(_con[father], _con[child]))//仿函数想函数一样使用
        {
          swap(_con[father], _con[child]);
          child = father;// 交换后向上走
          father = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
 
    void pop()
    {
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
 
      adjust_down(0);
    }
 
    void adjust_down(size_t father)
    {
      Compare cmp;
      size_t child = father * 2 + 1;// 默认左孩子大
      while (child < _con.size())
      {
        //if (child + 1 < _con.size() && _con[child] < _con[child + 1])
        if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1]))//先考虑右孩子是否存在
        {
          child += 1;
        }
        //if (_con[child] > _con[father]) 这里写了大于，所以是不好的(下次一定)
        if (cmp(_con[father], _con[child]))
        {
          swap(_con[child], _con[father]);
          father = child;
          child = father * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
 
    const T& top()
    {
      return _con[0];
    }
 
    bool empty()  const
    {
      return _con.empty();
    }
 
    size_t size() const
    {
      return _con.size();
    }
 
  private:
    Container _con;
  };
}

测试：直接传greater 建个小堆看看：

#include "PriorityQueue.h"
 
void test_priority_queue()
{
  rtx::priority_queue<int,vector<int>, greater<int>> pq;
 
  pq.push(3);
  pq.push(1);
  pq.push(2);
  pq.push(5);
  pq.push(0);
  pq.push(8);
  pq.push(1);
 
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
 
  int arr[] = { 0,3,2,1,6,5,4,9,8,7 };
  rtx::priority_queue<int, vector<int>, greater<int>> heap(arr, arr + sizeof(arr) / sizeof(arr[0]));
  while (!heap.empty())
  {
    cout << heap.top() << " ";
    heap.pop();
  }
  cout << endl;
}
 
int main()
{
   test_priority_queue();
    
    return 0;
}

值得一提的是我们这里传的是类型，因为是类模板，

sort里传的是对象（用匿名对象就好），是函数模板：

1.5 相关笔试选择题

1. STL中的priority_queue使用的底层数据结构是什么( )

A.queue

B.heap

C.deque

D.vector

2. 下列代码的运行结果是（）

int main()
{
    priority_queue<int> a;
    priority_queue<int, vector<int>, greater<int> > c;
    priority_queue<string> b;
    for (int i = 0; i < 5; i++)
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty())
    {
        cout << a.top() << ' ';
        a.pop();
    }
    cout << endl;
    while (!c.empty())
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;
    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty())
    {
        cout << b.top() << ' ';
        b.pop();
    }
    cout << endl;
    return 0;
}

A.4 3 2 1 0 0 1 2 3 4 cbd abcd abc

B.0 1 2 3 4 0 1 2 3 4 cbd abcd abc

C.4 3 2 1 0 4 3 2 1 0 abc abcd cbd

D.0 1 2 3 4 4 3 2 1 0 cbd abcd abc

3. 以下说法正确的是( )

A.deque的存储空间为连续空间

B.list迭代器支持随机访问

C.如果需要高效的随机存取，还要大量的首尾的插入删除则建议使用deque

D.vector容量满时，那么插入元素时只需增加当前元素个数的内存即可

4. 仿函数比起一般函数具有很多优点，以下描述错误的是( )

A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态

B.仿函数即使定义相同，也可能有不同的类型

C.仿函数通常比一般函数速度快

D.仿函数使程序代码变简单

5. 假设cont是一个Container 的示例，里面包含数个元素，那么当CONTAINER为：

1.vector 2.list 3.deque 会导致下面的代码片段崩溃的Container 类型是（）

int main()
{
  Container cont = { 1, 2, 3, 4, 5 };
  Container::iterator iter, tempIt;
  for (iter = cont.begin(); iter != cont.end();)
  {
    tempIt = iter;
    ++iter;
    cont.erase(tempIt);
  }
}

A.1, 2

B.2, 3

C.1, 3

D.1, 2, 3

答案：

1. D

分析:优先级队列priority_queue底层采用vector容器作为底层数据结构

2. A

分析:优先级队列默认情况为：大堆，这是解题的关键

priority_queue a; //a是大堆

priority_queue, greater > c; //c指定了比较规则，是小堆

priority_queue b; //b是大堆

因此分别建堆的过程是建立a大堆，c小堆，b大堆

所以出队的顺序就按照其优先级大小出队

3. C

A.deque底层总体为不连续空间

B.不支持，因为底层是一个个的不连续节点

C.正确

D.一般会以容量的2倍扩充容量，这是为了减少扩容的次数，减少内存碎片

4. C

A.仿函数是模板函数，可以根据不同的类型代表不同的状态

B.仿函数是模板函数，可以有不同类型

C.仿函数是模板函数，其速度比一般函数要慢,故错误

D.仿函数在一定程度上使代码更通用，本质上简化了代码

5. C

分析：此题主要考察cont.erase(tmpit)删除数据之后，迭代器失效相关问题

本题重点要关注的是底层实现

vector、deque底层都是用了连续空间，所以虽然++iter迭代器了，但是erase(tempit)以后

底层是连续空间，删除会挪动数据，最终导致iter意义变了，已失效了。

而list，不是连续空间，删除以后tempIt虽然失效了，但是不影响iter。

从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（下）：https://developer.aliyun.com/article/1521893?spm=a2c6h.13148508.setting.22.712b4f0eDngT44

从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（上）

1. priority_queue的模拟实现

1.1 未完全的priority_queue

1.2 迭代器区间构造和无参构造

1.3 仿函数的介绍和使用

1.4 完整priority_queue代码：

1.5 相关笔试选择题

答案：

热门文章

最新文章

相关课程

相关电子书