CODEWITHSUNDEEP
c++stlset
Kishore S
Kishore S

Reputation: 173

What is the role of greater <int> in set?

While declaring a set,

set <int, greater <int> > gquiz1;

why do we use greater <int>? What purpose does it serve?

Upvotes: 9

Views: 10834

Answers (4)

Kumawat Lalit
Kumawat Lalit

Reputation: 560

As an example of using greater in set, I think of this Monk and the Magical Candy Bags challenge on hackerEarth:

Our Monk loves candy! While taking a stroll in the park, he stumbled upon N Bags with candies. The i'th of these bags contains Ai candies.

He picks up a bag, eats all the candies in it and drops it on the ground. But as soon as he drops the bag, the number of candies in the bag increases magically! Say the bag that used to contain X candies (before eating), now contains [X/2] candies! ,where [x] is the greatest integer less than x (Greatest Integer Function).

Amazed by the magical spell, Monk can now have a lot more candies! But he has to return home in K minutes. In a single minute,Monk can consume all the candies in a single bag, regardless of the number of candies in it. Find the maximum number of candies that Monk can consume.

This question can be solved using a multiset and using greater<int>, as every time we need the maximum candy we remove that candy and need to find out the next maximum efficiently:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define nline "\n"
#define ll long long

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        multiset<ll,greater<ll>>s;
        for(int i=0;i<n;i++){
            ll a;
            cin>>a;
            s.insert(a);
        }
        ll candies=0;
        // auto it=s.begin();
        while(k>0){
            ll first=(*s.begin());
            candies+=first;
            ll p=floor(first/2);
            s.erase(s.begin());
            s.insert(p);
            k--;
        }
        cout<<candies<<endl;
    }
}

Upvotes: 0

Aashish Kumar
Aashish Kumar

Reputation: 1006

In set , default ordering of numbers is from low to high.

To make it high to low we have to use greater<int>.

Upvotes: 1

R Sahu
R Sahu

Reputation: 206637

std::set is a container that contains an ordered set of objects.

The ordering of the objects is determined by the second argument. By default, it is std::less<Key>. See the definition of std::set for additional details. However, you can override the default argument by using your own Compare type as the second argument, as you have done in your posted code.

E.g.

std::set<int> set1; // Use default compare class, std::less<int>
set1.insert(10);
set1.insert(5);
set1.insert(7);

The order of the objects in the above container will be 5, 7, and 10. The objects in the container are sorted in increasing orer.

If you use

std::set<int, std::greater<int>> set2;
set2.insert(10);
set2.insert(5);
set2.insert(7);

The order of the objects in the above container will be 10, 7, and 5. The objects in the container are sorted in decreasing orer.

Upvotes: 11

Gnawme
Gnawme

Reputation: 2399

The declaration of std::set looks like this:

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

The entry goes on to say:

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare.

By default, the key comparison is done using std::less, meaning that the incoming entry is inserted at the first position where it is less than the item in the set that it's being compared against.

In your example, insertion is being performed using the std::greater comparison, which will result in a set where the entries are sorted in an order opposite to the default case.

Upvotes: 2

Related Questions