C++初阶之一篇文章教会你queue和priority_queue（理解使用和模拟实现）（下）-阿里云开发者社区

什么是priority_queue

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

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

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

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

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

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

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

priority_queue的使用

1.priority_queue构造函数

std::priority_queue 是 C++ STL 提供的优先队列容器，它是基于堆实现的，允许你以特定的顺序添加和移除元素。

下面是这些构造函数的解释及示例：

priority_queue(const Compare& comp, const Container& ctnr)：构造一个优先队列，使用给定的比较函数 comp 和底层容器 ctnr。

priority_queue(InputIterator first, InputIterator last, const Compare& comp, const Container& ctnr)：使用迭代器范围 [first, last) 中的元素构造一个优先队列，并使用给定的比较函数 comp 和底层容器 ctnr。

explicit priority_queue(const Compare& comp = Compare(), Container&& ctnr = Container())：构造一个优先队列，使用给定的比较函数 comp 和移动语义传递的底层容器 ctnr。

template <class InputIterator> priority_queue(InputIterator first, InputIterator last, const Compare& comp, Container&& ctnr = Container())：使用迭代器范围 [first, last) 中的元素构造一个优先队列，并使用给定的比较函数 comp 和移动语义传递的底层容器 ctnr。

Allocator 版本：这些构造函数使用不同的分配器allocator来构造优先队列。

示例：

#include <iostream>
#include <queue>
#include <vector>
int main() {
    // 使用默认底层容器 std::vector，以默认比较函数（最大堆）构造优先队列
    std::priority_queue<int> maxHeap;
    // 使用自定义比较函数（最小堆）和底层容器 std::deque 构造优先队列
    auto compare = [](int a, int b) { return a > b; };
    std::deque<int> container = {5, 3, 8, 1, 9};
    std::priority_queue<int, std::deque<int>, decltype(compare)> minHeap(compare, container);
    // 使用迭代器范围构造优先队列
    std::vector<int> elements = {7, 2, 4, 6, 0};
    std::priority_queue<int, std::vector<int>> iteratorQueue(elements.begin(), elements.end());
    // 输出优先队列中的元素
    while (!iteratorQueue.empty()) {
        std::cout << iteratorQueue.top() << " ";
        iteratorQueue.pop();
    }
    return 0;
}

在这个示例中，我们演示了不同构造函数的用法。首先，使用默认构造函数构造了一个最大堆的优先队列。然后，我们使用自定义比较函数和底层容器 std::deque 构造了一个最小堆的优先队列。最后，使用迭代器范围构造了一个优先队列。根据输出，你可以看到优先队列以不同的顺序输出元素。

1.1 模板参数 Compare

在 std::priority_queue 类中，通过模板参数 Compare 来指定用于比较元素的函数对象，从而影响堆的排序方式。Compare 是一个仿函数，它定义了元素之间的比较方式。根据不同的 Compare，优先队列可以变成大堆（最大堆）或小堆（最小堆）。

默认的 std::less<T>（大堆）：

std::less 是一个函数对象，它重载了 operator()，用于比较两个元素。它返回一个布尔值，表示是否第一个参数小于第二个参数。在默认情况下，如果不提供 Compare 参数，优先队列使用 std::less 作为比较函数对象，即大堆。这意味着在大堆中，父节点的值总是大于或等于子节点的值。

std::greater<T>（小堆）：

std::greater<T> 是另一个函数对象，它重载了 operator()，用于比较两个元素。与 std::less<T> 不同，std::greater<T> 返回一个布尔值，表示第一个参数是否大于第二个参数。如果你将 std::greater<T> 传递给 priority_queue，它将会构造一个小堆。在小堆中，父节点的值总是小于或等于子节点的值。

以下是示例代码，演示了如何使用不同的比较函数对象来创建大堆和小堆：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap; // 默认大堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小堆
    maxHeap.push(5);
    maxHeap.push(3);
    maxHeap.push(8);
    minHeap.push(5);
    minHeap.push(3);
    minHeap.push(8);
    std::cout << "Max Heap (Top element): " << maxHeap.top() << std::endl;
    std::cout << "Min Heap (Top element): " << minHeap.top() << std::endl;
    return 0;
}

