
October 10th, 2009Have 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, searchtree, hashtable, and priorityqueue frameworks. For example, by configuring our searchtree 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 redblack 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 memorymanagement 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 binaryheap kernel for our priorityqueue framework. Instead of a single heap, I saw the data structure as a queue of pennants (a pennant is a heapordered 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 priorityqueue 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 binaryheap kernel, I encountered one surprise: the extractmin 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 extractmin 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 20093, 20094, and 20097.


©
Performance
Engineering Laboratory and the CPH STL contributors, 2000  2017
Last modification: 10.05.2017 