Clever Geek Handbook

Which heap structure uses the C ++ STL queue priority?

In particular, which variant of the heap does the STL priority queue container container use? I am comparing this to my own hand rolled into a binary heap and two implementations of the basket structure, so just curious. Bonus points for any interesting implementation knowledge!

+3


source to share


2 answers


This question is marked as C ++ (as opposed to asking for specific details for a specific specific compiler), so I checked the standard for any information. In the various sections 23.6.4 we learn that it priority_queue

just behaves like this: if it uses make_heap

, push_heap

and pop_heap

. These functions are then documented (in sections 25.4.6

) as having complexity At most 3 * (last - first) comparisons.

, At most log(last - first) comparisons.

and At most 2 * log(last - first) comparisons.

so on. Thus, certain characteristics of the heap can be specified by these characteristics, but no particular heap is called.



+9


source


You can select the container underlying the priority_queue. If not specified, std :: vector is used by default:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;


Container - The type of base container that will be used to store items. The container must satisfy the SequenceContainer requirements. In addition, it must provide the following functions with the usual semantics: front () push_back () pop_back () standard containers std :: vector and std :: deque satisfy these requirements.

The heap is implemented by functions *_heap

, in a simple way. You can check the code here:   http://www.sgi.com/tech/stl/stl_heap.h

-2


source






More articles:


All Articles