在这个示例中，我们分别创建了一个大堆和一个小堆。通过 top() 函数，我们可以看到大堆的顶部元素是最大的，小堆的顶部元素是最小的。这反映了不同比较函数对象的影响。

1.2 什么是仿函数?

仿函数（Functor）是一种重载了函数调用操作符 operator() 的类对象，使得该对象可以像函数一样被调用。它实际上是一种函数对象，它可以具有自己的成员变量和操作，同时可以在使用上类似于普通函数。

使用仿函数的主要优点之一是可以将函数的行为和状态封装在对象中，从而使代码更具有可读性和可维护性。仿函数可以用于各种情况，包括标准算法、STL容器和其他需要函数式操作的地方。

一个仿函数类通常至少需要实现 operator()，它可以具有不同的参数和返回类型，具体取决于仿函数的用途。以下是一个简单的示例：

#include <iostream>
class Adder {
public:
    Adder(int value) : value_(value) {}
    int operator()(int x) {
        return x + value_;
    }
private:
    int value_;
};
int main() {
    Adder addFive(5);
    Adder addTen(10);
    int result1 = addFive(7); // 调用仿函数 addFive
    int result2 = addTen(7);  // 调用仿函数 addTen
    std::cout << "Result 1: " << result1 << std::endl;
    std::cout << "Result 2: " << result2 << std::endl;
    return 0;
}

在这个示例中，Adder 类被定义为一个仿函数，它接受一个整数值，并在调用时将该值添加到传递的参数上。在 main() 函数中，我们创建了两个 Adder 对象 addFive 和 addTen，然后通过调用它们来执行加法操作。

总之，仿函数是一种函数对象，它使得对象可以像函数一样被调用，从而可以将函数的行为和状态封装在一个对象中。这在编写更加灵活和可读性高的代码时非常有用。

2.empty()

bool empty() const 是 std::priority_queue 类的成员函数之一，用于检查优先队列是否为空。

empty() 函数返回一个布尔值，表示优先队列是否为空。

const 修饰符表示这个函数不会修改优先队列的内容。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    if (maxHeap.empty()) {
        std::cout << "The priority queue is empty." << std::endl;
    } else {
        std::cout << "The priority queue is not empty." << std::endl;
    }
    maxHeap.push(42);
    if (maxHeap.empty()) {
        std::cout << "The priority queue is empty." << std::endl;
    } else {
        std::cout << "The priority queue is not empty." << std::endl;
    }
    return 0;
}

在这个示例中，我们首先创建了一个空的 std::priority_queue 对象 maxHeap，然后使用 empty() 函数检查它是否为空。根据输出，你可以看到在添加一个元素后，优先队列不再为空。

3.size()

size_type size() const 是 std::priority_queue 类的成员函数之一，用于获取优先队列中元素的数量。

size() 函数返回一个无符号整数size_type，表示优先队列中元素的数量。

const 修饰符表示这个函数不会修改优先队列的内容。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(42);
    maxHeap.push(20);
    maxHeap.push(10);
    std::cout << "Size of the priority queue: " << maxHeap.size() << std::endl;
    return 0;
}

在这个示例中，我们创建了一个包含三个元素的大堆优先队列 maxHeap，然后使用 size() 函数获取队列中元素的数量。根据输出，你可以看到队列中有三个元素。

4.top()

const_reference top() const 是 std::priority_queue 类的成员函数之一，用于获取优先队列的顶部元素（最大元素或最小元素，取决于堆的类型），但不改变队列的内容。

top() 函数返回队列的顶部元素的常引用const_reference，即最大元素或最小元素。

const 修饰符表示这个函数不会修改优先队列的内容。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(42);
    maxHeap.push(20);
    maxHeap.push(10);
    std::cout << "Top element: " << maxHeap.top() << std::endl;
    return 0;
}

在这个示例中，我们创建了一个大堆优先队列 maxHeap，并添加了三个元素。使用 top() 函数，我们获取了队列中的顶部元素（最大元素）。根据输出，你可以看到顶部元素的值是 42。

