ronakchauhan's blog

Need help with C++ STL & Dijkstra
By ronakchauhan, history, 9 years ago, In English

I understood why a priority queue is needed for Dijkstra's algorithm, but i have a doubt when it comes to the implementation.Here's one of the implementations I came across : https://gist.github.com/johngian/1821625/.

I donot understand why the following wouldn't work (here's my code for comparing)

struct comp {
    bool operator() (const pair<int, int> &a,  const pair<int, int> &b) {
        return a.second < b.second;
    }
};

and my code for defining the priority queue is priority_queue <pair<int, int>, comp> Q

Also, why did he (and almost all other implementations) have an additional vector while defining a priority queue? Something similar to this priority_queue <pair<int, int>, vector <pair<int, int> > , comp > Q;

Any help is greatly appreciated :)

Tags c++, stl
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The second class template parameter of priority_queue is the class of the underlying container for the priority_queue.

You can read more about priority_queue constructors here

Or you can just google it)

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Does this mean that a priority_queue is handled over a particular container rather than having its own container (unlike a standard queue) ??

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      then why does the following code work fine?

      #include <bits/stdc++.h>
using namespace std;
 
#define endl "\n"

int main() {
	ios_base :: sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	priority_queue <pair<char, int> > Q;
	Q.push(make_pair('r', 55));
	Q.push(make_pair('o' , 32));
	Q.push(make_pair('n' ,22));

	while(!Q.empty()) {
		pair <char, int> x = Q.top();
		cout << x.first << "  " << x.second << endl;
		Q.pop();	
	}
}

      it produces the following output as expected :

      r  55
o  32
n  22
      → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Does this mean that a priority_queue is handled over a particular container rather than having its own container

      yes

      (unlike a standard queue) ??

      no. queue is used on top of deque

      → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Yes, but you can set the type of the underlying container for queue too

      → Reply