0

I need to iterate over std::vector-based priority_queue. As many answers here suggest, I can inherit from priority_queue and access underlying container (std::vector in my case).

Is it guaranteed that priority_queue elements are stored starting from element 0 of the underlying vector and that vector size equals queue size?

PS. I am iterating regardless of priority, so I iterate: for (int i = 0; i < c.size(); ++i)...

Ranoiaetep
  • 5,872
  • 1
  • 14
  • 39
user2052436
  • 4,321
  • 1
  • 25
  • 46
  • 4
    If you want to iterate over a priority_queue then you probably don't actually want a priority queue. If you both need fast lookup of the largest element and also the ability to iterate, you should probably just use an `std::vector` and the [Heap operations](https://en.cppreference.com/w/cpp/header/algorithm#Heap_operations). – François Andrieux Jan 10 '22 at 20:55
  • @FrançoisAndrieux Every time I pop an element, I need to recompute something that depends on remaining elements (regardless of priority). So `priority_queue` with capability to iterate over elements would work fine for me. Though I agree, I can just use heap ops.. – user2052436 Jan 10 '22 at 20:57
  • FWIW, `for (int i = 0; i < c.size(); ++i)` can be replaced with `for (const auto& elem : c)` and you will loop through the whole vector without issue. That does not answer how the items are stored in the vector though. – NathanOliver Jan 10 '22 at 20:58
  • @user2052436 Does it actually work fine for you though? Isn't this question based on an uncertainty about whether or not it works? Edit : `std::vector` with heap functions is the same thing as an iterable priority queue, except you control the implementation details. – François Andrieux Jan 10 '22 at 21:01
  • @FrançoisAndrieux Yeah, I am starting to agree with your advice. The easiest is just to use heap ops... – user2052436 Jan 10 '22 at 21:04
  • 3
    I've never understood why the container was a **protected** data member. It should be private. There are no requirements whatsoever on how the priority queue uses that member. If you need to do things that are not part of the interface for `std::priority_queue` then `std::priority_queue` is not the right tool. Yes, you can sort of drive screws in with a hammer, but you really should use a screwdriver. – Pete Becker Jan 10 '22 at 21:09
  • Agreed. Someone at the Standard committee must have made a really good argument. That or someone screwed up and the mistake wasn't caught in time. – user4581301 Jan 10 '22 at 21:11
  • @user4581301 I think this feature is a sort of "escape hatch". I suspect the committee feared preventing users from doing something simply because the committee couldn't think of a use case for allowing it. Making it a protected member makes it technically feasible to do it, but strongly discourages its use in typical use cases. – François Andrieux Jan 10 '22 at 21:49

2 Answers2

3

In short, yes.

The standard [priqueue.members] defines the operators on a priority queue in terms of push/emplace/pop_back and heap operations. It is trivial to see that the size of the underlying container will be equal to the size of the priority queue, and that elements will be stored starting from the beginning of the container.

In fact, the standard even guarantees that the underlying container will be a heap as defined by the standard make_heap algorithm.

That said, it is likely worth considering whether or not priority_queue is the best solution for your problem if iteration is required.

konsolas
  • 1,041
  • 11
  • 24
2

Yes.

As part of the container adaptor library, the job of priority_queue is to provide an extended/modified/limited interfaces of existing containers.

The underlying container is implemented as a protected member c. .size() is implemented in terms of return c.size(), and .top() is implemented in terms of return c.front(). [priqueue.overview]

Similarly, construction, push, and pop are effectively the same as using std::make_heap, push_heap, and pop_heap directly onto the underlying c. [priqueue.cons], [priqueue.members]

More informations on ways to access the underlying c can be found here: Is there a way to access the underlying container of STL container adaptors?

Ranoiaetep
  • 5,872
  • 1
  • 14
  • 39