C++: Why priority queue has no back() function?

yapkm01 0
Viewed 97

According to the cppreference website on priority_queue:

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of LegacyRandomAccessIterator. Additionally, it must provide the following functions with the usual semantics:
front()
push_back()
pop_back()
The standard containers std::vector and std::deque satisfy these requirements.

and "C++ Primer, 5th Edition" by Stanley Lipmann:

q.back() Only valid for queue

Since cppreference states that priority_queue (container adaptor) requires front(), push_back() and pop_back(), why is q.back() only valid for queue and not for priority_queue? If you look at cppreference for priority_queue, there's no function back() for it.

priority-queue data-structures c++
1 Answers

priority_queue keeps the elements in a partially sorted state. The point of the structure is that it allows you to pull elements out in sorted order. Since the elements are only partially sorted the back() is not well defined. To maintain a back() pointer additional storage, or a different data structure would be required. Since this is typically not needed the standard opted for the simpler implementation.

If you try to do this with an array or vector, the naive approach is O(N) per insertion(find the right position then shift all larger values one place), while the priority_queue keeps it a O(logN). If you have all the elements from the start, putting them in a vector and sorting is better (there are less swaps and could have better cache consistency compared to priority_queue, on average, but they are both O(NlogN)).

If you really need back() look for a min-max heap.

Sorin0
Related