STL heap containing pointers to objects

Question

I have an std::list<MyObject*> objectList container that I need to sort and maintain in the following scenario:

• Each object has a certain field that supplies a cost (a float value for example). That cost value is used to compare two objects as if they were floating point numbers
• The collection must be ordered (ascending) and must quickly find the correct position for a newly inserted element.
• It is possible to delete the lowest element (in terms of cost) and it is also possible to update the cost of several arbitrarily positioned elements. The list must be then reordered as fast as possible, taking advantage of its already sorted nature.

Could I use any other stl container/mechanism to allow for the three behavioral properties? It pretty much resembles a heap and I thought using make_heap could be a good way to sort the list. I need to have a container of pointers, since there are several other data structures that rely on these pointers.

How then can I choose a better container that's also pointer friendly and allows sorting by looking at the comparison operators of the pointed types?

CLARIFICATION: I need an stl container that best fits the scenario and can successfully wrap pointers or references for that matter. (For example, I read briefly that the std::set container could be a good candidate, but I have no experience with it).

A current implementation, based on the below answers:

struct SHafleEdgeComparatorFunctor
    {
        bool operator()(SHEEdge* lhs, SHEEdge* rhs)
        {
            return (*lhs) < rhs;
        }
    };

std::multiset<SHEEdge*, SHafleEdgeComparatorFunctor>    m_edges;

Of course, the SHEEdge data structure has an overloaded operator:

bool operator<(SHEEdge* rhs) 
    {
        return this->GetCollapseError() < rhs->GetCollapseError();
    }

Answer 1

I would indeed use std::set. The tricky bit in your requirements is to update existing elements.

A std::set is always sorted. You will have to either wrap your pointers in a class with a useful compare operator or you have to pass a comparison predicate to the set.

Then you get the sorted property automatically and you get constant time removal of the lowest element.

You also get updating of the cost value in log complexity: Simply remove the object from the set and re-add it. This will be as fast as it can be for a sorted container.

Inserting, and deleting is fast in a set.

Answer 2

I'd start using a smart pointer like shared_ptr instead of a raw pointer (raw pointers are good e.g. if they are observing pointers, like pointers passed as function parameters, but when you have ownership semantics, like in this case, it's better to use a smart pointer).

Then, I'd start with std::vector as a container.

So, try make it vector<shared_ptr<MyObject>>.

You can measure performance of it compared to list<shared_ptr<MyObject>>.

(Note also that std::list has kind of more overhead than std::vector, since it's a node-based container, and each node has some overhead; instead std::vector allocates a contiguous chunk of memory to store its data, in this case the shared_ptrs; so std::vector is also more "cache-friendly", etc.)

In general, std::vector offers very good performance, and it's a good option as a "first choice" container. In any case, your mileage may very, and the best thing is to measure performance (speed) to get a better understanding in your particular case.