Re: Prioritized_Set<>
wade@stoner.com wrote:
Le Chaud Lapin wrote:
3. There must be a 1-to-1 mapping of elements to their corresponding
priorities.
4. There must be a 1-to-n mapping of priorities to their corresponding
9. Elements of identical priority become highest priority according to
a FIFO model.
I need all operations to run in O[log(n)], or better, actual time.
a) Is there already a data structure that satisfies these constraints?
Sure, just make your internal priority be
make_pair<priority, fifo_index>
where fifo_index is a counter, big enough to avoid overflow over the
lifetime of your application. Anything that handles 1-8 will, with
minor modifications, handle 9 also.
This is what other suggested, which leads be to revert to my original
plan, after spending four days in heap-land. When all these operations
are provided using conventional priority-queue schemes (binary heaps,
binomial heaps, Fibonacci heaps, and leftist trees), I find that, not
only is there added complexity, but the overhead that I was trying to
avoid reappears in different contexts.
Since STL does not have a prioritized_set<>, and in fact, its
prioritized_queue requires the technique you and others mentioned, I
thought I would make one, and discuss it here if anyone is interested.
template <typename Element, typename Priority> Prioritized_Set<Element,
Priortity>:
First, as always, unlike STL, I keep my iterators inside my containers
so that I do not have to declare them when I need them. That said, I
plan the following.
This data structure will be implemented "in the raw". The overhead
resulting from using map<>/etc. to synthesize this structure is simply
horrific. In fact, in the raw, the overhead is still horiffic.
I imagine a 2-dimensional matrix, consisting of Pnodes and Enodes.
Pnodes represent the priorities of the set. ENodes represent the
elements of the set. The the far-left column of the matrix will contain
the Pnodes, and the remnant of the matrix will contain the Enodes. The
Enodes will be assembled in queues, one queue per row. Each queue will
be attached to its corresponding Pnode.
With this data structure, and appropriate linkage, it is possible to
satisfy all 9 constraints mentioned in my original post, and several
more.
1. One must link the Pnodes to form a set among themselves perhaps
using an AVL or Red-Black implementation.
2. One must link the Enodes to form a set among themselves, perhaps
using and AVL or Red-Black implementation.
3. For a given priority, one must link the Enodes with that priority
among themselves to form a queue, and attach the head of the queue to
its corresponding Pnode.
4. Each Enode must contain a back-pointer to its corresponding Pnode.
Even though this data structure will have significant pointer overhead,
it should be evident that all operations will run in O[log(n)], actual
time, and there will be a very rich set of operations.
How significant is the pointer overhead?
For Pnode, there will be two child pointers (2), a color/balance/etc
word (1), plus unsigned long int for # of elements in queue for that
priority(1), plus pointer to first Enode in queue(1), plus pointer to
pointer to last Enode to be added to queue (1). That's 6 (32-bit)
words per Pnode. If a priority is also 32-bits, that's an overhead
ratio of 6:1.
For Enode, there will be two child pointers (2), a color/balance/etc
word (1), a back-pointer to Pnode (1). If each element is a pointer,
then that's an overhead ratio of 4:1
Despite this horrific overhead, this seems to me to be the simplest
approach, rich in features, providing O[log(n)] acutal time for all
operations.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]