c++ - 使用 struct 和 map 创建 priority_queue
问题描述
我有结构:
struct Node {
unsigned char symbol;
unsigned int freq;
Node* left;
Node* right;
Node(unsigned char _byte, int _freq)
: symbol(_byte), freq(_freq), left(nullptr), right(nullptr) {};
};
并且已经创建了这样的unordered_map
:
std::unordered_map<unsigned char, uint> freqs ={{'a',12}, {'b',122}};
我想要做的 - 是创建priority_queue
下一个方式:
- 为每一对创建新节点
freqs
priority_queue
从所有这些Node
s中创建。
到目前为止我尝试了什么:从地图创建矢量并尝试创建priority_queue:
bool nodeCompare(const Node* first, const Node* second){
return first->freq > second->freq;
}
typedef std::priority_queue<Node*,
std::vector<Node*>,
nodeCompare()> my_queue;
std::vector<Node*> node_vect;
std::unordered_map<byte, uint>::iterator it;
for (it = freqs.begin(); it != freqs.end(); ++it)
{
Node* new_node = new Node(it->first, it->second);
node_vect.push_back(new_node);
}
my_queue(node_vect.begin(), node_vect.end(), nodeCompare);
但这不起作用:typedef
构造错误:
函数“nodeCompare”不是类型名称
附加问题: 如果我以这种方式创建我的向量,也许有一些方法可以将节点推入 my_queue 而不创建额外的向量?
my_queue q;
std::vector<Node*> node_vect;
std::unordered_map<byte, uint>::iterator it;
for (it = freqs.begin(); it != freqs.end(); ++it)
{
Node* new_node = new Node(it->first, it->second);
node_vect.push_back(new_node);
//q.push(new_node); this doesn't work
}
解决方案
priority_queue 模板参数不期望一个函数,而是一个对象类型
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
所以只需将该函数包装到一个结构/类(Functor)中就可以了。
struct Comparator
{
bool operator()(const Node* first, const Node* second) const {
return first->freq > second->freq;
}
};
typedef std::priority_queue<Node*,
std::vector<Node*>,
Comparator> my_queue;
如果您想要 Node 结构中的 Comparator 只需创建一个内部结构
struct Node {
unsigned char symbol;
unsigned int freq;
Node* left;
Node* right;
Node(unsigned char _byte, int _freq)
: symbol(_byte), freq(_freq), left(nullptr), right(nullptr) {};
struct Comparator
{
bool operator()(const Node* first, const Node* second) const {
return first->freq > second->freq;
}
};
};
typedef std::priority_queue<Node*,
std::vector<Node*>,
Node::Comparator> my_queue;
my_queue queue(node_vect.begin(), node_vect.end());
推荐阅读
- zebra-printers - QZ 托盘打印 RAW 打印而不是实际条形码
- visual-studio-code - 在 VS Code 中更改颜色
- css - 网站部分的背景颜色与不同屏幕上视频的背景颜色不匹配的奇怪问题
- reactjs - 如果用户不使用 multer 选择文件,如何从表单数据中忽略“req.file.path”
- java - Spring boot 错误创建名为“entityManagerFactory”的 bean。是数据库问题吗?
- php - 如何用逗号将对象转换为字符串?
- laravel - 用户控制器不存在
- android - 如何从此 api 查询随机日期?
- sql - 如何在Oracle sql中将行转换为按多列分组的列
- mysql - Docker 撰写 - MySQL - MYSQL_ROOT_PASSWORD