Why does std::priority_queue return largest elements first but use std::less? [duplicate]

Question

Why does std::priority_queue return largest elements first (i.e. is a maximal priority queue) even though it uses std::less as the compare type?

This particularly confuses me when I want to create a minimal queue, which would be done by std::priority_queue<T, std::vector<T>, std::greater<T>>.

The priority queue is acting opposite to sort(), making things less consistent. If you sort() a vector using the greater comparator, then front() of the vector is your largest value. If you create a priority queue using greater then front is the smallest value. I realize a priority queue uses a heap, but I feel like there is a good reason for this.

If it were the other way around, it would probably confuse someone else. — juanchopanza
– juanchopanza, Commented Jun 25, 2017 at 21:07
So your custom type only has to provide less, and can use it for other containers as well, even implement greater by it. — Johannes Schaub - litb
– Johannes Schaub - litb, Commented Jun 25, 2017 at 21:14

Sergey Kalinichenko · Accepted Answer · 2017-06-25 21:19:40Z

This is done for consistency with historical implementations: many classes, such as std::map, and algorithms, such as std::sort, used less-than relation for their ordering functionality since the beginning of Standard Template Library, which later became C++ Standard Library.

Staying consistent across multiple classes and templates is important, because library users do not need to remember which comparison is default for what container or algorithm.

In my mind, the priority queue is acting opposite to sort(). If you give sort greater then front() is the largest value. If you give the priority queue greater() then front is the smallest value.

gsamaras · Accepted Answer · 2017-06-25 21:13:39Z

Because it was pretty natural to code, when using heap's methods?

Check a (simplified) possible implementation:

template <class T, class Container = std::vector<T>, class Compare = std::less<T> > class priority_queue { public: explicit priority_queue(const Container& c_ = Container(), const Compare& comp_ = Compare()) : c(c_), comp(comp_) { std::make_heap(c.begin(), c.end(), comp); } void push(const T& x) { c.push_back(x); std::push_heap(c.begin(), c.end(), comp); } void pop() { std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); } };

I understand what you say, but as juanchopanza said: "If it were the other way around, it would probably confuse someone else".

Collectives™ on Stack Overflow

Why does std::priority_queue return largest elements first but use std::less? [duplicate]

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related