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们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89950.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

论文阅读 RRNet: A Hybrid Detector for Object Detection in Drone-captured Images

文章目录 RRNet: A Hybrid Detector for Object Detection in Drone-captured ImagesAbstract1. Introduction2. Related work3. AdaResampling4. Re-Regression Net4.1. Coarse detector4.2. Re-Regression 5. Experiments5.1. Data augmentation5.2. Network details5.3. Tra…

DP(区间DP)

目录 石子合并 合并果子&#xff08;贪心 Huffman树&#xff09; 环形石子合并 石子合并 设有 N 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻…

全文检索与日志管理 Elasticsearch(上)

一、Elasticsearch介绍 1.1 全文检索索引 Elasticsearch是一个全文检索服务器&#xff0c;全文检索是一种非结构化数据的搜索方式。 那么什么是结构化数据和非结构化数据呢&#xff1f; 结构化数据&#xff1a;指具有固定格式固定长度的数据&#xff0c;如数据库中的字段。 …

如何有效开展网络安全事件调查工作

网络安全事件调查是现代企业网络安全体系建设的关键组成部分。为了防止网络攻击&#xff0c;仅仅关注于安全工具的应用效果远远不够&#xff0c;因为安全事件一直都在发生。安全团队只有充分了解攻击者的行踪和攻击路径&#xff0c;才能更好地防范更多攻击时间的发生。 做好网…

基于Python爬虫+词云图+情感分析对某东上完美日记的用户评论分析

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

【go语言学习笔记】05 Go 语言实战

文章目录 一、 RESTful API 服务1. RESTful API 定义1.1 HTTP Method1.2 RESTful API 规范 2. RESTful API 风格示例3. RESTful JSON API4. Gin 框架4.1 导入 Gin 框架4.2 使用 Gin 框架4.2.1 获取特定的用户&#xff08;GET&#xff09;4.2.2 新增一个用户&#xff08;POST&am…

ElasticSearch安装与介绍

Elastic Stack简介 如果没有听说过Elastic Stack&#xff0c;那你一定听说过ELK&#xff0c;实际上ELK是三款软件的简称&#xff0c;分别是Elasticsearch、 Logstash、Kibana组成&#xff0c;在发展的过程中&#xff0c;又有新成员Beats的加入&#xff0c;所以就形成了Elastic…

9月大理,Move HackerHouse,成为全球数字游民的第一站

&#x1f680;世界各地的 hacker 们&#xff01;即日起&#xff0c;我们正式向您发出 co-buiding & co-living 的邀请&#xff01; 9.3日至9.24日&#xff0c;为期3周的 Move 主题Antalpha HackerHouse 将坐落于大理&#xff0c;邀请所有 Web3 开发者一起探索 Move 生态发…

基于Selenium模块实现无界面模式 执行JS脚本

此篇文章主要介绍如何使用 Selenium 模块实现 无界面模式 & 执行JS脚本(把滚动条拉到底部)&#xff0c;并以具体的示例进行展示。 1、Selenium 设置无界面模式 创建浏览器对象之前&#xff0c;创建 options 功能对象 &#xff1a;options webdriver.ChromeOptions() 添加…

微服务系列(2)--注册中心

在博文&#xff1a;微服务系列(1)里我们提到过注册中心的概念&#xff0c;简单来说微服务注册中心是一个用于存储和管理微服务实例信息的组件&#xff0c;它提供了服务注册、服务发现、服务健康检查等功能&#xff0c;以确保微服务之间的稳定通信。在微服务架构中&#xff0c;各…

Python 图形界面框架TkInter(第八篇:理解pack布局)

前言 tkinter图形用户界面框架提供了3种布局方式&#xff0c;分别是 1、pack 2、grid 3、place 介绍下pack布局方式&#xff0c;这是我们最常用的布局方式&#xff0c;理解了pack布局&#xff0c;绝大多数需求都能满足。 第一次使用pack&#xff08;&#xff09; import …

6. CSS(三)

目录 一、盒子模型 &#xff08;一&#xff09;网页布局的本质 &#xff08;二&#xff09;盒子模型组成 &#xff08;三&#xff09;边框&#xff08;border&#xff09; &#xff08;四&#xff09;表格的细线边框 &#xff08;五&#xff09;内边距&#xff08;padding…

Android多屏幕支持-Android12

Android多屏幕支持-Android12 1、概览及相关文章2、屏幕窗口配置2.1 配置xml文件2.2 DisplayInfo#uniqueId 屏幕标识2.3 adb查看信息 3、配置文件解析3.1 xml字段读取3.2 简要时序图 4、每屏幕焦点 android12-release 1、概览及相关文章 AOSP > 文档 > 心主题 > 多屏…

【数据结构】栈与队列

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

【Git】

Git 简介下载安装验证安装 简介 Git 是一个分布式版本控制系统&#xff0c;用于跟踪和管理软件开发项目的变化。它可以有效地记录文件的修改历史、协调多人协作开发、解决代码冲突&#xff0c;并提供了分支管理、版本回滚等功能&#xff0c;使团队能够更好地合作开发软件项目。…

Android实现超出固定行数折叠文字“查看全文“、“收起全文“

先上效果图 分析问题 网上有很多关于这个的代码&#xff0c;实现都过于复杂了&#xff0c;github上甚至还看到一篇文章600多行代码&#xff0c;结果一跑起来全是bug。还是自己写吧&#xff01;&#xff01;&#xff01; 如果我们需要换行的"查看全文"、"收起全…

8.14 作业 ARM

.text .globl _gcd_gcd:mov r0,#9mov r1,#15cmp r0,r1 比较r0和r1寄存器中的值beq stopsubhi r0,r0,r1subcc r1,r1,r0stop:b stop .end用for循环实现1~100之间和&#xff1a; .text .globl _start_start:mov r0,#0 总和mov r1,#1 从1开始mov r2,#100 到100结束bl add_loopa…

安装elasticsearch

一、docker安装elasticsearch 1、下载镜像 docker pull elasticsearch:6.5.4 2、启动容器 docker run -p 9200:9200 -p 9300:9300 --name elasticsearch \ -e "discovery.typesingle-node" \ -e "cluster.nameelasticsearch" \ -e "ES_JAVA_OPTS-Xm…

软件测试基础篇——Docker

1、docker技术概述 docker描述&#xff1a;docker是一项虚拟化的容器技术&#xff08;类似于虚拟机&#xff09;&#xff0c;docker技术给使用者提供一个平台&#xff0c;在该平台上可以利用提供的容器&#xff0c;对每一个应用程序进行单独的封装隔离&#xff0c;每一个应用程…

IC人必看| 模拟IC方向面试常考问题及答案汇总(二)

有不少小伙伴说还想要更多模拟IC方向的面试题目&#xff0c;这不就来了&#xff01;&#xff08;文末可领全部面试题目&#xff09; 1. Bandgap 里有几种反馈&#xff1f;原理是&#xff1f; 正反馈和负反馈。 2. 负反馈种类&#xff1f;负反馈的优点&#xff1f; 种类&am…