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] << " " ;
}
}
Comparator Classes are used to compare the objects of user-defined classes. In order to develop a generic function use template, and in order to make the function more generic use containers, so that comparisons between data can be made.
In electronics, a comparator is a device that compares two voltages or currents and outputs a digital signal indicating which is larger. It has two analog input terminals and and one binary digital output .
By default std::set uses the operator < for comparing two elements and but if user passes the external sorting criteria i.e. comparator then it uses it instead of default operator < .
Custom Comparator are used to compare the objects of user-defined classes. The above comparator function comp() take two pair of objects at a time and return true if data members of the two operators are the same. There can be any condition as per the need of the problem in the comparator function.
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.
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);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With