Custom ordering for std::priority_queue

Question

I'm trying to make a program that has a std::priority_queue of objects. I want the queue to order the objects based on A::num. This is the code:

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

class A {
  public:
    int num;
    A (int n) {
        this->num = n;
    }
    ~A() {
        std::cout << "Deleting an A\n";
    }
};

struct Compare {
  bool operator()(const A* first, const A* second) {
      return first->num < second->num;
  }  
};

int main() {
    std::priority_queue AContainer(A*, std::vector<A*>, Compare);
    
    AContainer.push(new A(4));
    AContainer.push(new A(8));
    AContainer.push(new A(6));
    
    while (AContainer.size() < 0) {
        A* del = AContainer.top();
        delete del;
        del = nullptr;
        AContainer.pop();
    }
    return 0;
}

The compiler returns an error, however I'm not sure why or where it is referring to, or how to fix it:

error: deduced class type 'priority_queue' in function return type
   24 |     std::priority_queue AContainer(A*, std::vector<A*>, Compare);
      |                         ^~~~~~~~~~
In file included from /usr/include/c++/11/queue:64,
                 from /tmp/HvPOYonaOt.cpp:3:
/usr/include/c++/11/bits/stl_queue.h:456:11: note: 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue' declared here
  456 |     class priority_queue
      |           ^~~~~~~~~~~~~~

If you could help me out with this that would be great.

Raw pointers with manual new/delete should be used very rarely. Anyway the proper syntax of the with the error should be: `std::priority_queue, Compare> AContainer;`. — wohlstad, Feb 09 '23 at 14:24

score 1 · Accepted Answer · answered Feb 09 '23 at 14:24

1

A*, std::vector<A*>, Compare are types that you need to supply to the template parameters of std::priority_queue, not values you supply to a constructor.

std::priority_queue<A*, std::vector<A*>, Compare> AContainer;

See it on coliru

answered Feb 09 '23 at 14:24

Caleth

52,200
2
44
75

I believe you still have to pass the comparator as a parameter, as just the type alone does not suffice. – sweenish Feb 09 '23 at 14:25
2

Only if comparator is not default constructable. – Marek R Feb 09 '23 at 14:26
or if it is function pointer as it needs to know which function to point to. – NathanOliver Feb 09 '23 at 14:28
I feel so stupid because that is such a simple solution that I completely missed. – farnz Feb 09 '23 at 14:37
@MarekR I cannot find that requirement; and I am logically having a tough time imagining a world where the type alone is sufficient. – sweenish Feb 09 '23 at 14:43
1

https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue see overload (1). – Marek R Feb 09 '23 at 14:48
@sweenish do you make a point of passing instances of `std::vector` and `std::less` to your `std::priority_queue`s? – Caleth Feb 09 '23 at 14:52
So, I don't. But this seems more to rely on goodwill than anything else for a custom comparator. And in the instances where I've used a lambda, the compiler complained if I didn't pass the actual lambda as a parameter. Maybe I'm just overthinking it. – sweenish Feb 09 '23 at 14:57
@MarekR I missed that in my quick skim. Thank you. – sweenish Feb 09 '23 at 14:58

score 1 · Answer 2 · edited Feb 09 '23 at 14:31

1

Alternative fix using C++17 Class template argument deduction:

std::priority_queue AContainer{Compare{}, std::vector<A*>{}};

Which is closer to your example.

https://godbolt.org/z/547Tq1EnY

edited Feb 09 '23 at 14:31

NathanOliver

171,901
28
288
402

answered Feb 09 '23 at 14:30

Marek R

32,568
6
55
140

wohlstad · Answer 3 · 2023-02-09T14:45:32.763

In this line you use invalid syntax for instantiating a templated class:

std::priority_queue AContainer(A*, std::vector<A*>, Compare);

The proper syntax is:

std::priority_queue<A*, std::vector<A*>, Compare> AContainer;

Having written this, in modern c++ it is recommended to avoid using raw pointers with manual new/delete whenever possible.
If you can simply store A instances this would be the simplest solution.
If you need pointers (e.g. for using polymorphism, which is not shown in your question), you can use smart pointers, e.g. std::unique_ptr:

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

class A {
public:
    int num;
    A(int n) {
        this->num = n;
    }
    ~A() {
        std::cout << "Deleting an A\n";
    }
};

struct Compare {
    bool operator()(std::unique_ptr<A> const & first, std::unique_ptr<A> const & second) {
        return first->num < second->num;
    }
};

int main() {
    std::priority_queue<std::unique_ptr<A>, std::vector<std::unique_ptr<A>>, Compare> AContainer;

    AContainer.push(std::make_unique<A>(4));
    AContainer.push(std::make_unique<A>(8));
    AContainer.push(std::make_unique<A>(6));

    while (AContainer.size() > 0) {
        AContainer.pop();
    }
    return 0;
}

Note that you don't have to new or delete any object manually.

A side note: I think you have a typo in your while condition - while (AContainer.size() < 0) should be while (AContainer.size() > 0).

Custom ordering for std::priority_queue

3 Answers3