C ++ шаблонный вопрос относительно компараторов

Question

Вероятно, очень новый вопрос C ++. Скажем, у меня есть класс, вершина, с несколькими свойствами и методами. Я хочу поместить несколько вершин в очередь и упорядочить их по специальному свойству в классе вершин (выполнение основного алгоритма графа Дейкстры для школы да).

Однако у меня есть некоторые проблемы с проникновением в синтаксис C ++. Вот мой код (вершина не показана, но она довольно проста).

typedef std::priority_queue<benchmark::vertex*, 
                    std::vector<benchmark::vertex*>, 
                    std::less<benchmark::vertex*> > q_type;
q_type* q = new q_type();
benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1);
v1->cost = 4;
benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1);
v2->cost = 8;
benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1);
v3->cost = 6;
benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1);
v4->cost = 10;
benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1);
v5->cost = 2;
q->push(v1);
q->push(v2);
q->push(v3);
q->push(v4);
q->push(v5);
while (!q->empty()) {
    std::cout << (*(q->top())).cost << std::endl;
    q->pop();
}

Это выводит 2, 10, 6, 8, 4 на моей локальной машине. Я тестирую это на Linux-боксе с GCC (gcc версии 4.3.3 (Ubuntu 4.3.3-5ubuntu4)). Очевидно, я хочу, чтобы он выкладывал числа по порядку.

Как мне сделать компаратор, чтобы он смотрел и сравнивал vertex.cost при сравнении?

Answer 1

замените std::less<benchmark::vertex*> любой функцией или функтором, который принимает два указателя вершин в качестве параметров и возвращает true, если первый параметр принадлежит перед вторым.

std::less<benchmark::vertex*> собирается сравнить два указателя, поэтому результат, который вы видели, показывает их порядок в памяти.

Answer 2

std::less<benchmark::vertex*> сравнивает адреса, а не вершины

// Functor
struct VertexLess
{
   bool operator (const benchmark::vertex* left, const benchmark::vertex* right) const {
      return left->id < right->id;
   }
};

typedef std::priority_queue<benchmark::vertex*,     
                    std::vector<benchmark::vertex*>,
                    VertexLess > q_type;

Answer 3

Бонус внестабличной версии ответа Алексея Малистова:

template <class T, class M, const M T::*member>
struct MemberGenericDereferenceLess
{
    bool operator()(const T* lhs, const T* rhs) const
    {
        return ((*lhs).*member < (*rhs).*member);
    }
};

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                         int,
                                                         &benchmark::vertex::cost> > q_type;

Я подумал, что вам понадобятся только первый и третий параметры шаблона, но я не смог получить class M за несколько минут взлома. (упражнение для читателей)

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

namespace benchmark
{
    struct vertex
    {
        vertex(double a_, double b_) : a(a_), b(b_) {}

        double a;
        double b;

        int cost;
    };
}

Вы можете использовать сортировку typedef на a или b:

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                   double,
                                                   &benchmark::vertex::a> > q_type;

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                   double,
                                                   &benchmark::vertex::b> > q_type;

Вот небольшая программа для работы с драйвером:

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

namespace benchmark
{
    struct vertex
    {
        vertex(double a_, double b_) : a(a_), b(b_) {}

        double a;
        double b;

        int cost;
    };
}

template <class T, class M, const M T::*member>
struct MemberGenericDereferenceLess
{
    bool operator()(const T* lhs, const T* rhs) const
    {
        return ((*lhs).*member < (*rhs).*member);
    }
};

int main(int argc, char** argv)
{
    typedef std::priority_queue<benchmark::vertex*,
                                std::vector<benchmark::vertex*>,
                                MemberGenericDereferenceLess<benchmark::vertex,
                                                       int,
                                                       &benchmark::vertex::cost> > q_type;
    q_type q;

    benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1);
    v1->cost = 4;
    benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1);
    v2->cost = 8;
    benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1);
    v3->cost = 6;
    benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1);
    v4->cost = 10;
    benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1);
    v5->cost = 2;
    q.push(v1);
    q.push(v2);
    q.push(v3);
    q.push(v4);
    q.push(v5);
    while(q.empty() == false)
    {
        std::cout << q.top()->cost << std::endl;
        q.pop();
    }

    // Clean up all of those new()s
    delete v1;
    delete v2;
    delete v3;
    delete v4;
    delete v5;

    std::cin.get();

    return 0;
}