Приоритетная очередь указателей на структуры

Я знаю, что есть подобные темы, но, потратив час на то, чтобы заставить мою программу работать, я решил обратиться за помощью. Прежде всего. Я думал, что знаю С++ довольно хорошо, так как я пробовал что-то очень простое в PHP (язык программирования, который я знаю лучше всего), но очень сложный в С++ (по крайней мере, очень сложный для меня). Итак, я хочу создать priority_queue указателей структуры. Очевидно, что мне нужно создать свою собственную функцию сравнения. Итак, я попробовал этот код:

#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);
}

И когда я попытался скомпилировать свою программу, я получил ошибку компиляции:

test.cpp:11:44: error: ‘bool MI::operator<(const MI&, const MI&)’ must take exactly one argument

Можете ли вы объяснить мне, что я делаю неправильно, и объяснить мне, как все эти вещи со сравнением структур работают (или дать мне хороший учебник/статью, которая объясняет это с самого начала)

ИЗМЕНИТЬ:

Я изменил свой код на это:

#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);
}

И теперь я получаю это сообщение об ошибке:

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’

В чем проблема? Может быть, мне следует использовать копии структур вместо указателей на структуры?

ИЗМЕНИТЬ2

Этот код не вызывает ошибок компиляции:

#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);
}

Так что идея @Angew кажется ошибочной.

EDIT3: это мой окончательный код. Он не только компилируется без ошибок, но и делает именно то, что я хочу. Большое спасибо @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();
}

person ghi    schedule 07.11.2012    source источник
comment
Вы правы, я неправильно прочитал документы по priority_queue. Я отредактировал свой ответ.   -  person Angew is no longer proud of SO    schedule 07.11.2012


Ответы (4)


Здесь есть несколько проблем.

Когда вы определяете оператор внутри класса, он автоматически принимает параметр типа класса в качестве своего первого аргумента, и вы не должны создавать для него параметр. Таким образом, вы либо сохраняете оператор в классе, например:

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

или объявить оператора автономным:

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

Во-вторых, ваш priority_queue хранит указатели на MI, а не экземпляры MI, поэтому оператор все равно вызываться не будет. Вы должны указать компаратор при определении приоритетной очереди, например (ОТРЕДАКТИРОВАНО):

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;
  //...
}

В-третьих, это просто стиль: я бы посоветовал вам назвать класс напрямую miasto, а не просто typedef. Это более естественно в C++.

person Angew is no longer proud of SO    schedule 07.11.2012

Ошибка, если вы прочитаете ее еще раз, говорит вам, что именно не так: функция MI::operator< должна принимать только один аргумент вместо двух.

Если у вас есть operator< в классе (как у вас), то функция принимает только один аргумент, и это другой объект, с которым нужно сравнить this. Если вы создаете operator< как самостоятельную функцию (т. е. не являющуюся частью класса), она должна принимать два аргумента.

person Some programmer dude    schedule 07.11.2012

Ваш оператор сравнения является функцией-членом, поэтому он должен принимать только один параметр для RHS:

bool operator<(const MI& rhs) {
      koszt > rhs.koszt;
}

Другой вариант - объявить его как функцию, не являющуюся членом:

struct MI {};

bool operator<(const MI& a, const MI& b) {
      return a.koszt > b.koszt;
}
person juanchopanza    schedule 07.11.2012

Используйте ключевое слово друга, чтобы поместить оператор ‹ в глобальную область видимости.

typedef struct MI
{
    int nr;
    int koszt;
    friend bool operator<(const MI& a, const MI& b) 
    {
      return a.koszt > b.koszt;
    }
} miasto, *miasto_wsk;
person pogorskiy    schedule 07.11.2012
comment
1. Это самый простой способ решить проблему. 2. Данная нотация позволяет объединить 'оператор ‹' в единый интерфейс, т.е. является предпочтительным - person pogorskiy; 07.11.2012
comment
Для меня это выглядит как злоупотребление friend. Кроме того, я бы считал, что функция не-друга, не являющаяся членом, является частью интерфейса. Интересное чтение здесь. PS Кстати, я не минусовал. - person juanchopanza; 07.11.2012
comment
Вы можете найти такое использование ключевого слова friend в стандартной библиотеке C++. Например, в ‹tr2/bool_set› (библиотека GNU ISO C++): class bool_set { friend bool_set operator!(bool_set __b) { return __b._M_not(); } }; - person pogorskiy; 07.11.2012
comment
В случае bool_set это имеет смысл, потому что _M_not() является частным, поэтому friend действительно необходим. - person juanchopanza; 07.11.2012