1

我有这个结构：

struct Passenger
{
unsigned arrive;
unsigned depart;
};

现在我需要以相反的顺序创建一个 A 和一个 B priority_queue。如果我重载运算符<，它们将具有相同的顺序。

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

4

5 回答 5

1

您可以为 指定比较器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;
于 2013-03-06T14:41:03.230 回答
1

我建议您研究一下，boost::multi_index然后您可以拥有一个可以以不同方式访问的单一集合。

于 2013-03-06T14:42:09.360 回答
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;
于 2013-03-06T14:42:25.317 回答
1

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

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

所以你不应该重载an 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;
于 2013-03-06T14:45:50.867 回答
0

您可以将“比较”函数传递给优先级队列模板：

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 <乘客正常。

[而且我太慢了！]

于 2013-03-06T14:42:36.910 回答