Updating a single value in a sorted data structure

I need a data structure that is able to:

1. Add one value
2. Get the lowest value
3. Update one value

I can achieve this using std::multiset, where the operations are imlemented as:

1. multiset::insert()
2. multiset::begi开发者_Python百科n()
3. first remove the item using multiset::erase() then add updated item using multiset::insert()

One thing I don't like with multiset is that an iterator is required to update an item. It would be nice if a pointer was enough.

I wonder if it would be better to use std::priority_queue, std heap algorithms or anything else for the operations required and how to do it. The first two operations are straightforward for the std::priority_queue or the heap algorithms, but the third operation (updating) is a problem. Are there any other structures that can be used? What are their performance benefits over multiset?

std::priority_queue will give you efficient insertions and lowest value queries, but updates will be slow. You can make updates efficient by storing pointers in both a PQ and a std::vector and using the vector to perform updates. To perform an update, mark the entry as stale and insert a new updated copy. Then when querying the lowest value, ignore stale entries.

It looks like multiset should have good characteristics for what you need.

You'll need to consider which operations need to be fastest. If update is relatively rare a priority_queue may be better. If you use the priority_queue one option to make the update faster is to simply mark the old item invalid (assuming you have a reference/pointer to it) and add the new item+reheapify. Then when you pull off the lowest item first make sure it hasn't been marked invalid before using it (else get the next lowest item). This technique is useful any time it's somewhat expensive to remove an item from a container.