admin管理员组

文章数量:1623805

在用priority_queue时，我遇到了一些问题
（关于priority_queue的详细用法见C++优先队列)

定义：priority_queue<Type, Container, Functional>

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

写Huffman编码构造Huffman树时，我用到了优先队列：

class TreeNode {
private:
    char character;
    int weight;
    TreeNode*left;
    TreeNode*right;
public:
    TreeNode();
    TreeNode(char character, int weight);

    bool operator<(const TreeNode &rhs) const;
    bool operator>(const TreeNode &rhs) const;
    bool operator<=(const TreeNode &rhs) const;
    bool operator>=(const TreeNode &rhs) const;

    char getCharacter() const;
    int getWeight() const;
    TreeNode *getLeft() const;
    TreeNode *getRight() const;

    void setLeft(TreeNode *left);
    void setRight(TreeNode *right);
    void setWeight(int weight);
    void setCharacter(char character);
};

因为TreeNode类内我已经重载了比较运算符，因此在使用优先队列时我心安理得的直接把greater<TreeNode*>传了进去，即：

std::priority_queue<TreeNode*,std::vector<TreeNode*>,std::greater<TreeNode*>>priorityQueue;

预期这样写能够构造出一个根据TreeNode里以weight（权重）作比的最小堆

但事实上生成的Huffman树跟我预想的完全不一样，找了很久，才发现是这里出了问题。

其实这里传入的第三个参数根本没有起作用，因为我想定义的是TreeNode*类型的优先队列，但是我重载的比较运算符却是两个类对象的参数，因此编译器根本不知道两个类指针对象该怎么比，结果就是这个堆完全是随机生成的。

而重载运算符必须要求存在类对象，不能直接传入两个类指针参数比较，那该怎么办？
其实，第三个参数还有第二种用法，重写仿函数

struct cmp {
	bool operator()(TreeNode* a, TreeNode* b)const {
		return a->GetWeight() > b->GetWeight();
	}
};

自定义一个cmp类，作为第三个参数传入即可

priority_queue<TreeNode*, vector<TreeNode*>, cmp> queue;

（一个破问题浪费了两个小时）

本文标签： 自定义第三个参数priorityqueue

版权声明：本文标题：自定义类传入priority_queue时第三个参数的用法 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728896323a1178456.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。