|
The Curiously Recurring Template Pattern doesn't have to be exotic. Christopher uses it to make some flexible data types.
January 01, 2006
URL:http://drdobbs.com/building-more-flexible-types-with-mixins/184402056
Christopher Diggins is a freelance consultant and developer of the Heron programming language. He is a coauthor of the C++ Cookbook (O'Reilly, 2005) and can be reached at http://www.cdiggins.com/.
In C++, the Curiously Recurring Template Pattern (CRTP) [1] is a common name given to the technique of inheriting from a template parameter. Outside of the C++ community, this technique is known more widely as a mixin [2]. Mixins are described in the literature to be a powerful tool for expressing abstractions, but CRTP is often viewed as a somewhat exotic technique, and somewhat under utilized. In this article, I plan on showing how it can be used in a rather pedestrian manner to create simple designs that are significantly more flexible.
What many programmers realize, through observing Java and other languages, is that hierarchical layers of abstraction in our designs can reduce the amount of code we have to write and maintain. Furthermore, they can isolate the ripple effect of changes when refactoring, making such designs more appropriate for agile development.
Unfortunately, traditional OOP techniques for expressing abstractions, such as using abstract base classes, are not often used in C++ code. One of the big reasons for this is that it is incompatible with generic programming techniques such as those used by the STL. However, the advantages of OO designs can be achieved, even in generic designs, by using mixin-based composition of classes through simple application of the CRTP pattern.
Let's start by looking at a simple example, my favorite abstract data type (ADT), the stack. A stack ADT can be expressed minimally in C++ as an abstract base class (ABC), as shown in Listing 1.
A very trivial, yet effective, implementation of the AbstractStack is shown in Listing 2.
In and of itself, the ConcreteStack is not particularly useful in any real-world scenario because it is severely lacking in functionality. It could be augmented easily through the introduction of several utility functions such as: PushCopy(), MultiPop(), Clear(), Duplicate(), Exchange(), Top(), Reverse(), and so on. These functions can be added directly to ConcreteStack, but if I do that, what happens if I need a new implementation of AbstractStack? Consider the perfectly reasonable alternative implementation of FixedStack, which inherits AbstractStack in Listing 3.
All of the utility functions would have to be more or less cut and pasted into this new implementation. This violates a principle rule of programming: reduce redundancy. The obvious object-oriented solution, then, is to place the extra member functions directly in AbstractStack itself, or better yet, in a separate class that inherits from AbstractStack, such as AbstractStackExtension in Listing 4.
The approach of extending ADTs in this manner is very useful until you try to apply it to a container designed using generic-programming techniques, and wish to extend a concept in a similar manner. Consider the IterableConcept (expressed in pseudocode) in Listing 5.
You can't express a concept as an abstract type because the dependent member types (e.g., Iterator) are specific to (dependent on) the concrete implementation. This doesn't mean you can't still express an extension as a separate abstraction.
Let's say you want to introduce a set of utility member functions, ForEach(), IsEmpty(), and Count(), which can be used with any class that models a particular concept. Using the CRTP, this can be done as a separate layer of abstraction, for instance in Listing 6.
In order to use the extension class in conjunction with a class that models the concept being extended, you need to create a third class that glues the extension class to the implementation class through inheritance. This is demonstrated in Listing 7.
The biggest drawback of the CRTP technique is that constructors aren't inherited. This means that if you use an initializing constructor in your implementation class, every extension will have to have an appropriate initializing constructor. This causes the extensions to be more restricted and, as such, less useful.
Clearly, the CRTP is a very expressive technique. Furthermore, it is more efficient than the more traditional OO approach because there is no abstraction penalty paid. Now we just have to wait and see if C++ will enable constructor initialization in the future.
Much thanks to Max Lybbert for reviewing and commenting on this article.
CUJ
template<typename T>
class AbstractStack {
public:
typedef Item T;
virtual ~AbstractStack() { }
virtual void Push(std::auto_ptr<Item> x) = 0;
virtual std::auto_ptr<Item> Pop() = 0;
virtual bool IsEmpty() = 0;
};
template<typename T>
class ConcreteStack : AbstractStack {
public:
~ConcreteStack() { while (!IsEmpty()) Pop(); }
void Push(std::auto_ptr<Item> x) { m.push_back(x.release()); }
std::auto_ptr<Item> Pop() { std::auto_ptr<Item> x = m.top(); m.pop_back(); return m; }
bool IsEmpty() { return m.IsEmpty(); }
private:
std::vector<Item*> m;
};
template<typename T, int N>
class FixedStack : AbstractStack {
public:
FixedStack() : cur(0) { }
~FixedStack() { while (!IsEmpty()) Pop(); }
void Push(std::auto_ptr<Item> x) { m.push_back(x.release()); }
std::auto_ptr<Item> Pop() { assert(cur > 0);
std::auto_ptr<Item> x = m[cur-1]; m.pop_back(); return m; }
bool IsEmpty() { return cur == 0; }
private:
int cur;
Item* m[N];
};
template<typename T>
class AbstractStackExtension : AbstractStack<T> {
public:
void PushCopy(const Item& x) { Push(new Item(x)); }
void MultiPop(int n) { while (n > 0) Pop(), --n; }
void Clear() { while (!IsEmpty()) Pop(); }
...
};
template<typename T>
concept IterableConcept {
typedef Iterator;
Iterator Begin();
Iterator End();
}
template<typename IterableConcept>
struct IterableExtension : IterableConcept {
typedef typename IterableConcept::Iterator Iterator;
typedef typename IterableConcept::Item Item;
template<typename FunctionT>
void ForEach(FunctionT f) {
Iterator first = IterableConcept::Begin(), last =
IterableConcept::End();
while (first != last) f(*first++);
}
bool IsEmpty() {
return IterableConcept::Begin() == IterableConcept::End();
}
int Count() {
int ret = 0;
Iterator first = IterableConcept::Begin(), last =
IterableConcept::End();
while (first != last) ++first, ++ret;
return ret;
}
};
template<typename T>
struct StackImpl {
typedef typename std::vector<T>::iterator Iterator;
typedef T Item;
Iterator Begin() {
return m.begin();
}
Iterator End() {
return m.end();
}
void push(T n) { m.push_back(n); }
T pop() { T ret = m.back(); m.pop_back(); return ret; }
private:
std::vector<T> m;
};
template<typename T>
struct Stack : IterableExtension<StackImpl<T> > {
};
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.