当前位置: 首页 > news >正文

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

在这里插入图片描述

queue和priority_queue(理解使用和模拟实现)

  • 什么是queue
  • queue的使用
    • 1.queue构造函数
    • 2.empty()
    • 3.size()
    • 4.front()
    • 5.back();
    • 6.push
    • 7.emplace
    • 8.pop()
    • 9.swap
  • 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
  • 结语

什么是queue

在这里插入图片描述

  1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty:检测队列是否为空
size:返回队列中有效元素的个数
front:返回队头元素的引用
back:返回队尾元素的引用
push_back:在队列尾部入队列
pop_front:在队列头部出队列

  1. 标准容器类dequelist满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque

queue的使用

1.queue构造函数

在这里插入图片描述

initialize (1):使用已存在的容器初始化队列。

explicit queue(const container_type& ctnr);
这个构造函数接受一个已存在的容器 ctnr,并使用其内容初始化队列。

示例:

std::deque<int> myDeque = {1, 2, 3};
std::queue<int> myQueue(myDeque); // 使用已存在的 deque 初始化队列

move-initialize (2):使用已存在的容器初始化队列,并在初始化后将原容器置为空。

explicit queue(container_type&& ctnr = container_type());
这个构造函数接受一个右值引用的容器 ctnr,将其用于初始化队列,并在初始化后清空 ctnr

示例:

std::deque<int> myDeque = {1, 2, 3};
std::queue<int> myQueue(std::move(myDeque)); // 使用已存在的 deque 初始化队列,并清空 myDeque

allocator (3):使用自定义分配器 Alloc 初始化队列。

template <class Alloc> explicit queue(const Alloc& alloc);
这个构造函数接受一个自定义分配器类型 Alloc,用于在初始化时分配内存。

示例:

std::allocator<int> myAllocator;
std::queue<int> myQueue(myAllocator); // 使用自定义分配器初始化队列

init + allocator (4):使用已存在的容器和自定义分配器初始化队列。

template <class Alloc> queue(const container_type& ctnr, const Alloc& alloc);
这个构造函数接受已存在的容器 ctnr 和自定义分配器 alloc,用于在初始化时指定底层容器和分配器。

示例:

std::deque<int> myDeque = {1, 2, 3};
std::allocator<int> myAllocator;
std::queue<int> myQueue(myDeque, myAllocator); // 使用已存在的 deque 和自定义分配器初始化队列

move-init + allocator (5):使用已存在的容器和自定义分配器初始化队列,并在初始化后将原容器置为空。

template <class Alloc> queue(container_type&& ctnr, const Alloc& alloc);
类似于 (2),这个构造函数接受右值引用的容器 ctnr 和自定义分配器 alloc,用于初始化队列,并在初始化后清空 ctnr

示例:

std::deque<int> myDeque = {1, 2, 3};
std::allocator<int> myAllocator;
std::queue<int> myQueue(std::move(myDeque), myAllocator); // 使用已存在的 deque 和自定义分配器初始化队列,并清空 myDeque

copy + allocator (6):复制已存在队列,并使用自定义分配器初始化新队列。

template <class Alloc> queue(const queue& x, const Alloc& alloc);
这个构造函数接受一个已存在的队列 x 和自定义分配器 alloc,用于在初始化时复制 x 中的元素到新的队列。

示例:

std::queue<int> originalQueue;
// 添加一些元素到 originalQueue
std::allocator<int> myAllocator;
std::queue<int> myQueue(originalQueue, myAllocator); // 复制已存在队列并使用自定义分配器初始化新队列

move + allocator (7):移动已存在队列,并使用自定义分配器初始化新队列。

template <class Alloc> queue(queue&& x, const Alloc& alloc);
类似于 (5),这个构造函数接受右值引用的队列 x 和自定义分配器 alloc,用于初始化新队列并从 x 移动元素。

示例:

std::queue<int> originalQueue;
// 添加一些元素到 originalQueue
std::allocator<int> myAllocator;
std::queue<int> myQueue(std::move(originalQueue), myAllocator); // 移动已存在队列并使用自定义分配器初始化新队列

