C/C++:切换非整数

Question

通常我需要根据非POD常量元素的值选择要做的事情,如下所示:

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

可悲的是switch只能用整数:error: switch quantity not an integer.

实现这样的事情最简单的方法是获得一系列ifs:

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

但是这个解决方案看起来很脏并且应该花费O(n),其中n是案例数,而在最坏的情况下,使用二进制搜索,这段代码可能花费O(log n).

使用一些数据结构(如Maps)可以获得表示字符串的整数(O(log n)),然后使用O(1)switch,或者可以通过if在右边嵌套s 来实现静态二进制排序但是,这些黑客攻击还需要大量编码,使一切变得更加复杂和难以维护.

最好的方法是什么？(快速,干净,简单,正如switch声明所述)

Answer 1

使用一些讨厌的宏和模板魔法,可以在编译时使用漂亮的语法获得展开的二进制搜索 - 但必须对MATCHES("case")进行排序: 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)

这将生成(大致)一个函数bool xy_match(char *&_buf,T &user),因此它必须位于外层.称它为例如:

xy_match("bqr",youruserdata);

这break是隐含的,你不能堕落.对不起,它也没有大量记录.但你会发现,有更多的使用可能性,看看.注意:仅使用g ++进行测试.

更新C++ 11:

Lambdas和初始化列表使事情变得更漂亮(不涉及宏!):

#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;
}

这就是主意.可以在这里找到更完整的实现:switch.hpp.

2016年更新:编译时间trie

我对此问题的最新看法是使用高级c ++ 11元编程在编译时生成搜索.与以前的方法不同,这将处理未分类的 case-branches/strings就好了; 它们只需要是字符串文字.G ++也允许使用constexpr,但不能使用clang(从HEAD 3.9.0/trunk 274233开始).

在每个trie节点中,使用switch语句来利用编译器的高级代码生成器.

完整的实现可以在github:smilingthax/cttrie获得.

Answer 2

在C++中,您可以O(lg n)通过拥有一个来获得性能std::map<std::string, functionPointerType>.(在C中,你可以实现基本相同的东西但是会更难)使用的拉出正确的函数指针std::map<k, v>::find,并调用该指针.当然,这不会像语言支持的switch语句那么简单.在另一方面,如果你有足够的项目,有将是之间的巨大差异O(n)和O(lg n),这可能是你应该去为在第一时间不同的设计的指示.

就个人而言,无论如何,我总是发现ELSEIF链更具可读性.

Answer 3

您可以在不使用任何地图或unordered_map的情况下实现它,如下所示.单独比较第一个字符以识别哪个字符串.如果不止一个匹配,那么您可以回退到该case语句中的if/else链.如果没有多个以相同字母开头的字符串,则比较次数将大大减少.

char *str = "foo";
switch(*str)
{
case 'f':
    //do something for foo
    cout<<"Foo";
    break;
case 'b':
    //do something for bar
    break;
case 'c':
    if(strcmp(str, "cat") == 0)
    {
        //do something for cat
    }
    else if(strcmp(str, "camel") == 0)
    {
        //do something for camel
    }
}

这看起来是没有任何成本的最佳解决方案,即使它不是标准的.

Answer 4

用一个if...else block.你并没有一个令人信服的理由,除了它不是很好看之外,这个if...else块是最直接的解决方案.

其他一切都需要额外的代码,据说这会增加复杂性.它只是把丑陋的东西移到别处.但在某种程度上,字符串比较仍然必须发生.现在你已经用更多的代码覆盖了它.

您可以通过使用地图或哈希映射获得一些性能提升,但是您也可以通过简单地选择智能订单来评估您的if...else块,从而获得类似的即使不是更好的收益.出于性能原因切换到地图实际上只是过早的微优化.

Answer 5

在C中,有两种常见的解决方案.第一个是将关键字保存在排序数组中

typedef struct Keyword {
    const char *word;
    int         sub;
    int         type;
} Keyword;

Keyword keywords[] ={   /* keep sorted: binary searched */
    { "BEGIN", XBEGIN, XBEGIN },
    { "END",   XEND,   XEND },
    { "NF",    VARNF,  VARNF },
    { "atan2", FATAN,  BLTIN },
    ...
};

并对它们进行二分查找.前面的内容直接来自C大师Brian W. Kernighan 的awk源代码.

另一个解决方案是O(min(m,n)),如果n是输入字符串的长度,m是最长关键字的长度,则使用有限状态解决方案,例如Lex程序.