peoro peoro - 10 months ago 90
C Question

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: ...

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

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)
, or one could implement a static binary sort by nesting
s 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
statement is)

Answer Source

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

  some c++ code
  ... the buffer for the match is in _buf
  ...  user.YOURSTUFF 

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:


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)) ) {
  } // 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.