GuidesTo Switch or Not to Switch

To Switch or Not to Switch

Developer.com content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.

Crazy Little Thing Called Switch — An Overview


The “switch” is one of the most underrated statements in C++ programming. Usually, you’ll find it mentioned in the “do not” sections of books and articles—associated with the dangers of manual type dispatching and implicitly denoting bad programming style. Not even efficiency saves it from obscurity. When code is optimized for speed or the case labels have a compact distribution of values, “switch” is implemented as a jump table—extremely fast without any manual intervention. The only possible optimization is to concentrate the most used cases on the first places inside the switch—on small embedded platforms, it might make a difference.


All the above means that there is not much to say about a “switch” and the subject is hopelessly uninteresting.


But wait—there might be something left out. Many times, “switch” is used in the context of “factories” or finite state machines as a fast dispatching mechanism based on integer type parameters. These (especially factories) are cases when there is no way to use a polymorphic approach as there are no types defined yet—a switch or a switch-like construct are the only possibilities.


The potential problem in these cases is how to maintain and extend a switch1. There is an idiom for extending a switch (see canon_switch.cpp):

struct A
{
static int doSwitch(int pos)
{
switch (pos)
{
case 0: return 0;
default: return -1;
}
}
};
template <class S>
struct B
{
static int doSwitch(int pos)
{
switch (pos)
{
case 1: return 1;
default: return S::doSwitch(pos);
}
}
};

Variations are possible: inheritance instead of composition, for example. The issue here is that individual cases are hard to maintain.


Another way is to use std::map instead of switch. This technique has the added benefit of dispatching on types other than integer and is easy to extend (just append a new instance). The penalty to pay is an additional step of loading the map. This is great as long as the map stays in memory and is used over and over again. But, in stateless designs, this might be an overburden.


There is a meta-programming version of “switch” too [2]:

template<int I>
class CASE {
public:
static inline void f() //default
{ }
};
class CASE<value1> {
public:
static inline void f()
{ }
};
class CASE<value2> {
public:
static inline void f()
{}
};
CASE<I>::f();

It looks almost perfect, but (nothing is perfect!) it can be used at compile-time only.


I will try to investigate other options, balancing different factors and alternatives.


Templates Come to the Rescue


This is the first attempt:

template < int I>
struct X
{
static int getValue(int pos)
{
if (pos== I)
return I;
return X<I -1>::getValue(pos);
}
};
template < >
struct X<-1>
{
static int getValue(int pos)
{
return -1;
}
};
template < >
struct X<0>
{
static int getValue(int pos)
{
if (pos == 0)
return 0;
return X<-1>::getValue(pos);
}
};
void doSwitch(int pos)
{
std::cout << X<I>::getValue(pos);
}

This design exposes the meta-programming model to the real-time realm through chaining. Is it very efficient (the chain is actually calculated at compile time), but it doesn’t do a very good job in hiding the chaining mechanism itself—every specialization has to (re)implement it (see X<0>).


Using a Curiously Recurring Template Pattern


An alternative is to use CRTP (Curiously Recurring Template Pattern)3—and factor out the mechanism (see sequence.cpp):

template <template <int> class T, int I>
struct Root
{
int run(int pos) const
{
const T<I>& ref = static_cast<const T<I>&>(*this);
if (pos== I)
return ref.getValue();
return T<I-1>().run(pos);
}
};
template <template <int> class T>
struct Root<T, -1>
{
int run(int pos) const
{
return -1;
}
};
template < int I>
struct X : Root<X, I>
{
static int getValue()
{
return I;
}
};
template < >
struct X<2> : Root<X, 2>
{
static int getValue()
{
return 10;
}
};
void doSeq(int j)
{
std::cout << X<10>().run(j) << std::endl;
}

Now, Root contains the advancing mechanism—the specializations only contain what’s traditionally found in case statements. Unfortunately, the “template template” non-type specialization used in the above code is not fully supported by some compilers at this moment (VC 7.1, for example).

A Versioning Alternative to Inheritance


Of course, things can be further improved. Why switch to using integer parameters only? Why rigidly require all the classes to be part of the same family (X<I>)? Why not be able to extend the “case” classes? Analyze the requirements one by one.


A “generalized switch” can be created by isolating the comparisons and making the return mechanism more generic. This, together with a PREVIOUS_TYPE composite, solves the first two issues.


