CODEWITHSUNDEEP
c++c++11
Shihao Xu
Shihao Xu

Reputation: 1200

C++ - how to copy elements from std::priority_queue to std::vector

For example, I want to pick out the k-th largest elements from a input vector.

I know it can be better done with QuickSelect std::nth_element.

My question is how to copy the underlying container std::vector of std::priority_queue to another vector, rather than solve this coding problem.

priority_queue<int, vector<int>, greater<int>> pq;
for (int num : nums) {
    pq.push(num);
    if (pq.size() > k) {
        pq.pop();
    }
}

My way is stupid:

vector<int> res;
while (!pq.empty()) {
    res.push_back(pq.top());
    pq.pop();
}

Is there better way to do it?

Can we do it like

vector<int> res = pq;

The top k elements do not need to be ordered.

Upvotes: 15

Views: 20909

Answers (3)

Quuxplusone
Quuxplusone

Reputation: 27005

The data member c of priority_queue is protected, which means only derived classes can access it. You can write an extractable_priority_queue like this:

template<class PQ>
class Extractable : public PQ {
public:
    using PQ::PQ;
    using typename PQ::container_type;
    container_type&& container() && { return std::move(this->c); }
    const container_type& container() const & { return this->c; }
    container_type& container() & { return this->c; }

    container_type sorted_container() && {
        std::sort_heap(this->c.begin(), this->c.end(), this->comp);
        return std::move(this->c);
    }
};

And then:

Extractable<std::priority_queue<int, std::vector<int>, std::greater<int>>> pq;
for (int num : nums) {
    pq.push(num);
    if (pq.size() > k) {
        pq.pop();
    }
}
std::vector<int> res = std::move(pq).container();

If you need the top k items to be sorted (which you've said you don't), then:

std::vector<int> res = std::move(pq).sorted_container();

Would it be nicer to write

template<class T, class Container, class Comparator>
class ExtractablePriorityQueue :
    public std::priority_queue<T, Container, Comparator> {

? Quite possibly, for some use-cases. In my case I'm optimizing only for the amount of typing I have to do to implement it. :)

Upvotes: 2

Johan Lundberg
Johan Lundberg

Reputation: 27038

No, you can't access all elements of a priority_queue without popping. There's also no built in way to move the elements out, but there is a way, using const cast. For integers it is surely not worth it, but imagine the type be expensive to copy. The trick is safe as long as pq is not itself in const storage (that is, declared const to begin with), which should be rare for priority queue. 

vector<int> res;
while (!pq.empty()) {
  res.push_back(std::move(const_cast<int&>(pq.top())));
  pq.pop();
}

Upvotes: 7

Shihao Xu
Shihao Xu

Reputation: 1200

You could use vector<int> at the beginning.

And treat this vector as heap, with std::make_heap, std::push_heap, std::pop_heap.

That way, you can copy the vector.

Upvotes: 8

Related Questions