2.empty()

bool empty() conststd::queue 类的成员函数之一,用于判断队列是否为空。这个函数不会修改队列的内容,因此被声明为 const,表示它不会对对象进行修改。

返回值:

如果队列为空,返回 true
如果队列不为空,返回 false

使用示例:

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

在这个示例中,首先创建了一个空队列 myQueue,然后通过 empty() 函数判断队列是否为空。在添加一个元素后,再次调用 empty() 函数来验证队列的状态。根据输出,你可以看到队列在没有元素时为空,在添加元素后不为空。

3.size()

size_type size() conststd::queue 类的成员函数之一,用于获取队列中元素的数量。这个函数不会修改队列的内容,因此被声明为 const,表示它不会对对象进行修改。

返回值:

返回队列中当前的元素数量(大小)。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;std::cout << "Initial size: " << myQueue.size() << std::endl;myQueue.push(42);myQueue.push(20);myQueue.push(10);std::cout << "Updated size: " << myQueue.size() << std::endl;return 0;
}

在这个示例中,首先创建一个空队列 myQueue,然后使用 size() 函数获取队列的初始大小。接着添加三个元素到队列中,并再次调用 size() 函数来获取更新后的队列大小。根据输出,你可以看到队列在添加元素后大小发生了变化。

4.front()

reference& front()const_reference& front() conststd::queue 类的成员函数之一,用于访问队列的前(头)元素。这些函数不会修改队列的内容,因此被声明为 const 或者返回常量引用,表示它们不会对对象进行修改。

referenceconst_reference 是模板参数 T 的引用类型和常量引用类型,分别用于表示队列中元素的类型和常量引用类型。返回的引用允许你访问队列的第一个元素。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;myQueue.push(42);myQueue.push(20);int& firstElement = myQueue.front();const int& constFirstElement = myQueue.front();std::cout << "First element: " << firstElement << std::endl;std::cout << "Constant first element: " << constFirstElement << std::endl;return 0;
}

在这个示例中,首先创建一个队列 myQueue,然后添加两个元素。通过 front() 函数获取队列的第一个元素,并将其存储到一个非常量引用 firstElement 和一个常量引用 constFirstElement 中。根据输出,你可以看到两种引用都可以访问队列的第一个元素的值。

5.back();

reference& back()const_reference& back() conststd::queue 类的成员函数之一,用于访问队列的后(尾)元素。这些函数不会修改队列的内容,因此被声明为 const 或者返回常量引用,表示它们不会对对象进行修改。

referenceconst_reference 是模板参数 T 的引用类型和常量引用类型,分别用于表示队列中元素的类型和常量引用类型。返回的引用允许你访问队列的最后一个元素。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;myQueue.push(42);myQueue.push(20);int& lastElement = myQueue.back();const int& constLastElement = myQueue.back();std::cout << "Last element: " << lastElement << std::endl;std::cout << "Constant last element: " << constLastElement << std::endl;return 0;
}

在这个示例中,首先创建一个队列 myQueue,然后添加两个元素。通过 back() 函数获取队列的最后一个元素,并将其存储到一个非常量引用 lastElement 和一个常量引用 constLastElement 中。根据输出,你可以看到两种引用都可以访问队列的最后一个元素的值。

6.push

void push (const value_type& val)void push (value_type&& val) 是 std::queue 类的成员函数之一,用于将元素添加到队列的末尾。

const value_type& val 是一个常量引用,用于传递需要添加到队列的元素。
value_type&& val 是一个右值引用,用于传递需要添加到队列的元素,通常用于支持移动语义。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;myQueue.push(42); // 使用右值int value = 20;myQueue.push(value); // 使用左值return 0;
}

在这个示例中,首先创建一个队列 myQueue,然后使用 push() 函数将两个不同类型的值添加到队列中。第一个 push() 使用右值 42,第二个 push() 使用左值变量 value。队列将会按照元素添加的顺序保持它们。

7.emplace

