如何在C++中实现支持分数的Policy-Based有序集合？

我需要在C中维护一个分数（p/q形式）的有序集合，同时保留order_of_key和find_by_order操作，能对外部输入的分数执行这些操作。这里的有序集合指G的基于策略的数据结构（Policy-Based Data Structure），用于存储有序的唯一元素。

示例：

ordered_set = {2/5, 2/3, 3/4, 3/2, 5/3, 2/1}

执行操作后结果：

ordered_set.order_of_key(2/3) = 2
ordered_set.order_of_key(1/2) = 1

ordered_set.find_by_order(1) = 3/4
ordered_set.find_by_order(0) = 2/5

我尝试定义了Fraction类和自定义比较器（类似普通set的写法），但编译报错，提示有序集只接受1个模板参数，我传了2个。

我的有序集合定义代码：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

Fraction类和自定义比较器：

struct Fraction {
    int n;
    int d;
};

struct cmp{
    bool operator()(const Fraction &x, const Fraction &y) const {
        return (x.n * y.d) < (x.d * y.n);
    }
};

我尝试创建带自定义比较器的有序集合：

ordered_set<Fraction, cmp> os;

错误信息：

error: wrong number of template arguments (2, should be 1)

请问有没有办法让有序集合对分数正确排序？

问题出在你定义的ordered_set模板只接受1个参数，而你想传入比较器作为第二个参数，不符合模板定义。有两种可行的解决方法：

方法1：修改ordered_set模板，支持自定义比较器 #

把原有的ordered_set模板改成支持传入比较器参数的版本，就能指定自定义的cmp：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

// 新增比较器模板参数，默认使用less<T>
template<class T, class Compare = less<T>> 
using ordered_set = tree<T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

之后即可用自定义比较器创建有序集合：

ordered_set<Fraction, cmp> os;

方法2：为Fraction重载<运算符 #

不需要额外的比较器结构体，直接在Fraction里重载<运算符，让原有的ordered_set模板（依赖less<T>）能正确比较分数：

struct Fraction {
    int n;
    int d;

    // 重载<运算符，实现分数的大小比较
    bool operator<(const Fraction& other) const {
        // 注意：实际使用时要确保分母不为0，此处需额外判断
        return (long long)n * other.d < (long long)d * other.n;
    }
};

然后直接用原模板创建集合即可：

ordered_set<Fraction> os;

注意事项 #

• 分数比较时，n*d可能超出int的范围，建议转成long long避免溢出。
• 实际使用时要确保分母不为0，最好在Fraction的构造函数中加入合法性检查。

内容的提问来源于stack exchange，提问作者TLE on test 77