Comparators in STL

Question

I am using struct minHeap to generate a min heap using priority_queue .And function comp to print numbers in reverse order using sort function given in STL . Now my doubt is that I can not use struct minHeap in function sort and can not use function comp in priorityQueue .

I feel that function of both struct minHeap and comp is similar. Please explain me when to use structs for comaprator and when to use normal functions to behave as comparators in STL ?

#include<iostream>
#include <queue>
#include <stdio.h>
#include<algorithm>
using namespace std;

struct minHeap
{
    bool operator()(const int a , const int b )
    {
        return a>b;
    }
};
bool comp(int a , int b)
{
    return a>b;
}

int main()
{
    priority_queue<int , vector<int> , minHeap > b;

    b.push(4);
    b.push(23);
    b.push(12);
    while(b.size()!=0)
    {
        cout << b.top() << " " ;
        b.pop();
    }
    cout<<"\n" ;
    int arr[] = {12,34, 112,12};
    sort(arr , arr+4  ,comp);

    for(int x= 0 ; x < 4 ; x++)
    {
        cout << arr[x] << " " ;
    }
}

Answer 1

What you are looking for in general is when to use functions or when to use functors.

The short answer is: Use a functor if and only if you need to retain state across multiple calls to the operator. For comparison functions this is usually not the case, but there are other instances of uses such as accumulators, averagers, min/max calculators, etc.

Another question that seems to cover similar ground and that may help you with more detail and some great references to external material: Comparison Functor Types vs operator<

As to passing an actual function to priority_queue - it's not that obvious but it is possible:

typedef bool(*CompareFunc)(float, float); // You need to have your function pointer 
                                          // type available
bool Compare(float i_lhs, float i_rhs)    // The actual compare function matching the 
  {                                       // CompareFunc type
  // Do your compare stuff here.
  }

...
std::priority_queue<float, std::vector<float>, CompareFunc> p(Compare);
// Tell priorityqueue you're passing a compare *function*, and pass the actual function
// as a parameter.

Answer 2

You can use a functor in sort(), no problem at all:

sort(arr , arr+4  ,minHeap());

Maybe your problem was that you were just using the class name (minHeap) instead of an instance of the functor. minHeap() is a call to the constructor, not to operator().

As for priority_queue, it is specified as follows:

template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;

Therefore, you need a class name (as opposed to an instance) for the third template argument. If you want to use a function, you must use a pointer to a function type as third template argument and then pass the function pointer in the constructor:

priority_queue<int , vector<int> , bool (*)(int a, int b) > b(&comp);