What does greater<pair<int,int>> do actually?

user_18346953 0
Viewed 477

I have encountered this greater<pair<int,int>> in many codes. For example, in the initialisation of the priority queue [code below]

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

I tried a lot of googling but still couldn't find the best answer.

c++17 c++
2 Answers

This is the std::greater type.

This is a function object type that does comparisons using the > operator. A rough implementation looks like this:

template<typename T>
struct greater {
    constexpr auto operator()(T const& a, T const& b) const -> bool {
        return a > b; // greater operator
    }
};

In your example, this is being used to order the std::pairs in the priority_queue from "smallest" to "largest" using std::pair's operator >.

user_21046970

The std::greater is a template function object defined as:

template<typename T> struct greater {
    constexpr bool operator()(T const& a, T const& b) const {
        return a > b; // greater operator
    }
};

Now, the '>' operator is defined for std::pair as -

template <class T1, class T2>
  bool operator>  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)    { return rhs<lhs; }

Now, the '<' operator is defined as-

template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

So, effectively, the function greater<pair<int, int>> works as-

template<typename T> struct greater {
        constexpr bool operator()(T const& a, T const& b) const {
            return a.first>b.first || ( (a.first<b.first) && (a.second>b.second));
        }
    };

That is, greater<pair<int, int>>(a, b) returns true if and only if the 'first' parameter of a is greater than b or if 'first' parameters are equal then 'second' parameter of a is greater than b. This is a strict weak ordering.

user_164302680
Related