0

Edit: Yes I have made a mistake defining the comparator. I have changed the operator to <. The behavior is now defined and does not change.

I defined a simple comparator class

class MyCompare {
    public:
       bool operator()(int a, int b){
           return a < b;
      }
};

This returns true, and gives a more priority when it is smaller. When used as follow, it sorts the vector in ascending order, first element is the smallest.

However, when it is used in priority_queue, the top() element is the largest. I wonder why it is inversed in the priority_queue? What's the logic behind this?

When used in sort:

vector<int> v = {3,2,1};
sort(v.begin(), v.end(), MyCompare());
for (int i : v) {
    cout << to_string(i) << endl;
}

The result is:

1
2
3

When used in priority_queue：

priority_queue<int, vector<int>, MyCompare> pq;
pq.push(3);
pq.push(2);
pq.push(1);

while (!pq.empty()) {
   cout << pq.top() << " " << endl;
   pq.pop();
}

The result is:

3
2
1

I am expecting 1, 2, 3 as smaller element has higer priority I'm wondering why the effect is inversed?

DawnRising
  • 23
  • 2
  • 6
    [`std::priority_queue`](https://en.cppreference.com/w/cpp/container/priority_queue): *"Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare"* – Yksisarvinen Mar 15 '23 at 14:21
  • read about strict weak ordering. https://en.cppreference.com/w/cpp/named_req/Compare – 463035818_is_not_an_ai Mar 15 '23 at 14:22
  • Specifically, given two equal values `a` and `b`, your `MyCompare{}( a, b )` returns "true - `a` **must** be ordered before `b`". And `MyCompare{}( b, a )` returns "true - `b` **must** be ordered before `a`". That's impossible to satisfy. – Drew Dormann Mar 15 '23 at 14:24
  • @Yksisarvinen this: https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering ? – Jason Mar 15 '23 at 14:25
  • I have edited the code and imposed < comparisons. The behavior does not change. – DawnRising Mar 15 '23 at 14:25
  • 1
    Oh, come on. I asked about why sort and priority_queue behaviors are inversed. You closed my question with an answer about strict weak ordering. – DawnRising Mar 15 '23 at 14:28
  • 1
    @DawnRising -- You are comparing sorting with a data structure. See [std::make_heap](https://en.cppreference.com/w/cpp/algorithm/make_heap). You will see that a max-heap is created using `<`. – PaulMcKenzie Mar 15 '23 at 14:31
  • ***"Undefined behavior means anything can happen including but not limited to the program giving your expected output. But never rely(or make conclusions based) on the output of a program that has UB. The program may just crash."*** – Jason Mar 15 '23 at 14:32
  • 2
    @Jason If you read my earlier comments, I have adjusted the comparator to use `<`. The behavior is now defined. – DawnRising Mar 15 '23 at 14:34
  • 2
    See second comment, priority queue is defined as largest first. Is your question why the standard defines it this way? – teapot418 Mar 15 '23 at 14:36
  • @DawnRising -- The probable reason is that `operator <` is used throughout the STL containers for ordering purposes. If the container/data structure "naturally" puts larger items first, then that's what `<` will do. – PaulMcKenzie Mar 15 '23 at 14:37
  • Strict weak ordering is not a relevant dupe, but we have many relevant ones here. – Evg Mar 15 '23 at 16:33

1 Answers1

2

This simply how priority queue is defined, according to cppreference:

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

I presume, basic implementions rely on std::make_heap and related functions that also store maximal element in the front (by default).

ALX23z
  • 4,456
  • 1
  • 11
  • 18
  • 1
    Thanks for actually trying to answer the question. Since I defined a customized comparator that gives priority to smaller values. Why doesn't it become a min heap? When I changed the code to `return a>b`, which gives more priority to larger value, the `pq` is now a min heap. I'm confused why this is inversed. – DawnRising Mar 15 '23 at 14:45
  • 1
    @DawnRising why do you presume it gives higher priority to lesser elements? What you gave is equivalent to `std::lesser`, the default comparator. You need to give the equivalent of `std::greater` for lowest element to be in the front. – ALX23z Mar 15 '23 at 14:48
  • *When I changed the code to return a>b, which gives more priority to larger value,* -- This is not what it does. That's not the purpose of `operator <` with respect to `std::priority_queue`. – PaulMcKenzie Mar 15 '23 at 14:50
  • @ALX32z I assumed so because in my understanding a comparator returns true if `a` should come before `b`. I thought in priority queues 'come before' means be poped first. Is this a wrong interpretation of the comparator? – DawnRising Mar 15 '23 at 14:57
  • @DawnRising: you have the wrong interpretation of the priority queue. Priority queue puts the HIGHEST PRIORITY first. – Mooing Duck Mar 15 '23 at 15:07
  • 1
    @DawnRising whenewer C++ is asking you to supply a comparator, it is asking you to provide a less-than operation "a is (strictly) less than b". And the doc for priority queue is telling you that relative to this operation top is going to be the maximum element. – teapot418 Mar 15 '23 at 15:08
  • 1
    @DawnRising -- It seems you read too much into what the purpose of `operator <` is. Again, if the natural state of the data structure is highest goes first, then `operator <`, the default if no comparitor is specified, will build that data structure accordingly. It isn't going to do something opposite of what is expected. If you want a simpler example, look at [std::max_element](https://en.cppreference.com/w/cpp/algorithm/max_element) and how it uses `operator <` to determine the *maximum* element, not the minimum element. – PaulMcKenzie Mar 15 '23 at 15:09