Extending a “case” is more complicated. What you want to achieve is a guaranteed usage of the latest extended version. For example, having a switch-like chain containing CASE1 and CASE2, where CASE2 has a newer implementation CASE2_1, you would like to chain CASE1 and CASE2_1 together at compile time. The compiler has to figure out that, at most, two versions of CASE2 exist and to pick up the latest.


Note that inheritance cannot be used because we don’t know in advance the latest subclass. One solution might be the following:

template <class T>
struct Root
{
enum { VERSION = 0};
template <class U, class Z>
void operator()( const U& i, const Z& z) const
{
typedef typename T::PREVIOUS_TYPE W;
const T& ref = static_cast<const T&>(*this);
ref.equals(i) ? ref.evaluate(z) : W()(i, z);
}
};
template <>
struct Root<void>
{
template <class U, class Z>
void operator()( const U& i, const Z& z)
{ z(“NOT_FOUND”);}
};
typedef Root<void> ROOT_NOT_FOUND;
template <int I>
struct NOT_FOUND : Root<NOT_FOUND<I> >
{
typedef ROOT_NOT_FOUND PREVIOUS_TYPE;
template <class U> bool equals(const U& i) const
{
return false;
}
template <class Z>
void evaluate(const Z& z) const
{}
};
template <int I>
struct T0 : Root<T0<I> >
{
typedef NOT_FOUND< NOT_FOUND<1>::VERSION> PREVIOUS_TYPE;
template <class U> bool equals(const U& i) const
{
return (i == 0);
}
template <class Z>
void evaluate(const Z& z) const
{
z(“T00”);
}
};
template <>
struct T0<1> : Root<T0<1> >
{
typedef NOT_FOUND< NOT_FOUND<1>::VERSION> PREVIOUS_TYPE;
enum { VERSION = T0<2>::VERSION == 0 ? 1 : T0<2>::VERSION};
template <class U> bool equals(const U& i) const
{
return (i == 0);
}
template <class Z>
void evaluate(const Z& z) const
{
z(“T01”);
}
};
template <int I>
struct T7 : Root<T7<I> >
{
typedef T0< T0<1>::VERSION> PREVIOUS_TYPE;
template <class U> bool equals(const U& i) const
{
return (i == 60);
}
template <class Z>
void evaluate(const Z& z) const
{
z(60);
}
};
template <>
struct T7<1> : Root<T7<1> >
{
typedef T0< T0<1>::VERSION> PREVIOUS_TYPE;
enum { VERSION = T7<2>::VERSION == 0 ? 1 : T7<2>::VERSION};
template <class U> bool equals(const U& i) const
{
return (i == 60);
}
template <class Z>
void evaluate(const Z& z) const
{
z(601);
}
};
struct T9 : Root<T9>
{
typedef T7< T7<1>::VERSION> PREVIOUS_TYPE;
template <class U> bool equals(const U& i) const
{
return (i == 120);
}
template <class Z>
void evaluate(const Z& z) const
{
z(“120”);
}
};
struct O
{
template <class Z>
void operator()(const Z& z) const
{
std::cout << “CRTP ” << z << std::endl;
}
};
void doCurRecur(int j)
{
T9()(j, O());
}

Let’s analyze the previous design a little bit.


We are still dealing with CRTP—only that the advancing mechanism is base now on PREVIOUS_TYPE (actually is a backwards going mechanism). And PREVIOUS_TYPE itself uses VERSION, which advances through all the versions of a certain “case” and collects the latest one—using constructs like:

typedef T0< T0<1>::VERSION> PREVIOUS_TYPE;
enum { VERSION = T7<2>::VERSION == 0 ? 1 : T7<2>::VERSION};

Of course, the latest design can be subject to other improvements (for example, policies can be used to encapsulate the versioning mechanism) but this is beyond the scope of this article, which just wanted to demonstrate that there are open options even when dealing with well-established programming concepts.

Download


Download the accompanying code’s zip file here.


Conclusion


This article tried to analyze patterns associated to “switch” statement usage in C++ and generalize the concept of a “switch.” Possible designs of a more generic “switch” were described together with a way of extending classes based on versioning.

References



  1. “The Open Closed Principle,” Robert C. Martin, C++ Report, January 1996
  2. Todd Veldhuizen: “Template Metaprograms” http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html
  3. C++ Templates: The Complete Guide, by David Vandevoorde, Nicolai M. Josuttis. Addison-Wesley Professional, 2002
  4. Design Patterns, Gamma, et. al, Addison-Wesley, 1995

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Latest Posts

Related Stories