我们如何使用STL的priority_queue
来处理结构体?
请举一个例子说明如何在结构体中有多种数据类型时进行推送和弹出操作。
比如,假设我们有这样一个结构体:struct thing { int a; char b;} glass[10];
,现在我们想要按照其中的'int a'对其进行排序并放入优先队列中,该怎么做呢?
我们如何使用STL的priority_queue
来处理结构体?
请举一个例子说明如何在结构体中有多种数据类型时进行推送和弹出操作。
比如,假设我们有这样一个结构体:struct thing { int a; char b;} glass[10];
,现在我们想要按照其中的'int a'对其进行排序并放入优先队列中,该怎么做呢?
这是对您原来的问题,您无缘无故删除了稍加修改后的答案。原始内容已经包含了足够的信息让您能够理解,但以下是具体步骤:提供一个使用int
进行比较的小于比较。
你需要做的就是提供一个实现严格弱序的小于比较的函数对象,或者为实现相同功能的类提供一个小于运算符。以下结构体可以满足要求:
struct thing
{
int a;
char b;
bool operator<(const thing& rhs) const
{
return a < rhs.a;
}
};
那么
std::priority_queue<thing> q;
thing stuff = {42, 'x'};
q.push(stuff);
q.push(thing{4242, 'y'}); // C++11 only
q.emplace(424242, 'z'); // C++11 only
thing otherStuff = q.top();
q.pop();
为 thing
重载 <
运算符:
struct thing
{
int a;
char b;
bool operator<(const thing &o) const
{
return a < o.a;
}
};
priority_queue<thing> pq;
thing t1, t2, t3;
// ...
pq.push(t1);
pq.push(t2);
// ...
t3 = pq.top();
pq.pop();
结构中的优先队列可以通过两种方式实现:
让我们以一个名为 car 的结构为例,该结构具有模型和价格两个整数,并基于最高价格构建优先队列。
struct Car
{
int m;
int p;
void set(int a,int b){
m =a,p = b;
}
};
对于方法1,我们需要这样做:
bool operator < (const Car& c1,const Car& c2){
return c1.p < c2.p;
}
对于方法2,我们需要传递这个结构:
struct Cmp{
bool operator()(const Car& c1,const Car& c2){
return c1.p < c2.p;
}
};
完整的代码示例:
#include <iostream>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
using namespace std;
struct Car
{
int m;
int p;
void set(int a,int b){
m =a,p = b;
}
};
struct Car cT[50];
int cI=0;
void printC(){
for(int i=0;i<cI;i++){
cout <<" car model: " << cT[i].m << " price: " <<cT[i].p <<endl;
}
}
bool operator < (const Car& c1,const Car& c2){
return c1.p < c2.p;
} //Method 1
struct Cmp{
bool operator()(const Car& c1,const Car& c2){
return c1.p < c2.p;
}
}; //Method 2
void pushQ(priority_queue<Car,vector<Car>,Cmp>& Q){
for(int i=0;i<cI;i++){
Q.push(cT[i]);
cout <<"Queue Push car model: " << cT[i].m << " price: " <<cT[i].p <<endl;
}
};
void printQ(priority_queue<Car,vector<Car>,Cmp> Q){
while(!Q.empty()){
Car c = Q.top();
Q.pop();
cout <<" car model: " << c.m << " price: " <<c.p <<endl;
}
}
int main() {
// Write C++ code here
// priority_queue<Car> Q; // #Method 1
priority_queue<Car,vector<Car>,Cmp> Q;// #Method 2
cT[cI++].set(4,5);
cT[cI++].set(34,4);
cT[cI++].set(43,6);
cT[cI++].set(41,15);
pushQ(Q);
printQ(Q);
// printC();
// cout << "Hello world!" <<f1;
return 0;
}
输出将是:
car model: 41 price: 15
car model: 43 price: 6
car model: 4 price: 5
car model: 34 price: 4
你可以像这样做!
struct example{
int height;
int weight;
};
struct comp{
bool operator()(struct example a, struct example b){
//Sorting on the basis of height(Just for example)
return (a.height > b.height);
}
};
// And here comes your priority queue
priority_queue<struct example, vector<struct example>, comp> pq;
struct example your_obj;
pq.push(your_obj);
q.push(thing{42, 'x'})
或q.emplace(42, 'x')
。如果您没有C ++ 11支持,则需要给thing
一个构造函数。 - juanchopanza