template <class... Args> void emplace (Args&&... args)std::queue 类的成员函数之一,用于通过构造函数参数列表直接在队列的末尾构造一个新元素。

Args... args 是模板参数包,表示传递给构造函数的参数列表。
使用 emplace() 函数可以避免额外的对象复制或移动操作,直接在容器内部构造对象。

使用示例:

#include <iostream>
#include <queue>class MyObject {
public:MyObject(int value) : m_value(value) {std::cout << "Constructed: " << m_value << std::endl;}~MyObject() {std::cout << "Destructed: " << m_value << std::endl;}private:int m_value;
};int main() {std::queue<MyObject> myQueue;myQueue.emplace(42); // 使用右值参数构造myQueue.emplace(20); // 使用右值参数构造return 0;
}

在这个示例中,首先创建一个队列 myQueue,然后使用 emplace() 函数通过右值参数直接在队列末尾构造两个 MyObject 对象。由于使用了 emplace(),对象将在队列中直接构造,而不会发生额外的复制或移动操作。

8.pop()

void pop()std::queue 类的成员函数之一,用于从队列中移除队列头部的元素。

调用 pop() 函数会删除队列中的第一个元素,并将队列中的其余元素向前移动,以填补被移除的元素的位置。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;myQueue.push(42);myQueue.push(20);myQueue.push(10);std::cout << "Size before pop: " << myQueue.size() << std::endl;myQueue.pop();std::cout << "Size after pop: " << myQueue.size() << std::endl;return 0;
}

在这个示例中,首先创建一个队列 myQueue,然后使用 push() 函数添加三个元素到队列中。通过调用 pop() 函数,将队列头部的元素 42 移除。根据输出,你可以看到在调用 pop() 后,队列的大小减少了。

9.swap

void swap(queue& x) noexceptstd::queue 类的成员函数之一,用于交换当前队列与另一个队列 x 的内容。

x:一个要与当前队列进行交换的另一个队列。
noexcept:这个函数被声明为不会抛出异常,表示在交换过程中不会引发异常。

使用示例:

#include <iostream>
#include <queue>int main() {std::queue<int> queue1;std::queue<int> queue2;queue1.push(42);queue1.push(20);queue2.push(10);std::cout << "Before swap:" << std::endl;std::cout << "Queue 1 front: " << queue1.front() << std::endl;std::cout << "Queue 2 front: " << queue2.front() << std::endl;queue1.swap(queue2);std::cout << "After swap:" << std::endl;std::cout << "Queue 1 front: " << queue1.front() << std::endl;std::cout << "Queue 2 front: " << queue2.front() << std::endl;return 0;
}

在这个示例中,首先创建两个队列 queue1queue2,并分别添加元素到它们中。通过调用 swap() 函数,交换了队列的内容。根据输出,你可以看到在交换后,队列的内容也发生了交换。

queue模拟实现

#pragma once
#include <deque>namespace xzq
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& back(){return _con.back();}T& front(){return _con.front();}const T& back() const{return _con.back();}const T& front() const{return _con.front();}bool empty()  const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

首先,这个队列类使用了一个名为 Container 的模板参数,默认值为 std::deque<T>。这允许你在创建队列对象时指定底层容器类型,如果不指定,默认使用 std::deque

push(const T& x) 函数用于将元素 x 添加到队列的末尾,它实际上调用了底层容器的 push_back() 方法。

pop() 函数用于移除队列头部的元素,它实际上调用了底层容器的 pop_front() 方法。

back() 函数返回队列中的最后一个元素的引用,它可以用于访问队列的末尾元素。

front() 函数返回队列中的第一个元素的引用,用于访问队列的头部元素。

empty() 函数用于检查队列是否为空,它实际上调用了底层容器的 empty() 方法。

size() 函数用于获取队列中元素的数量,它实际上调用了底层容器的 size() 方法。

私有成员 _con 是底层容器对象,用于存储队列的元素。

使用这个模拟队列类,你可以选择不同的底层容器类型(默认为 std::deque),并调用类的方法来模拟队列的基本操作,如添加元素、移除元素、访问元素、判断是否为空等。这种实现方式允许你通过模板来适应不同的数据类型和底层容器,从而更加灵活地使用队列。

