C/C++: switch for non-integers

Often I need to choose what to do according to the value of a non-POD constant element, something like this:

switch( str ) {
  case "foo": ...
  case "bar": ...
  default:    ...
}

Sadly switch can only be used with integers: error: switch quantity not an integer.

The most trivial way to implement such thing is then to have is a sequence of ifs:

if( str == "foo" )      ...
else if( str == "bar" ) ...
else                    ...

But this solution looks dirty and should cost O(n), where n is the number of cases, while that piece of code could cost O(log n) at the worst case with a binary search.

Using some data structs (like Maps) it could be possible to obtain an integer representing the string ( O(log n) ), and then use an O(1) switch, or one could implement a static binary sort by nesting ifs in the right way, but still these hacks would require a lot of coding, making everything more complex and harder to maintain.

What's the best way to do this? (fast, clean and simple, as the switch statement is)

Solution 1:

Using some nasty macro and template magic it's possible to get an unrolled binary search at compiletime with pretty syntax -- but the MATCHES ("case") have to be sorted: fastmatch.h

NEWMATCH
MATCH("asd")
  some c++ code
MATCH("bqr")
  ... the buffer for the match is in _buf
MATCH("zzz")
  ...  user.YOURSTUFF 
/*ELSE 
  optional
*/
ENDMATCH(xy_match)

This will generate (roughly) a function bool xy_match(char *&_buf,T &user), so it must be at the outer level. Call it e.g. with:

xy_match("bqr",youruserdata);

And the breaks are implicit, you cannot fall-thru. It's also not heavily documented, sorry. But you'll find, that there are some more usage-possibilities, have a look. NOTE: Only tested with g++.

Update C++11:

Lambdas and initializer list make things much prettier (no macros involved!):

#include <utility>
#include <algorithm>
#include <initializer_list>

template <typename KeyType,typename FunPtrType,typename Comp>
void Switch(const KeyType &value,std::initializer_list<std::pair<const KeyType,FunPtrType>> sws,Comp comp) {
  typedef std::pair<const KeyType &,FunPtrType> KVT;
  auto cmp=[&comp](const KVT &a,const KVT &b){ return comp(a.first,b.first); };
  auto val=KVT(value,FunPtrType());
  auto r=std::lower_bound(sws.begin(),sws.end(),val,cmp);
  if ( (r!=sws.end())&&(!cmp(val,*r)) ) {
    r->second();
  } // else: not found
}

#include <string.h>
#include <stdio.h>
int main()
{
  Switch<const char *,void (*)()>("ger",{ // sorted:                      
    {"asdf",[]{ printf("0\n"); }},
    {"bde",[]{ printf("1\n"); }},
    {"ger",[]{ printf("2\n"); }}
  },[](const char *a,const char *b){ return strcmp(a,b)<0;});           
  return 0;
}

That's the idea. A more complete implementation can be found here: switch.hpp.

Update 2016: Compile time trie

My newest take on this problem uses advanced c++11 metaprogramming to generate a search-trie at compile time. Unlike the previous approaches, this will handle unsorted case-branches/strings just fine; they only have to be string-literals. G++ also allows constexpr for them, but not clang (as of HEAD 3.9.0 / trunk 274233).

In each trie node a switch-statement is utilized to harness the compiler's advanced code generator.

The full implementation is available at github: smilingthax/cttrie.

Solution 2:

In C++, you can obtain O(lg n) performance by having a std::map<std::string, functionPointerType>. (In C you could implement what was essentially the same but it would be more difficult) Pull out the right function pointer using std::map<k, v>::find, and call that pointer. Of course, that's not going to be nearly as simple as a language supported switch statement. On the other hand, if you have enough items that there's going to be a huge difference between O(n) and O(lg n), that's probably an indication that you should be going for a different design in the first place.

Personally, I've always found the ELSEIF chain more readable anyway.