Home > Net >  How to clear a `priority_queue` that uses user-defined compare?
How to clear a `priority_queue` that uses user-defined compare?

Time:09-06

How to clear a priority_queue that uses user-defined compare?

From std::priority_queue documentation, I reduced the use of priority_queue to the case I need (= queue with user-defined compare)

>> cat test.cpp 
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
#include <utility>

auto queue_cmp = [](std::pair<int, double> const& lhs,
                    std::pair<int, double> const& rhs) {
    return lhs.second > rhs.second; // Custom order.
};
typedef std::priority_queue<std::pair<int, double>,
                            std::vector<std::pair<int, double>>,
                            decltype(queue_cmp)> custom_queue;

template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    int s = 0;
    while(!q.empty()) {
        std::pair<int, double> elem = q.top();
        std::cout << s << ": " << elem.first << ", " << elem.second << std::endl;
        q.pop();
        s  ;
    }
    std::cout << '\n';
}

int main() {
    custom_queue q(queue_cmp);
    for (int n = 10; n < 20; n  ) {
        double val = static_cast <double>(rand())/(static_cast<double>(RAND_MAX));
        q.push(std::pair<int, double>(n, val));
    }
    print_queue(q);
    //q = custom_queue(queue_cmp);
}

This runs OK

>> g   -o test test.cpp 

>> ./test 
0: 15, 0.197551
1: 18, 0.277775
2: 16, 0.335223
3: 11, 0.394383
4: 19, 0.55397
5: 17, 0.76823
6: 12, 0.783099
7: 13, 0.79844
8: 10, 0.840188
9: 14, 0.911647

Now I need to reset q so, following priority queue clear method, I uncomment the last line in test.cpp... And get this compilation error as if I get this correctly, copy constructors are deleted on lamdba:

>> g   -o test test.cpp 
test.cpp: In function ‘int main()’:
test.cpp:34:31: error: use of deleted function ‘std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >& std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >::operator=(std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >&&)’
   34 |     q = custom_queue(queue_cmp);
      |                               ^
In file included from /usr/include/c  /12/queue:64,
                 from test.cpp:2:
/usr/include/c  /12/bits/stl_queue.h:498:11: note: ‘std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >& std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >::operator=(std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double> >, <lambda(const std::pair<int, double>&, const std::pair<int, double>&)> >&&)’ is implicitly deleted because the default definition would be ill-formed:
  498 |     class priority_queue
      |           ^~~~~~~~~~~~~~
/usr/include/c  /12/bits/stl_queue.h:498:11: error: use of deleted function ‘<lambda(const std::pair<int, double>&, const std::pair<int, double>&)>&<lambda(const std::pair<int, double>&, const std::pair<int, double>&)>::operator=(const<lambda(const std::pair<int, double>&, const std::pair<int, double>&)>&)’
test.cpp:7:19: note: a lambda closure type has a deleted copy assignment operator
    7 | auto queue_cmp = [](std::pair<int, double> const& lhs,
      |                   ^

Is there a way to reset q in this case?

EDIT


bool queue_cmp(std::pair<int, double> const& lhs,
               std::pair<int, double> const& rhs) {
    return lhs.second > rhs.second; // Custom order.
};


Doesn't help

CodePudding user response:

Not in C 17.

C 20 gives capture-less lambdas a default constructor. But in earlier language versions, the constructor is deleted.

Really, you should not be using a lambda. Just use a named struct.

CodePudding user response:

As noted above in C 17 capture-less lambdas do not have default constructor.
Since a lambda is actually an anonymous class with a operator() method, you can use a named struct for the same purpose.

Your comparator will become:

struct queue_cmp
{
    bool operator()(std::pair<int, double> const& lhs, std::pair<int, double> const& rhs) const
    {
        return lhs.second > rhs.second; // Custom order.
    };
};

The rest of the code is almost the same.
You need to drop the decltype because queue_cmp is already a type, and there's no need to supply an instance of the comparator when constructing a queue:

typedef std::priority_queue<std::pair<int, double>,
    std::vector<std::pair<int, double>>,
    queue_cmp> custom_queue;


template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    int s = 0;
    while (!q.empty()) {
        std::pair<int, double> elem = q.top();
        std::cout << s << ": " << elem.first << ", " << elem.second << std::endl;
        q.pop();
        s  ;
    }
    std::cout << '\n';
}

int main() {
    custom_queue q;
    for (int n = 10; n < 20; n  ) {
        double val = static_cast <double>(rand()) / (static_cast<double>(RAND_MAX));
        q.push(std::pair<int, double>(n, val));
    }
    print_queue(q);
    q = custom_queue{};
}

Demo: https://godbolt.org/z/7eq86r915.

  • Related