如何根据条件对优先级队列使用不同的比较器
How to use different comparators for a priority queue depending on conditions
我正在处理一项任务,我有一个优先队列,我希望它像这样工作:
if(field == '0')
priority_queue<record_t*,vector<record_t*>, CompareRecordID > pq;
else if(field == '1')
priority_queue<record_t*,vector<record_t*>, CompareRecordNum > pq;
else if(field == '2')
priority_queue<record_t*,vector<record_t*>, CompareRecordStr > pq;
else if(field == '3')
priority_queue<record_t*,vector<record_t*>, CompareRecordNumStr > pq;
其中 record_t 是:
typedef struct {
unsigned int recid;
unsigned int num;
char str[STR_LENGTH];
bool valid; // if set, then this record is valid
int blockID; //The block the record belongs too -> Used only for minheap
} record_t;
这意味着,根据函数参数字段,队列将"sort" record_t 的不同字段。但是,我不能在 if 语句中声明队列,因为它显然会给我一个错误 "pq was not declared in this scope"。我能做什么?
A priority_queue 可以将比较器作为构造函数参数。
std::priority_queue<record_t*,vector<record_t*>, CompareRecord > pq((CompareRecord(field)));
您只需要适当地定义 CompareRecord 比较器。一个简单的方法是:
struct CompareRecord{
char type;
CompareRecord(char type):type(type){}
bool operator()(const record_t* lhs, const record_t* rhs){
switch(type){
case '1': return lhs->recid < rhs->recid;
.. and so forth.
}
}
您可以使用将比较对象作为参数的 std::priority_queue
构造函数。然后你可以像这样给它一个可配置的比较器:
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
const int STR_LENGTH = 20;
struct record_t
{
unsigned int recid;
unsigned int num;
char str[STR_LENGTH];
bool valid; // if set, then this record is valid
int blockID; //The block the record belongs too -> Used only for minheap
};
// switchable priority comparator
struct CompareRecord
{
int field;
CompareRecord(int field = 0): field(field) {}
bool operator() (const record_t* lhs, const record_t* rhs) const
{
switch(field)
{
case 0: return lhs->recid < rhs->recid;
case 1: return lhs->num < rhs->num;
case 2: return std::strcmp(lhs->str, rhs->str) < 0;
}
return true;
}
};
int main()
{
// physical records
std::vector<record_t> records;
record_t r;
r.recid = 1;
r.num = 1;
std::strcpy(r.str, "banana");
records.push_back(r);
r.recid = 2;
r.num = 4;
std::strcpy(r.str, "orange");
records.push_back(r);
r.recid = 3;
r.num = 2;
std::strcpy(r.str, "apple");
records.push_back(r);
// input priority type: 0, 1 or 2
int field;
std::cout << "Sort type [0, 1, 2]: " << std::flush;
std::cin >> field;
std::cout << '\n';
// build priority view
CompareRecord cmp(field);
std::priority_queue<record_t*, std::vector<record_t*>, CompareRecord> pq(cmp);
for(auto& r: records)
pq.push(&r);
while(!pq.empty())
{
std::cout << "rec: " << pq.top()->recid << '\n';
std::cout << "num: " << pq.top()->num << '\n';
std::cout << "str: " << pq.top()->str << '\n';
std::cout << '\n';
pq.pop();
}
}
输出:
Sort type [0, 1, 2]: 0
rec: 3
num: 2
str: apple
rec: 2
num: 4
str: orange
rec: 1
num: 1
str: banana
我正在处理一项任务,我有一个优先队列,我希望它像这样工作:
if(field == '0')
priority_queue<record_t*,vector<record_t*>, CompareRecordID > pq;
else if(field == '1')
priority_queue<record_t*,vector<record_t*>, CompareRecordNum > pq;
else if(field == '2')
priority_queue<record_t*,vector<record_t*>, CompareRecordStr > pq;
else if(field == '3')
priority_queue<record_t*,vector<record_t*>, CompareRecordNumStr > pq;
其中 record_t 是:
typedef struct {
unsigned int recid;
unsigned int num;
char str[STR_LENGTH];
bool valid; // if set, then this record is valid
int blockID; //The block the record belongs too -> Used only for minheap
} record_t;
这意味着,根据函数参数字段,队列将"sort" record_t 的不同字段。但是,我不能在 if 语句中声明队列,因为它显然会给我一个错误 "pq was not declared in this scope"。我能做什么?
A priority_queue 可以将比较器作为构造函数参数。
std::priority_queue<record_t*,vector<record_t*>, CompareRecord > pq((CompareRecord(field)));
您只需要适当地定义 CompareRecord 比较器。一个简单的方法是:
struct CompareRecord{
char type;
CompareRecord(char type):type(type){}
bool operator()(const record_t* lhs, const record_t* rhs){
switch(type){
case '1': return lhs->recid < rhs->recid;
.. and so forth.
}
}
您可以使用将比较对象作为参数的 std::priority_queue
构造函数。然后你可以像这样给它一个可配置的比较器:
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
const int STR_LENGTH = 20;
struct record_t
{
unsigned int recid;
unsigned int num;
char str[STR_LENGTH];
bool valid; // if set, then this record is valid
int blockID; //The block the record belongs too -> Used only for minheap
};
// switchable priority comparator
struct CompareRecord
{
int field;
CompareRecord(int field = 0): field(field) {}
bool operator() (const record_t* lhs, const record_t* rhs) const
{
switch(field)
{
case 0: return lhs->recid < rhs->recid;
case 1: return lhs->num < rhs->num;
case 2: return std::strcmp(lhs->str, rhs->str) < 0;
}
return true;
}
};
int main()
{
// physical records
std::vector<record_t> records;
record_t r;
r.recid = 1;
r.num = 1;
std::strcpy(r.str, "banana");
records.push_back(r);
r.recid = 2;
r.num = 4;
std::strcpy(r.str, "orange");
records.push_back(r);
r.recid = 3;
r.num = 2;
std::strcpy(r.str, "apple");
records.push_back(r);
// input priority type: 0, 1 or 2
int field;
std::cout << "Sort type [0, 1, 2]: " << std::flush;
std::cin >> field;
std::cout << '\n';
// build priority view
CompareRecord cmp(field);
std::priority_queue<record_t*, std::vector<record_t*>, CompareRecord> pq(cmp);
for(auto& r: records)
pq.push(&r);
while(!pq.empty())
{
std::cout << "rec: " << pq.top()->recid << '\n';
std::cout << "num: " << pq.top()->num << '\n';
std::cout << "str: " << pq.top()->str << '\n';
std::cout << '\n';
pq.pop();
}
}
输出:
Sort type [0, 1, 2]: 0
rec: 3
num: 2
str: apple
rec: 2
num: 4
str: orange
rec: 1
num: 1
str: banana