Difference between std::set and std::priority_queue

Question

Since both std::priority_queue and std::set (and std::multiset) are data containers that store elements and allow you to access them in an ordered fashion, and have same insertion complexity O(log n), what are the advantages of using one over the other (or, what kind of situations call for the one or the other?)?

While I know that the underlying structures are different, I am not as much interested in the difference in their implementation as I am in the comparison their performance and suitability for various uses.

Note: I know about the no-duplicates in a set. That's why I also mentioned std::multiset since it has the exactly same behavior as the std::set but can be used where the data stored is allowed to compare as equal elements. So please, don't comment on single/multiple keys issue.

Answer 1

A priority queue only gives you access to one element in sorted order -- i.e., you can get the highest priority item, and when you remove that, you can get the next highest priority, and so on. A priority queue also allows duplicate elements, so it's more like a multiset than a set. [Edit: As @Tadeusz Kopec pointed out, building a heap is also linear on the number of items in the heap, where building a set is O(N log N) unless it's being built from a sequence that's already ordered (in which case it is also linear).]

A set allows you full access in sorted order, so you can, for example, find two elements somewhere in the middle of the set, then traverse in order from one to the other.

Answer 2

std::priority_queue allows to do the following:

1. Insert an element O(log n)
2. Get the smallest element O(1)
3. Erase the smallest element O(log n)

while std::set has more possibilities:

1. Insert any element O(log n) and the constant is greater than in std::priority_queue
2. Find any element O(log n)
3. Find an element, >= than the one your are looking for O(log n) (lower_bound)
4. Erase any element O(log n)
5. Erase any element by its iterator O(1)
6. Move to previous/next element in sorted order O(1)
7. Get the smallest element O(1)
8. Get the largest element O(1)