Policy Based Design Using C++ Typemaps
In C++ sense typemap is not a class, but since we are involved in meta-programming, let's name it meta-class or classoid. We can emulate class functionality by using namespace constructs of C++ language. First we define namespace typemap, which acts as actual class. Then each class defined in that namespace is regarded as member function and each typedef acts as member variable. We move all private members into typemap_private namespace. Of coarse typemap_private is not private (in C++ sense) at all. The programmer can still access these members intentionally, but not accidentally. Actually, by this way we can simulate even better functionality of member access mechanism, than exists in modern C++. Instead of revoking the access to private members, we simply make them invisible.
namespace typemap { ... // public members namespace typemap_private { ... // private members } }
As for any associative container every element of typemap contains a key and value parts. The common way of designing meta-container is to have each element referring to the next one. The last element refers to a type that is never used anywhere else (Listing 1).
NullType contains Key member to prevent failures, when the compiler tries to look at the Key component of the last element. I use struct keyword instead of class just to skip writing annoying public statements. It really doesn't matter whether you use class or struct in this case. One may suggest using class, just to point that this is a C++ code, but this is not strictly a C++ class. In our meta-programming sense this is just a declaration of meta-member.
The typemap container is simply a reference to the first element. Typemap is defined as separate class, because in the future we may need to add something without touching the item class. I would suggest moving the implementation into private for all other members. More complicated constructions would require many parameters, and doing so will protect against accidental passing of unwanted template parameters.
Note the X type definition, which serves as a return value. Some libraries use type word, some try to use more descriptive names. I would argue for one-letter name for making code shorter and capital to indicate a type in C++ sense.
As we have described the container and its item, we may want to jump directly to the insertion of elements. Having procedural programming language it is relatively easy to implement the insertion into map class. Basically you have to search for the key and then insert or update the element depending on whether the key was found or not. The description of an insertion algorithm takes one sentence and the actual code will not be much longer. Having meta-language such simple algorithm requires the use of several techniques of meta-programming and significant size of code. One thing that makes the design of insert easier, is that we don't have the relational operation among C++ types. It is hard to invent a logic by how you should sort File and Widget classes. Our typemap meta-class just keeps the keys unique.
The insertion algorithm uses almost all the other techniques of typemap meta-class. As soon as we finish with insert member, we will be through almost all other typemap techniques.
The public part of insert member just checks for emptiness of the container and calls the private implementation (Listing 2). If the container is empty, then the specialization works and provided key-value pair becomes the first element of map. If the container is not empty, then the algorithm should search for the given key. This is a place for another member of typemap meta-class - find.
The search algorithm uses C++ partial specialization construction. The heart of the search algorithm is the match class (Listing 3). The first specialization works when element is found. As the K parameter becomes equal to KK, the compiler picks it up and returns the item as X. The second specialization is used, if the compiler reaches the end of the list without finding the element.
If insert algorithm can't find the given element, then it just appends the new one. This is easy to do using push_front member. Note, that having push_front is useful only internally and for debugging purposes. The user of the class should never use it, but always insert instead. Therefore push_front and push_back should be moved into private area. The definition of push_front is simple and straightforward (Listing 4). The definition of erase_front is similar.
The hardest part comes, when we have to replace an existing element. It is interesting to compare with procedural language case, where this is the easiest case. It doesn't matter however, whether we remove the existing element and insert the new one or just change the value part of the element. None of those change the complexity of the algorithm. The algorithm still looks ugly. While being ugly in regular programming is usually unacceptable, in meta-programming world it could be perfectly useful. Anyway, if reader can find a better solution than presented below, I will appreciate much for the information. The problem with the present solution is that it requires reversing the container after finding the element, erasing, adding, and then reversing again. The better solution would be a way of changing some element without restructuring the container itself. Another solution is to mark the existing element and skip using it later. The disadvantage of this method is the growth of the container with unwanted elements. While the described algorithm in no way harms the application performance, it degrades the compilation time, which is also a concern.
The described insertion algorithm reverses the part of the container for manipulating its boundary elements. It is hard to define relational operator for types and in our current purpose doesn't make any sense at all. In this case, when the elements are not ordered but just grouped, the reverse operation makes sense. Unfortunately reverse algorithm requires total restructuring of the container, so with large containers, the compilation time might degrade significantly. As shown on Listing 5, the reverse algorithm starts with NullType element and accumulates other elements through Item component. As soon as the end of container has reached (the compiler picks the specialization), then the current collected element (I parameter) becomes the resulting reversed container.
Erase member uses the matching technique to find the element. When the element is found, the algorithm reverses all the previous elements, to bring the found item to front. After using erase_front method, the algorithm reverses part of the container back and concatenates it with the remaining part. The insert method uses the same technique to remove the found element and then add the new one.
The final insert algorithm is described in Listing 7. It encapsulates all the previous defined techniques. I have repeated the code, to make it more readable and maybe compilable slightly faster.
Another functionality that we should add to typemap class is iteration through its elements. The iteration through the meta-container often plays a role of a bridge between meta- and real-code. The simplest case of for_each method is shown in Listing 6. The iteration is done by recursive inheritance. Each inherited class calls a member of its base. The last class calls the member of empty base, which does nothing.
For_each member accepts the container as first parameter and a functor as second. The functor has to accept a template parameter, which refers to the current element. For_each instantiates the functor and calls its member for each element of the container.
I don't see a good way of implementing generic for_each member, some sort of generic code of second degree. With current C++ capabilities I would prepare for_each member for the simple and most common case, and reimplement for_each for each more complicated and specific use. The examples coming with this article have implementation of for_each member with support of returning values and passing additional parameters.
Copyright (C) 2005,2006,2013 Andre Mirzoyan