cpp stl::priority queue using 2 keys not sorting correctly

Question

I have defined a struct as follows:

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

};

And am trying to use the STL priority queue class to sort the persons in ascending order according to id and sort values with matching id's lexicographically according to country of origin. Below is my code:

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

}

The output that I get is:

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

Instead of:

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

Why is this the case?

Answer 1

You can make this a lexicographical compare by ordering on the first field and, only if they are equal, then testing the second field to break the tie. It should work if rewrite your comparator as follows:

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

Another method is to use std::tie, it's more concise and correctly does the lexicographical compare:

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