I needed a mutable priority queue (the priorities can be changed) for my currect project, and started by simply wrapping a class around a std::vector and make/push/pop_heap. However, it is not nearly fast enough, profiling shows ~70% of processing time is spent in the queue. I need some input on how to either fix the queue, or if there already exists something which can do this but better (there is a mutable_queue in boost, but in the pending directory, for instance).template <typename ValueT, typename KeyT>class UnconsistentQueue {    struct Elem {        Elem(const ValueT& v_, const KeyT& p_) : v(v_), p(p_) {}        bool operator<(const Elem& rhs) const {             // Note that this is reversed, since we want a lowest-first prio queue            return rhs.p < p;         }        ValueT v;        KeyT p;    };public:    typedef typename std::vector<Elem>::iterator iterator;    typedef typename std::vector<Elem>::const_iterator const_iterator;    void push(const ValueT& v, const KeyT& p) {        q.push_back(Elem(v, p));        std::push_heap(q.begin(), q.end());    }    void update(const ValueT& v, const KeyT& p) {        update(v, p, q.begin());    }    void update(const ValueT& v, const KeyT& p, const_iterator hint) {        iterator i = q.begin();        if(hint->v == v)            std::advance(i, std::distance<const_iterator>(q.begin(), hint));        else {            for(; i != q.end(); ++i) {                if(i->v == v)                     break;            }        }        if(i != q.end()) {            i->p = p;            std::make_heap(q.begin(), q.end());        }    }    void pop() {        std::pop_heap(q.begin(), q.end());        q.pop_back();    }    const ValueT& top() const { return q.front().v; }    const KeyT& top_key() const { return q.front().p; }    const_iterator begin() const { return q.begin(); }    const_iterator end() const { return q.end(); }    const_iterator find(const ValueT& v) const {        const_iterator i;        for(i = q.begin(); i != q.end(); ++i) {            if(i->v == v)                break;        }        return i;    }    void remove(const ValueT& v) {        const_iterator i = find(v);        if(i != q.end()) {            q.erase(i);            std::make_heap(q.begin(), q.end());        }    }    bool empty() const { return q.empty(); }    void clear() { q.clear(); }private:    std::vector<Elem> q;};In my project, the key type is encoded in this struct:template <typename CostType>struct Key {    bool operator<=(Key<CostType> rhs) const {        return (k1 <= rhs.k1) || (k1 == rhs.k1 && k2 <= rhs.k2);    }    bool operator<(Key<CostType> rhs) const {        return (*this <= rhs) && !(rhs <= *this);    }    CostType k1;    CostType k2;};(The paper which defines the algorithm only defines a <= operator, but I need a strict weak ordering, so I implemented it like this. Good?)Below is the relevant part of the profiling results as generated by AMD CodeAnalystCS:EIP      Symbol + Offset                                                                                                                                                                                                                                                         64-bit  Timer samples   0xf156c0    Key<double>::operator<=                                                                                                                                                                                                                                                         14.45           0xf1c350    std::_Adjust_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                  7.29            0xf140d0    Key<double>::operator<                                                                                                                                                                                                                                                          6.91            0xf1d260    UnconsistentQueue<unsigned int,Key<double> >::Elem::operator<                                                                                                                                                                                                                   6               0xf1c250    std::_Push_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                    5.64            0xf15910    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator!=                                                                                              4.56            0xf16570    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator==                                                                                              4.27            0xf15160    UnconsistentQueue<unsigned int,Key<double> >::find                                                                                                                                                                                                                              4.01            0xf16130    std::vector<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> >::end                                                                                                                                        3.99            0xf1b0b0    std::_Make_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                    3.21            0xf16a90    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,             2.97            0xf15b50    std::_Tree<std::_Tmap_traits<unsigned int,double,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,double> >,0> >::_Lbound                                                                                                                                   2.93            0xf16540    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator++                                                                                              2.41            0xf1c240    std::_Move<UnconsistentQueue<unsigned int,Key<double> >::Elem &>                                                                                                                                                                                                                1.86            0xf16500    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator*                                                                                               1.81            15 functions, 408 instructions, Total: 120448 samples, 72.33% of shown samples, 32.53% of total session samples
Slow mutable priority queue
c++;performance
The standard already has a priority queue.std::priority_queueInternally it uses std::vector<> (by default) but the elements in the vector are organized into a binary tree structure for faster sorting and organization. (ie element 0 is the root, element 1,2 are children of 0 etc).If you want to do this manually you can your own container and the following methods:Push HeapPop HeapMake HeapSort HeapThe problem with the heap structure it only really supports removal of the head node. Once you start deleting nodes in the middle you need to re-build the heap manually (which seems to be your problem). According to the documentation re-building the map is linear (up-to 3n plus your linear traversal so 4n) so O(n).So it does not look like you really want a priority queue. What you really want to use is the std::map. This allows O(log(n)) insertion and deletion of elements anywhere in the map and the container is maintained in sorted order (using strict weak ordering). So you can iterate over the map in order if required.Also once elements are in the container there is no further copying of the elements. In the priority queue the elements were copied around the vector and if the copy construction of the key/value was expensive then other operation would suffer.Of course there will be a cost in using a map which is the extra memory  it will use (a vector is very efficient in terms of memory usage).