Priority queue of struct's pointers

c++, priority-queue, stl

Solution

There are multiple issues here.

When you define an operator inside a class, it automatically takes a parameter of the class type as its first argument, and you must not create a parameter for it. So you either keep the operator in the class, like so:

struct MI {
  bool operator< (const MI&);
};

or declare the operator as free-standing:

struct MI {
  //...
};
bool operator< (const MI&, const MI&);

Second, your `priority_queue` stores pointers to `MI`, not instances of `MI`, so the operator will not be called anyway. You must provide a comparator when defining the priority queue, like this (EDITED):

struct MyComparator {
  bool operator() (miasto_wsk arg1, miasto_wsk arg2) {
    return *arg1 < *arg2; //calls your operator
  }
};

int main() {
  priority_queue<miasto_wsk, vector<miasto_wsk>, MyComparator> q;
  //...
}

Third is just a style thing: I'd suggest you name the class directly `miasto` rather than making it just a `typedef`. It's more natural in C++.

Problem

I know that there are similar threads but after spending an hour trying to force my program to work, I decided to ask for a help. First of all. I've thought that I know c++ pretty well since I tried something which is very simple in PHP(programming language which I know best) but very complexed in c++ (at least very complexed for me). So I want to create priority_queue of struct's pointers. It's obvious that I need to create my own compare function. So I tried this code: ``` #include <iostream> #include <list> #include <queue> using namespace std; typedef struct MI { int nr; int koszt; bool operator<(const MI& a, const MI& b) { return a.koszt > b.koszt; } } miasto, *miasto_wsk; int main() { priority_queue<miasto_wsk> q; miasto_wsk mi; mi = new miasto; mi->nr = 1; mi->koszt = 2; q.push(mi); } ``` And when I tried to compile my program I ended up with compilation error: ``` test.cpp:11:44: error: ‘bool MI::operator<(const MI&, const MI&)’ must take exactly one argument ``` Can you explain me what I'm doing wrong and explain me how all this stuff with structs compare works(or give me a good tutorial/article which explains that from the beginning) EDIT: I changed my code to this: ``` #include <iostream> #include <list> #include <queue> using namespace std; typedef struct miasto { int nr; int koszt; } *miasto_wsk; bool myComparator(miasto_wsk arg1, miasto_wsk arg2) { return arg1->koszt < arg2->koszt; //calls your operator } int main() { priority_queue<miasto_wsk, vector<miasto_wsk>, myComparator> q; miasto_wsk mi; mi = new miasto; mi->nr = 1; mi->koszt = 2; q.push(mi); } ``` And now I getting this error msg: ``` test.cpp: In function ‘int main()’: test.cpp:19:64: error: type/value mismatch at argument 3 in template parameter list for ‘template<class _Tp, class _Sequence, class _Compare> class std::priority_queue’ test.cpp:19:64: error: expected a type, got ‘myComparator’ test.cpp:19:67: error: invalid type in declaration before ‘;’ token test.cpp:24:7: error: request for member ‘push’ in ‘q’, which is of non-class type ‘int’ ``` What is the problem? Maybe I should use copies of structs instead pointers to structs? EDIT2 This code doesn't produce any compilation errors: ``` #include <iostream> #include <list> #include <queue> using namespace std; typedef struct miasto { int nr; int koszt; bool operator< (const miasto& rhs) { koszt > rhs.koszt; } } *miasto_wsk; int main() { priority_queue<miasto_wsk> q; miasto_wsk mi; mi = new miasto; mi->nr = 1; mi->koszt = 22; q.push(mi); } ``` So @Angew idea seems to be wrong. EDIT3: This is my final code. It not only compile without errors but also doing exactly what I want. Thank you so much @Angew ``` #include <iostream> #include <list> #include <queue> using namespace std; typedef struct miasto { int nr; int koszt; } *miasto_wsk; struct MyComparator { bool operator() (miasto_wsk arg1, miasto_wsk arg2) { return arg1->koszt > arg2->koszt; //calls your operator } }; int main() { //priority_queue<miasto_wsk, vector<miasto_wsk>, myComparator> q; priority_queue<miasto_wsk, vector<miasto_wsk>, MyComparator> q; miasto_wsk mi; mi = new miasto; mi->nr = 1; mi->koszt = 22; q.push(mi); miasto_wsk mi1; mi1 = new miasto; mi1->nr = 2; mi1->koszt = 50; q.push(mi1); miasto_wsk mi2; mi2 = new miasto; mi2->nr = 3; mi2->koszt = 1; q.push(mi2); cout << q.top()->koszt << endl; q.pop(); cout << q.top()->koszt << endl; q.pop(); cout << q.top()->koszt << endl; q.pop(); } ```

Original source