[boost] Dynamic Priority Queues

From: Reid Sweatman (reids_at_[hidden])
Date: 1999-06-22 18:39:06

I hope this isn't too off-topic for this list, but I was wondering whether
anyone had given any thought to (or knew of an implementation of) a dynamic
priority queue template.  By DPQ, I mean a priority queue in which items
committed to the queue can change priority before being popped off the
queue.  If I can't turn any such thing up, I'll do one based on reworking
the SGI STL priority queue adaptor.  Looks like all it really needs is
random access, and maybe a scheme for optimizing things where
reprioritization occurs considerably more often than popping (since the STL
priority queue is *supposed* to be heap-based, you'd want to limit heap
rebuilds in such a case).

This kind of structure comes up all the time in LRU mechanisms, and I've
rolled app-specific ones myself several times in the past.  But it would be
nice to have a generic solution and not have to mess with it again.  If I
end up writing my own, and can get my company to consider it public domain,
I'll submit it here.  But I was sort of hoping someone might know of one
that's already done.

------------------------------------------------------------------------

eGroups.com home: http://www.egroups.com/group/boost
http://www.egroups.com - Simplifying group communications