5.push

void push(const value_type& val) 和 void push(value_type&& val) 是 std::priority_queue 类的成员函数之一，用于将新元素添加到优先队列中。

push(const value_type& val) 接受一个常引用 val，将一个新的元素拷贝到优先队列中。

push(value_type&& val) 接受一个右值引用 val，使用移动语义将一个新的元素移动到优先队列中。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(42); // 使用 push(const value_type& val)
    maxHeap.push(20); // 使用 push(const value_type& val)
    maxHeap.push(10); // 使用 push(const value_type& val)
    std::cout << "Top element: " << maxHeap.top() << std::endl;
    return 0;
}

在这个示例中，我们使用两种不同的方式将元素添加到大堆优先队列 maxHeap 中。第一种是使用 push(const value_type& val)，第二种是使用 push(value_type&& val)。这两种方式都会将元素添加到队列中。根据输出，你可以看到顶部元素的值是 42，这是因为优先队列会自动将最大（或最小）的元素放在顶部。

6.emplace

template <class... Args> void emplace(Args&&... args) 是 std::priority_queue 类的成员函数之一，用于以就地构造的方式在优先队列中插入一个新元素。

emplace() 函数使用参数包parameter pack来接受构造元素所需的参数。

它可以在现有元素中进行插入，同时避免额外的拷贝或移动操作，提高效率。

这个函数使用完美转发来传递参数，以适应不同类型的构造函数。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.emplace(42); // 插入一个新元素
    int value = 20;
    maxHeap.emplace(value); // 插入一个新元素，使用拷贝构造函数
    maxHeap.emplace(10); // 插入一个新元素
    std::cout << "Top element: " << maxHeap.top() << std::endl;
    return 0;
}

在这个示例中，我们使用 emplace() 函数以就地构造的方式插入新元素到大堆优先队列 maxHeap 中。在插入时，我们可以传递构造元素所需的参数。这个函数会自动调用适当的构造函数，以在堆中插入新元素。根据输出，你可以看到顶部元素的值是 42。

7.pop()

void pop()是 std::priority_queue 类的成员函数之一，用于移除优先队列的顶部元素（最大元素或最小元素，取决于堆的类型）。

pop() 函数将优先队列的顶部元素移除，同时会重新调整堆以维持堆的性质。

注意，调用这个函数前需要确保队列不为空，否则会产生未定义的行为。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(42);
    maxHeap.push(20);
    maxHeap.push(10);
    std::cout << "Top element before pop: " << maxHeap.top() << std::endl;
    maxHeap.pop();
    std::cout << "Top element after pop: " << maxHeap.top() << std::endl;
    return 0;
}

在这个示例中，我们首先创建了一个大堆优先队列 maxHeap，然后使用 push() 函数添加了三个元素。通过 top() 函数，我们获取了队列的顶部元素。接着，我们使用 pop() 函数将顶部元素移除，并再次通过 top() 函数获取了新的顶部元素。根据输出，你可以看到在移除一个元素后，队列的顶部元素变为 20。

8.swap

void swap(priority_queue& x) noexcept 是 std::priority_queue 类的成员函数之一，用于交换两个优先队列的内容。

swap() 函数用于交换调用对象和传递的参数 x 之间的内容。

这个操作会导致两个优先队列的内容互换，但不会改变它们的比较函数或其他属性。

noexcept 关键字表示这个函数不会抛出异常。

使用示例：

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> maxHeap1;
    std::priority_queue<int> maxHeap2;
    maxHeap1.push(42);
    maxHeap1.push(20);
    maxHeap2.push(10);
    maxHeap2.push(30);
    std::cout << "Max Heap 1 (Top element before swap): " << maxHeap1.top() << std::endl;
    std::cout << "Max Heap 2 (Top element before swap): " << maxHeap2.top() << std::endl;
    maxHeap1.swap(maxHeap2);
    std::cout << "Max Heap 1 (Top element after swap): " << maxHeap1.top() << std::endl;
    std::cout << "Max Heap 2 (Top element after swap): " << maxHeap2.top() << std::endl;
    return 0;
}

