C++ STL中的priority_queue emplace()

优先队列是一种容器适配器，特别设计使队列的第一个元素是队列中所有元素中最大或最小的。但在C++ STL中（默认情况下），最大的元素在队列的顶部。我们还可以通过在创建优先队列时简单地传递一个额外的参数来创建具有最小元素在顶部的优先队列。

priority_queue::emplace()

该函数用于将新元素插入到优先队列容器中，新元素将根据其优先级添加到优先队列中。它类似于push操作。不同之处在于emplace()操作可以避免不必要的对象复制。

时间复杂度：O(log n)

语法：

priorityqueuename.emplace(value)
参数：
要插入到优先队列中的元素作为参数传递。
结果：
将参数添加到优先队列的顶部位置。

示例：

Input  : mypqueue{5, 4};
         mypqueue.emplace(6);
Output : mypqueue = 6, 5, 4

Input  : mypqueue{};
         mypqueue.emplace(4);
Output : mypqueue = 4

注意： 在优先队列容器中，元素是按相反的顺序打印的，因为首先打印顶部，然后再移动到其他元素。

错误和异常

1.它具有强异常保证，因此，如果抛出异常，就不会进行任何更改。

2.参数应与容器的类型相同，否则会引发错误。

// 整数优先队列
// CPP program to illustrate
// Implementation of emplace() function
#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
    priority_queue<int> mypqueue;
    mypqueue.emplace(1);
    mypqueue.emplace(2);
    mypqueue.emplace(3);
    mypqueue.emplace(4);
    mypqueue.emplace(5);
    mypqueue.emplace(6);
    // 队列变为 1, 2, 3, 4, 5, 6
 
    // 输出优先队列
    cout << "mypqueue = ";
    while (!mypqueue.empty()) {
        cout << mypqueue.top() << " ";
        mypqueue.pop();
    }
 
    return 0;
}

输出

mypqueue = 6 5 4 3 2 1

// 字符优先队列
// CPP program to illustrate
// Implementation of emplace() function
#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
    priority_queue<char> mypqueue;
    mypqueue.emplace('A');
    mypqueue.emplace('b');
    mypqueue.emplace('C');
    mypqueue.emplace('d');
    mypqueue.emplace('E');
    mypqueue.emplace('f');
    // 队列变为 A, b, C, d, E, f
 
    // 输出优先队列
    cout << "mypqueue = ";
    while (!mypqueue.empty()) {
        cout << mypqueue.top() << " ";
        mypqueue.pop();
    }
 
    return 0}

输出

mypqueue = f d b E C A

// STRING PRIORITY QUEUE
// CPP program to illustrate
// Implementation of emplace() function
#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
int main()
{
    priority_queue<string> mypqueue;
    mypqueue.emplace("portal");
    mypqueue.emplace("computer science");
    mypqueue.emplace("is a");
    mypqueue.emplace("GEEKSFORGEEKS");
    // queue becomes portal, computer science,
    // is a, GEEKSFORGEEKS
 
    // printing the priority queue
    cout << "mypqueue = ";
    while (!mypqueue.empty()) {
        cout << mypqueue.top() << " ";
        mypqueue.pop();
    }
 
    return 0;
}

输出

mypqueue = portal is a computer science GEEKSFORGEEKS

应用：

给定一些整数，请使用emplace()将它们添加到优先级队列中，并找到优先级队列的大小。

输入：5, 13, 0, 9, 4
输出：5

算法
1. 逐个使用emplace()向优先级队列容器插入给定的元素。
2. 连续弹出优先级队列的元素，直到它变为空，并增加计数器变量。
3. 打印计数器变量。

// CPP program to illustrate
// Application of emplace() function
#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
    int c = 0;
 
    // Empty Priority Queue
    priority_queue<int> pqueue;
 
    // inserting elements into priority_queue
    pqueue.emplace(5);
    pqueue.emplace(13);
    pqueue.emplace(0);
    pqueue.emplace(9);
    pqueue.emplace(4);
 
    // Priority queue becomes 13, 9, 5, 4, 0
 
    // Counting number of elements in queue
    while (!pqueue.empty()) {
        pqueue.pop();
        c++;
    }
    cout << c;
}

输出

emplace()与push()的区别

当我们使用push()时，会创建一个对象，然后将其插入优先级队列。而使用emplace()，该对象将原地构造，节省了不必要的副本。请参阅empace vs insert in C++ STL以了解详情。

// C++ code to demonstrate difference between
// emplace and insert
#include<bits/stdc++.h>
using namespace std;
   
int main()
{
    // declaring priority queue
    priority_queue<pair<char, int>> pqueue;
       
    // using emplace() to insert pair in-place
    pqueue.emplace('a', 24);
       
    // Below line would not compile
    // pqueue.push('b', 25);   
       
    // using push() to insert pair
    pqueue.push(make_pair('b', 25));   
       
    // printing the priority_queue
    while (!pqueue.empty()) {
        pair<char, int> p =  pqueue.top();
        cout << p.first << " "
             << p.second << endl;
        pqueue.pop();
    }
   
    return 0;
}