October 10th, 2009
Have you ever heard of component frameworks? You should! We have
finally understood that the container part of the C++
standard library is nothing but seven component frameworks: vector,
deque, array, list, search-tree,
hash-table, and priority-queue frameworks. For example, by configuring
our search-tree framework the container classes set,
multiset, map, and multimap can be
obtained. On your choice, the underlying realizator can be based on an
AVL tree or a red-black tree if you want.
If you have an idea how some of the standard containers should be
implemented, the implementation of such an idea would be a manageable
task using our component frameworks. Let us take our vector
framework as an example. The memory-management kernel that handles the
dynamization of an array by doubling and halving requires 70 lines of
code. Everything else in the vector implementation is
different type of interface code, which is quite straightforward.
After seeing these 70 lines you really understand what
a vector is. And to write a new kernel does not sound that
difficult, but it requires that you understand the framework of course.
Yesterday, I implemented a binary-heap kernel for our priority-queue
framework. Instead of a single heap, I saw the data structure as a
queue of pennants (a pennant is a heap-ordered binary tree whose size
is a power of two, its root stores the maximum and has no left child,
and the right subtree of the root is a perfect binary tree). I had to
write three member functions for a node class: promote (swaps
a node and its parent), distinguished_ancestor (for binary
heaps this is just the parent), and join (links two pennants
together). After this I had a complete priority-queue implementation
fulfilling the CPH STL API and providing all bells and whistles. The
resulting priority queue supports insertion of a new element in
amortized constant time. Moreover, the data structure is meldable and
provides the function of melding two heaps of size m
and n in O(lg m × lg n) time.
Observe that the classical textbook by Cormen et al. still, even in
its third edition, claims that insertion takes logarithmic time and
melding linear time for binary heaps.
When benchmarking the new binary-heap kernel, I encountered one
extract-min function, which is the same for all priority
queues, has O((lg n)2) running time for a
queue of pennants, even though this member function works fine for the
other data structures. So now I have to improve the framework, which
is not necessarily a simple task. In principle, I have to write an
extract-min function that is optimal for all the existing
priority queues and the ones you will invent tomorrow. As you may
guess, we might want to provide a partial specialization of this
single member function for specific data structures, but according to
the current rules of C++ one has to specialize the whole
If you want to see some interesting code, look at CPH STL reports
2009-3, 2009-4, and 2009-7.
All rights reserved Jyrki Katajainen.