ARTICLE AD BOX
I would like to know how to keep an ordered set of fractions (form of p/q), while maintaining the use of its operations order_of_key and find_by_order, on other fractional inputs. (By ordered set, I am referring to the Policy-Based Data Structure in g++ that keeps unique elements in sorted order: https://www.geeksforgeeks.org/cpp/ordered-set-gnu-c-pbds/.)
Example:
ordered_set = {2/5, 2/3, 3/4, 3/2, 5/3, 2/1}Upon running the operations, you would get:
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/5I tried making a "Fraction" Class, and a custom comparator, as you would for a normal set. However, it shows as a compilation error that the ordered set only accepts one argument, while I am trying to give it 2.
My implementation for the Ordered Set:
#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>;My Fraction Class and Custom Comparator:
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); } };My Attempt to make a Ordered Set sort by a Custom Comparator:
ordered_set<Fraction, cmp> os;Error Shown:
error: wrong number of template arguments (2, should be 1)Is there another way to sort the ordered set with regards to fractions?
