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 surprise: the 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 framework class...

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. <- <-
© Performance Engineering Laboratory and the CPH STL contributors, 2000–2018
Last modification: 2018-01-31