Простой способ изменить алфавитный порядок сортировки в C++ std::priority_queue?

Question

Привет, я решаю некоторые проблемы с алгоритмом сортировки.

Я использую C++ STL priority_queue с заголовком очереди STL для сортировки ввода строки в обратном алфавитном порядке с некоторыми целыми числами.

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

#include <queue>

priority_queue<int> pq;
int arr[5] = {4,3,2,1,5};

for(int i = 0; i < 5; i++)
   pq.push(-arr[i]);
while(!pq.empty()) {
   cout << -pq.top() << endl;
   pq.pop();
}
//the result may be 1, 2, 3, 4, 5

или я могу реализовать это, используя оператор меньше

priority_queue<int, vector<int>, less<int>> pq;
int arr[5] = {4,3,2,1,5};

for(int i = 0; i < 5; i++)
   pq.push(arr[i]);
while(!pq.empty()) {
   cout << pq.top() << endl;
   pq.pop();
}
//the result may be 1, 2, 3, 4, 5

проблема в том, что я использую сложную структуру данных, как это

priority_queue<pair<int, pair<int, pair<int, string>>>> pq;

Я знаю, что могу решить эту проблему с перегрузкой оператора priority_queue.

Но есть ли простой и достойный способ реализовать обратный алфавитный порядок без такой перегрузки операторов?

Answer 1

Вы никогда не должны использовать такую ​​сложную структуру данных, используя вложенные пары в реальном коде. Это делает код сложным для понимания. Что такое pq.top().second.second.first?

Если ваша структура сложная, то определите структуру с желаемыми членами, такими как это (но с осмысленными именами членов):

struct datastructure
{
    int member1;
    int member2;
    int member3;
    std::string member4;
};

Затем вы должны определить оператор сравнения. Это всего лишь несколько строк кода, и это делает ваш код более читабельным. Это может быть вложенным struct Если вы предпочитаете...

struct datastructure_comp
{
    bool operator()(const datastructure &lhs, const datastructure &rhs) const
    {
        return lhs.member1 < rhs.member2;
    }
};

Насколько я знаю, если вы просто хотите изменить порядок вашей сложной структуры данных, вы можете использовать std::greater вместо по умолчанию std::less (при условии, что все поля должны сравниваться в обратном порядке, а не только в первом).

Ну, если вы хотите по-прежнему использовать пары для простоты, то вы можете сделать что-то вроде этого:

class datastructure 
{
    std::pair<int, std::pair<int, std::pair<int, string>>>> data;

public:
    int GetValue1() const { return data.first; }
    void SetValue1(int value) { data.first = value; }

    // other access function here...
};

И тогда определение сравнения будет тривиальным:

struct datastructure_comp
{
    bool operator()(const datastructure &lhs, const datastructure &rhs) const
    {
        return lhs.data > rhs.data; // reversed sort...
    }
};