什么是priority_queue

在这里插入图片描述

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

empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素

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

priority_queue的使用

1.priority_queue构造函数

在这里插入图片描述
std::priority_queueC++ 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); // 调用仿函数 addFiveint result2 = addTen(7);  // 调用仿函数 addTenstd::cout << "Result 1: " << result1 << std::endl;std::cout << "Result 2: " << result2 << std::endl;return 0;
}

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

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

2.empty()

bool empty() conststd::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() conststd::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() conststd::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) noexceptstd::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;
}

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

模拟实现priority_queue

#pragma oncenamespace 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(理解使用和模拟实现)

queue和priority_queue&#xff08;理解使用和模拟实现&#xff09; 什么是queuequeue的使用1.queue构造函数2.empty()3.size()4.front()5.back();6.push7.emplace8.pop()9.swap queue模拟实现什么是priority_queuepriority_queue的使用1.priority_queue构造函数1.1 模板参数 C…...

性能场景和性能需求指标

目录 一 性能场景 1、基准性能场景 2、容量性能场景 3、稳定性性能场景 4、异常性能场景 二 性能需求指标 1、业务指标 2、技术指标 2.1 时间指标 RT 2.2 容量指标 TPS 2.3 资源利用率 3、指标之间的关系 “TPS”与“响应时间” “用户数”与“TPS”与“压力工具中…...

Python学习 -- 常用函数与实例详解

在Python编程中&#xff0c;数据转换是一项关键任务&#xff0c;它允许我们在不同数据类型之间自由流动&#xff0c;从而提高代码的灵活性和效率。本篇博客将深入探讨常用的数据转换函数&#xff0c;并通过实际案例为你展示如何巧妙地在不同数据类型之间转换。 数据类型转换函…...

MySQL 账号权限

mysql 在安装好后&#xff0c;默认是没有远端管理账号。 一、账号管理 1. 查看账号列表 MySQL用户账号和信息存储在名为 mysql 的数据库中。一般不需要直接访问 mysql 数据库和表&#xff0c;但有时需要直接访问。例如&#xff0c;查看数据库所有用户账号列表时。 USE mysql; …...

[Mongodb 5.0]单机启动

安装完mongodb后&#xff0c;会自动生成下面两个目录(mongod.conf中设定的)&#xff0c;用来存放日志和数据 /var/lib/mongo (数据目录) /var/log/mongodb (日志目录) 要启动一个单机版的mongodb&#xff0c;一般有两种方式&#xff1a; 第一种启动方式&#xff1a;直接使用…...

[HDLBits] Exams/m2014 q4b

