priority queue implementation explanation

Question

I was reading Dijkstra's algorithm from the book competitive programming 1.In the implementation program they have written something like this :

#define pair<int,int> ii;
priority_queue< ii,vector<ii>,greater<ii> > pq ;

If we are taking an integer s as a source,the implementation shows to push pair (cost,source) like this (nodes are numbered from 1 to n) :

pq.push(ii(0,s)) ;

My question is we are pushing a pair of cost and node in the priority queue. But what the two other parameters (namely vector and greater ) are doing in the priority_queue declaration ?

priority_queue< ii,vector<ii>,greater<ii> > pq ;

I tried declaring something like :

priority_queue< ii > pq ;

And the code works (on those testcases I have tried) .

Can anyone tell me what they meant by the declaration :

priority_queue< ii,vector<ii>,greater<ii> > pq ;

And what is the difference between the upper declaration and

priority_queue< ii > pq ;

declaration ?

Answer 1

So the declaration of the template class is something like this:

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

There are supposed to be three template parameters. The first one, "T", is the type of the elements (ii in your case). The second parameter is what I called "underlying container". You see, priority_queue is an adaptor, i.e. it uses other containers in secret while presenting to you another set of operations. (You might want to look up "adaptor pattern" on wikipedia.) For performance considerations, you can tell the compiler what container it should use underneath. The classes, deque and vector from the standard library can be used. See here for the requirements for the container class.

Now, the comparator is something you use to define the ordering of your elements. It can either be a function pointer or a class with the bracket operator overloaded. It takes two arguments of your element type, and returns (bool) "true" if the first element should appear after the second in the queue. It's useful when you want to change the default order, or use some exotic ways to order your elements.

e.g. see below for a trivial example

struct car{
    car(double engine_displ):_engine_displ(engine_displ) {} 
    double _engine_displ;
};
bool cmp_cars(car one, car other){
    return one._engine_displ < other._engine_displ;
}
//..somewhere else
std::priority_queue<car, std::vector<car>, cmp_cars> pq;

the queue should then hold a std::vector-ful of cars sorted by engine displacement.

When there's something like class Container = vector<T> in the list of template arguments, the compiler filles in std::vector<T> for you when you don't say what your underlying container type is. That's why you can just say priority_queue<ii>; the compiler extends it to priority_queue<ii,vector<ii>,less<ii>>. In your example, the author of the book is explicitly using greater<ii>, so the queue should put the least element in front. It makes sense since in Dijkstra's algorithm, you're interested in the path that has the least cost. priority_queue<ii> uses less<ii> by default, so now the queue would put the path with the largest cose in front, which doesn't make sense.

As a side note, you might find that the code is actually typedef pair<int,int> ii. The #define directive tells the preprocessor to replace every pair<int,int> with "ii", which doesn't help at all. Typedef tells the compiler "ii" means pait<int,int>.