在这个示例中，我们创建了两个大堆优先队列 maxHeap1 和 maxHeap2，并分别添加了不同的元素。通过 top() 函数，我们获取了两个队列的顶部元素。然后使用 swap() 函数，我们交换了两个队列的内容。根据输出，你可以看到交换后，两个队列的内容互换了。

模拟实现priority_queue

#pragma once
namespace xzq
{
  // Compare进行比较的仿函数 less->大堆
  // Compare进行比较的仿函数 greater->小堆
  template<class T, class Container = vector<T>, class Compare = std::less<T>>
  class priority_queue
  {
  public:
    priority_queue()
    {}
    template <class InputIterator>         
    priority_queue(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        _con.push_back(*first);
        ++first;
      }
      for (int i = (_con.size()-1-1)/2; i >= 0; --i)
      {
        adjust_down(i);
      }
    }
    void adjust_up(size_t child)
    {
      Compare com;
      size_t parent = (child - 1) / 2;
      while (child > 0)
      {
        if (com(_con[parent], _con[child]))
        {
          std::swap(_con[child], _con[parent]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void adjust_down(size_t parent)
    {
      Compare com;
      size_t child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
        {
          ++child;
        }
        if (com(_con[parent],_con[child]))
        {
          std::swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void pop()
    {
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    const T& top()
    {
      return _con[0];
    }
    bool empty()  const
    {
      return _con.empty();
    }
    size_t size() const
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}

命名空间 xzq：

这段代码位于命名空间 xzq 中，这是一个自定义的命名空间，用于将相关的类、函数等封装在一起，以避免与其他代码的命名冲突。

模板类 priority_queue：

这是一个模板类，它代表了一个优先队列的实现。它接受三个模板参数：T（元素类型），Container（底层容器类型，默认为 std::vector<T>），和 Compare（用于比较元素的仿函数，默认为 std::less<T>）

Compare 是一个模板参数，用于进行元素的比较。它是一个仿函数，可以是 std::less<T>（默认）或 std::greater<T>，具体取决于用户提供的优先队列类型。Compare 仿函数用于确定在堆中的元素排序方式，从而决定了是最大堆还是最小堆。在 priority_queue 类的各个成员函数中，通过调用 Compare 仿函数来进行元素的比较，从而实现了插入和调整堆的操作。

构造函数 priority_queue()：

这是一个默认构造函数，不需要使用 Compare 仿函数进行比较。

构造函数模板 priority_queue(InputIterator first, InputIterator last)：

在构造函数内部，使用 Compare 仿函数来执行比较操作，以确定元素的顺序。在添加元素后，通过调用 adjust_down 函数来构建堆。

成员函数 adjust_up(size_t child)：

在上浮操作中，使用 Compare 仿函数执行比较，以确定是否需要交换父子节点的位置，从而保持堆的性质。

成员函数 push(const T& x)：

在插入操作中，首先将新元素添加到底层容器 _con，然后通过调用 adjust_up 函数来执行上浮操作，保证新元素位于合适的位置。

成员函数 adjust_down(size_t parent)：

在下沉操作中，使用 Compare 仿函数执行比较，以确定是否需要交换父子节点的位置，从而保持堆的性质。

成员函数 pop()：

在删除操作中，首先将顶部元素与底层容器的最后一个元素交换，然后通过调用 adjust_down 函数来执行下沉操作，保证堆的性质。

成员函数 const T& top()：

通过返回 _con[0]，获取优先队列的顶部元素。

结语

有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！

制作不易，如有不正之处敬请指出

感谢大家的来访，UU们的观看是我坚持下去的动力

在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！

C++初阶之一篇文章教会你queue和priority_queue（理解使用和模拟实现）（下）

什么是priority_queue

priority_queue的使用

1.priority_queue构造函数

1.1 模板参数 Compare

1.2 什么是仿函数?

2.empty()

3.size()

4.top()

5.push

6.emplace

7.pop()

8.swap

模拟实现priority_queue

结语

热门文章

最新文章

相关课程

相关电子书