Implement the following circuit: module top_module (input clk,input d, input ar, // asynchronous resetoutput q);always(posedge clk or posedge ar) beginif(ar)q<1b0;elseq<d;end endmodule...

数据结构入门:队列

目录 文章目录 前言 1.队列 1.1 队列的概念及结构 1.2 队列的实现 1.2.1 队列的定义 1.2.2队列的初始化 1.2.3 入队 1.2.4 判空 1.2.5 出队 1.2.6 队头队尾数据 1.2.7 队列长度 1.2.8 队列销毁 总结 前言 队列&#xff0c;作为一种重要的数据结构&#xff0c;在计算机科学中扮演…...

面试热题(合并K个升序链表)

给定一个链表数组&#xff0c;每个链表都已经按升序排列。 请将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a;链表数组如下&#xff1a; [1->4->5,1…...

优化过多if else判断代码

有些判断难免会遇到很多 if else 看起来很头疼 下面是一个优化示例 修改前 if(this.$route.query.deptId){this.queryParams.deptId this.$route.query.deptId}else if (this.$store.state.adaptation.roleSign.includes(fengongsicengji)) {const ancestorsId this.$stor…...

最强自动化测试框架Playwright (27)-跟踪查看器

Playwright Trace Viewer 是一个 GUI 工具&#xff0c;可帮助您在脚本运行后探索记录的 Playwright 跟踪。可以本地打开&#xff0c;也可以在trace.playwright.dev.打开&#xff0c; 录制跟踪文件 使用context.tracing.start进行录制&#xff0c;使用stop方法保存录制文件 b…...

【工作中问题解决实践 十一】Kafka消费者消费堆积且频繁rebalance

最近有点不走运&#xff0c;老是遇到基础服务的问题&#xff0c;还是记着点儿解决方法&#xff0c;以后再遇到快速解决吧&#xff0c;今天遇到这个问题倒不算紧急&#xff0c;但也能通过这个问题熟悉一下Kafka的配置。 问题背景 正在开会的时候突然收到一连串的报警&#xff…...

ChatGpt提示词大全

中文版本 行为 提示词 Linux终端 我希望你能充当一个linux终端。我将输入命令&#xff0c;你会回复终端应该显示什么。我想让你只回复在一个唯一的代码块内的终端输出&#xff0c;而没有别的。不要写一些解释。不要键入命令&#xff0c;除非我指示你这样做。当我需要用英语告…...

利用SimpleDateFormat或者LocalDateTime生成格式为“yyyy-MM-dd HH:mm:ss“的当前时间

java程序&#xff1a; // 利用LocalDateTime生成格式为"yyyy-MM-dd HH:mm:ss"的当前时间 DateTimeFormatter formatter DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss"); LocalDateTime now LocalDateTime.now(); String time1 now.format(format…...

使用 Postman 批量发送请求的最佳实践

目录 背景 批量发送&#xff1f; 起因 思考 Postman 批量发送接口 创建集合和接口 批量发送接口 资料获取方法 背景 最近写了几个接口&#xff1a; 获取 books 的接口获取 likes 的接口获取 collections 的接口 但是我还是不放心&#xff0c;因为这些接口到底稳不稳…...

Docker一键部署项目,无需登录XShell

文章目录 一键部署项目Docker手动部署SpringBoot项目编写docker部署的脚本文件script.sh 脚本内容 特别注意&#xff01;编写dockerfiledockerfile 文件内容 上传后端服务的jar包到服务器中执行 script 脚本部署后端服务 自动部署SpringBoot项目引入jsch依赖编写jsch工具类执行…...

GIt Squash 多个提交压缩提交

假设你有一个名为 feature 的分支&#xff0c;它包含三个提交&#xff08;A, B, C&#xff09;&#xff0c;并且你想将这三个提交压缩成一个。下面是如何做到这一点的。 首先&#xff0c;找出你要开始压缩的那个最早提交的哈希值。在这个例子中&#xff0c;我们假设 A 是最早的…...

【数据结构】栈与队列

1 栈 1.1 栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出 LIFO (Last In First Out) 的原则。 压栈&#xff1a;栈…...

突然让做性能测试?试试RunnerGo

当前&#xff0c;性能测试已经是一名软件测试工程师必须要了解&#xff0c;甚至熟练使用的一项技能了&#xff0c;在工作时可能每次发版都要跑一遍性能&#xff0c;跑一遍自动化。性能测试入门容易&#xff0c;深入则需要太多的知识量&#xff0c;今天这篇文章给大家带来&#…...

(7)(7.4) 集结航点

文章目录 7.4.1 概述 7.4.2 设置集结航点 7.4.3 飞行示例 7.4.4 附录 7.4.1 概述 通常情况下&#xff0c;当固定翼或旋翼飞机进入"返回发射"(Return to Launch (RTL))模式&#xff08;通常由自动驾驶仪失控保护触发&#xff09;(failsafe)时&#xff0c;默认行为…...

基于kubeadm部署K8S集群:上篇

目录 一、环境准备 1、主机初始化配置 2、配置主机名绑定hosts&#xff0c;不同主机名称不同 3、主机配置初始化 4、部署docker环境 二、部署kubernetes集群 1、组件介绍 2、所有主机配置阿里云yum源 3、安装kubelet 、kubeadm 、kubectl 4、配置init-config.yaml 5、…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

python打卡第47天

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图&#xff0c;展示模…...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...