Очередь приоритетов C ++ с настроенным объектом - PullRequest
Новая
       25

Очередь приоритетов C ++ с настроенным объектом

0 голосов
/ 30 апреля 2018

Я пытаюсь понять, как работает компаратор для приоритетной очереди, я сделал несколько тестов:

Тест 1: создайте класс компаратора и используйте priority_queue<T, vector<T>, cmp>

Всегда отлично работает

Тест 2: 

struct test {
    int a = 0;
};

bool operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

int main() 
{
    priority_queue<test> pq;
}

Это работает как ожидалось.

Тест 3: Поместите тест 2 в класс 

class T{
    struct test {
        int a = 0;
    };

    bool operator<(const test& lhs, const test& rhs) {
        return lhs.a < rhs.a;
    }
};

Ошибка компиляции: 

'bool T::operator<(const T::test&, const T::test&)' must take exactly one argument

Похоже, что компилятор подумал, что я перегружал оператор <для класса T. Есть ли другие способы сделать это, если мне действительно нужно, чтобы классы были вложенными? </p>

Тест 4: оператор перегрузки <</p> 

struct test {
    int a = 0;
    bool operator<(const test& rhs) {
        return a < rhs.a;
    }
};

int main() 
{
    vector<test> v;
    sort(v.begin(), v.end());   // No error
    set<test> s;                // No error
    priority_queue<test> pq;    // Compiling error
}

Только priority_queue выдает ошибку: 

'passing 'const test*' as 'this' argument discards qualifiers'

Я не знаю, почему это работает для сортировки и установки, но не для приоритетной очереди.

Ответы [ 2 ]

0 голосов
/ 30 апреля 2018

Компаратор для priority_queue работает как для любого другого компаратора. Следует иметь возможность участвовать в выражении 

if (compare(element1, element2))

Реализация по умолчанию уменьшается до 

if (element1 < element 2) ....

То, что вы сделали в 3, привело к 

if ( tObject.operator<(anotherTObject, yetAnotherTObject))

Итак, ваш 

bool T::operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

действительно должен сравниваться с самим объектом, как 

bool T::operator<(const test& rhs) const {
    auto lhs = *this;
    return lhs.a < rhs.a;
}

Последнее const действует как const для первого аргумента в разумном ответе.

0 голосов
/ 30 апреля 2018

operator< должен принимать два аргумента, в то время как когда вы делаете его членом class T, он неявно получает this в качестве третьего аргумента, таким образом, ошибка в тесте 3: 

class T {
  bool operator<(const test& lhs, const test& rhs) { // error
    return lhs.a < rhs.a;
  }
};

Чтобы это исправить, определите operator< во вложенном test классе: 

class T {
public:
  struct test {
    int a = 0;
    friend bool operator<(const test& lhs, const test& rhs) {
      return lhs.a < rhs.a;
    }
  };
};

или в области имен.

А в Тесте 4 operator< должно быть const: 

struct test {
  int a = 0;
  bool operator<(const test& rhs) const {
    return a < rhs.a;
  }
};
...