从相同的结构体以相反的顺序创建两个优先级队列

Question

我已经得到了这个结构体:

struct Passenger
{
unsigned arrive;
unsigned depart;
};

现在我需要以相反的顺序创建A和B优先级队列。如果重载操作符<，它们的顺序将相同。

我想知道，如何使用相对比较器创建这些优先级队列?

Answer 1

您需要在创建优先级队列时指定比较器:

// For the moment, I'm specifying these to just compare arrival times.
// Modify that as needed.
struct GT {
    bool operator()(Passenger const &a, Passenger const &b) { 
       return b.arrive < a.arrive;
    }
};
struct LT { 
    bool operator()(Passenger const &a, Passenger const &b) { 
        return a.arrive < b.arrive;
    }
};
std::priority_queue<Passenger, std::vector<Passenger>, GT> max_heap;
std::priority_queue<Passenger, std::vector<Passenger>, LT> min_heap;

Answer 2

您可以为std::priority_queue指定一个比较器:

typedef std::priority_queue<Passenger, std::vector<Passenger>> min_queue;
typedef std::priority_queue<Passenger, std::vector<Passenger>, std::greater<Passenger>> max_queue;

,或者通用:

template <typename T, typename Container = std::vector<T>>
using min_queue = std::priority_queue<T, Container>;
template <typename T, typename Container = std::vector<T>>
using max_queue = std::priority_queue<T, Container,
        std::greater<typename Container::value_type>>;

然后:

min_queue<Passenger> my_min_queue;
max_queue<Passenger> my_max_queue;

Answer 3

我建议您查看boost::multi_index，然后您可以有一个可以以不同方式访问的单个集合

Answer 4

std::priority_queue有第二个和第三个模板参数:

• 第二个是底层容器，默认为std::vector
• 第三个是比较器类，如std::map和std::set

所以你不应该重载operator<，因为这不是直观的使用。相反，实现那些比较器:

struct ArriveLess {
  bool operator()(Passenger const& lhs, Passenger const& rhs)
  { return lhs.arrive < rhs.arrive; }
};
struct DepartLess {
  bool operator()(Passenger const& lhs, Passenger const& rhs)
  { return lhs.depart < rhs.depart; }
};
/* ... */
std::priority_queue<Passenger, std::vector<Passenger>, ArriveLess> A;
std::priority_queue<Passenger, std::vector<Passenger>, std::not<ArriveLess>> B;

Answer 5

您可以将"Compare"函数传递给优先队列模板:

std::priority_queue<Passenger> A;
std::priority_queue<Passenger, std::vector<Passenger>, reverse_compare> B;
bool Passenger::reverse_compare(const Passenger& rhs)
{
  return rhs < *this;    /* Note reverse order! */
}

编辑:以上假设乘客有一个正常的operator <。

我太慢了!)