cpp stl :: приоритетная очередь, использующая 2 ключа, неправильно сортирующая - PullRequest
Новая
       25

cpp stl :: приоритетная очередь, использующая 2 ключа, неправильно сортирующая

0 голосов
/ 01 ноября 2018

Я определил структуру следующим образом: 

using namespace std; 
struct Person {
    int id; 
    int age; 
    string country_of_origin; 

};

И я пытаюсь использовать класс очереди приоритетов STL для сортировки людей в порядке возрастания по идентификатору и сортировки значений с лексикографически совпадающими идентификаторами в соответствии со страной происхождения. Ниже мой код: 

#include <queue> 
#include <vector> 
#include <iostream>
#include <queue>
#include <string> 

using namespace std; 
struct Person {
    int id; 
    int age; 
    string country_of_origin; 

};

struct PersonCompare
{
    bool operator()(const Person &p1, const Person &p2) const
    {
        if (p1.id>p2.id) {
            return true; 
        } else if (p1.country_of_origin>p2.country_of_origin){
            return true; 
        }  else {
            return false; 
        }
    }
};




int main(int argc, char ** argv)
{
    Person p={1,2,"Zimbabwe"}; 
    Person q={3,4,"New Zealand"};
    Person r={5,7,"Wales"}; 
    Person s={2,3,"India"};
    Person t={1,4,"Sri Lanka"}; 
    Person u={1,4,"Benin"}; 
    priority_queue<Person,vector<Person>,PersonCompare> queue;
    queue.push(p); 
    queue.push(q); 
    queue.push(r); 
    queue.push(s); 
    queue.push(t); 
    queue.push(u);
    while (!queue.empty())
    {
        Person p = queue.top();
        cout << p.id << "\t"<<p.age<<"\t"<<p.country_of_origin<<endl;  
        queue.pop();
    }

}

Вывод, который я получаю: 

1       4       Benin
2       3       India
3       4       New Zealand
1       4       Sri Lanka
1       2       Zimbabwe
5       7       Wales

Вместо: 

1       4       Benin
1       4       Sri Lanka
1       2       Zimbabwe
2       3       India
3       4       New Zealand
5       7       Wales

Почему это так?

1 Ответ

0 голосов
/ 01 ноября 2018

Вы можете сделать это лексикографическим сравнением, упорядочив по первому полю и, , только если они равны , затем протестировав второе поле, чтобы разорвать связь. Это должно работать, если переписать ваш компаратор следующим образом: 

struct PersonCompare
{
    bool operator()(const Person &p1, const Person &p2) const
    {
        if (p1.id > p2.id) {
            return true; 
        } else if (p1.id < p2.id) {
            return false;
        }
        return p1.country_of_origin > p2.country_of_origin;
    }
};

Другой метод заключается в использовании std::tie, он более лаконичен и правильно выполняет лексикографическое сравнение: 

#include <tuple>

struct PersonCompare
{
    bool operator()(const Person &p1, const Person &p2) const
    {
        return std::tie(p1.id, p1.country_of_origin) > std::tie(p2.id, p2.country_of_origin);
    }
};
...