How do I construct an instance of std::priority_queue from a Container object without an explicit Compare object?

user_2520359 0
Viewed 62

As per cppreference, std::priority_queue is defined as a template of three arguments, T, Container and Compare, out of which the last two have default values based on T:

class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>

Now let's say that I'm very happy with these defaults, and want to construct an std::priority_queue<int> object from an existing std::vector<int> one.

The closest I can have is

priority_queue(const Compare& compare, Container&& cont);

which move-constructs the underlying container using cont and then heapifies it by calling std::make_heap.

It's all great, but I would have to explicitly provide a Compare object, i.e.

std::vector<int> vec;
// filling vec with values
std::priority_queue<int> pq{std::less<int>(), std::move(vec)};

Why doesn't std::priority_queue have constructors like

priority_queue(const Container& cont);
priority_queue(Container&& cont);

It only seems reasonable, as it has a comparator-only constructor:

explicit priority_queue(const Compare& compare)
: priority_queue(compare, Container()) { }

Or am I missing some other way to do it?

priority-queue stl c++
1 Answers

I think your requirement is reasonable and I was considering the use case too, but sadly the STL doesn't support it. Then we can consider making our own wrapper: We just inherit the priority_queue, and make a cast:

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

template <typename T, typename Seq = std::vector<T>,
          typename Cmp = std::less<typename Seq::value_type>>
class MyPriorityQueue : public std::priority_queue<T, Seq, Cmp> {
 public:
  using base_t = std::priority_queue<T, Seq, Cmp>;
  MyPriorityQueue() = default;
  template <typename Cont>
  MyPriorityQueue(Cont&& cont) : base_t(Cmp{}, std::move(cont)) {}
  template <typename Cont>
  MyPriorityQueue(const Cont& cont) : base_t(Cmp{}, cont) {}
};

template <typename Cont, typename T = typename Cont::value_type,
          typename Seq = std::vector<T>,
          typename Cmp = std::less<typename Seq::value_type>>
std::priority_queue<T, Seq, Cmp> MakePriorityQueue(Cont&& cont) {
  return std::priority_queue<T, Seq, Cmp>(
      MyPriorityQueue<T, Seq, Cmp>(std::move(cont)));
}

template <typename Cont, typename T = typename Cont::value_type,
          typename Seq = std::vector<T>,
          typename Cmp = std::less<typename Seq::value_type>>
std::priority_queue<T, Seq, Cmp> MakePriorityQueue(const Cont& cont) {
  return std::priority_queue<T, Seq, Cmp>(MyPriorityQueue<T, Seq, Cmp>(cont));
}
template <typename T, typename Seq = std::vector<T>,
          typename Cmp = std::less<typename Seq::value_type>>
std::priority_queue<T, Seq, Cmp> MakePriorityQueue() {
  return std::priority_queue<T, Seq, Cmp>(MyPriorityQueue<T, Seq, Cmp>());
}

The usage would be clean:

  std::vector<int> vec;
  auto pq = MakePriorityQueue(std::move(vec));

Online demo

user_12927910
Related