C/C++：非整数类型的switch语句

Question

经常需要根据非POD常量元素的值来选择要执行的操作, 就像这样:

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

遗憾的是，switch 仅能用于整数：error: switch quantity not an integer。

最简单实现该功能的方法是使用一系列 if 语句：

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

但是这个解决方法看起来比较繁琐，并且成本为O(n)，其中n是情况的数量，而那段代码在最坏情况下可能会耗费O(log n)时间进行二进制搜索。

使用一些数据结构(如Maps)，可以获得代表字符串的整数(O(log n))，然后使用O(1)的switch语句，或者可以通过嵌套if来实现静态二进制排序，但是这些“黑科技”需要大量的编码，使一切变得更加复杂和难以维护。

有什么好的方法来做到这一点吗？（快速、简洁和简单，就像switch语句一样）

- peoro

---

如果你的列表中有足够多的项，以至于O(n)和O(lg n)之间的差别非常大，那么这可能表明你本应该不要首先使用switch语句。 - Billy ONeal

可能是重复问题：https://dev59.com/xG865IYBdhLWcg3wCqHI - Johan Kotlinski

@kotlinski提到这个 "possible duplicate" 只标记了C语言，而这个假设是基于C++（请看str=="foo"的条件，这在C中无法工作）。我的翻译不会改变原意，只会尽量让内容更加通俗易懂。 - MSalters

我删除了C标签，因为显然不是由OP所想。 - rubenvb

@peoro：好的，我在这里被否决了，但是你的第一点非常错误。为什么？有两个原因，都同样糟糕：a）“foo”是一个const char，而不是char，b）对于char指针，相等性将不能达到预期的效果（在所有情况下，一些编译器优化可能会使其达到您想要的效果，但仍然是不正确的）：您正在比较指针值，而不是数组的内容。这是一个重要的区别，这就是为什么@MSalters上面的评论和@Kos下面的答案解释了实际发生的事情。我同意，这是一个可怕的例子 ;) - rubenvb

Answer 1

使用一些复杂的宏和模板魔法，可以在编译时得到一个展开的二分查找，而且语法很清晰--但是匹配（"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是隐式的，你不能fall-thru。这也没有过多的文档记录，抱歉。但你会发现，还有一些更多的用法，可以看一下。注意：仅在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年更新：编译时字典树

我对这个问题的最新解决方案使用了先进的c++11元编程，在编译时生成一个搜索字典树。与以前的方法不同，这将很好地处理未排序的情况分支/字符串；它们只需要是字符串文字。G++也允许对它们进行constexpr，但clang不允许（截至HEAD 3.9.0 / trunk 274233）。

在每个字典树节点中，利用开关语句来利用编译器的高级代码生成器。

完整的实现可在github上找到：smilingthax/cttrie。

- smilingthax

---

+1 对于一个有趣的库解决方案，它可以接近 OP 所想要的。 - Billy ONeal

有趣。我想知道如何开发出更健壮的解决方案而不使用宏。这是一个新方法的好起点。 - John Dibling

@John：我认为没有宏是不可能的，因为我必须使用两个模板（模板特化）来计算每个MATCH的二进制搜索时间。这是我能接近“开关”的最接近方式。即使是展开也是不可避免的，由模板元编程的工作方式所决定。我甚至不相信这在C++中是可能的——直到我让它编译并看到它工作。 - smilingthax

+1 这模仿了编译器对整数值所做的事情，但是针对非整数值。编译器采用跳转表或静态二叉树来优化 case 查找（和随后的分支）。但总的来说，如果我们要在运行时执行操作以启用此抽象，则字典似乎是答案。我的意思是，OP 不应该纠结于使语法看起来类似于 switch 语句。字典为他提供了与整数的 switch 相同的东西。 - Ziffusion

有一种更好的方法，而不需要使用宏：实际上可以使用gperf生成完美哈希函数。http://www.gnu.org/software/gperf/ - Wade

Answer 2

在 C++ 中，通过使用 std::map<std::string, functionPointerType> 可以获得 O(lg n) 的性能。 (在 C 语言中，你可以实现类似的功能，但会更加困难) 使用 std::map<k, v>::find 找到正确的函数指针，并调用该指针。当然，这不会像语言支持的 switch 语句那样简单。另一方面，如果有足够多的项，使得 O(n) 和 O(lg n) 之间存在巨大差异，则这可能表明你应该首先考虑不同的设计。

个人而言，我始终认为 ELSEIF 链更易于阅读。

- Billy ONeal

---

+1 建议使用 std::map，但是 elseif 对于长列表来说不太好。 - BЈовић

@VJo：如果你的项目列表足够长，无论如何都应该将其替换为某种形式的多态行为。 - Billy ONeal

在C语言中，你可以使用有序列表和bsearch。原始的Awk实现对关键字执行此操作。在C ++中，unordered_map 可以在O(n)时间内进行操作。 - Fred Foo

@larsmans：这将是一个不错的C语言解决方案。也许我们可以点赞？:) 不过，unordered_map还没有成为标准，这阻止了我在推荐中使用它（如果我不使用它，我不知道如何要求其他人使用它），当然使用bsearch需要你的字符串已经排序。 - Billy ONeal

@Billy 不一定。例如，如果你想将字符串映射到某些常量整数值，你可以使用 boost::assign::map_list_of 初始化映射。 - BЈовић

Answer 3

你可以通过以下方式实现它，而不使用任何map或unordered_map。 仅比较第一个字符以识别哪个字符串。 如果有多个匹配项，则可以在该情况语句中回退到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
    }
}

这似乎是一种没有任何成本的最佳解决方案，尽管它不是标准的。

- bjskishore123

---

你为什么说它不标准？ - Alexandre C.

@Alexandre：我的意思是，我在使用C风格字符串时使用了strcmp。如果我们改用std::string，则这将是最佳的C ++解决方案。 - bjskishore123

这实际上是一个相当不错的解决方案... :) - rubenvb

@Billy： 首先，第一个字符将会在缓存行中，所以获取它几乎是免费的。其次，如果你真的关心那个单一的获取，你怎么看待这种情况呢？ case 'c': if (strcmp(str+1, "at"))... if (strcmp(str+1, "amel")" - blabla999

@blabla999：不，我不在意单个获取。我在意的是你让代码变得更加复杂，更容易出现错误，而且性能提升微乎其微或者没有。 - Billy ONeal

Answer 4

使用if...else块。 除了它看起来不太美观之外，你没有真正的理由不这样做，if...else块是最直接的解决方案。

其他所有方案都需要额外的代码，这增加了复杂性。而且它只是把丑陋的东西移动到别处。但在某个层面上，字符串比较仍然必须发生。现在你只是用更多的代码掩盖了它。

你可以通过使用map或hash map来获得一些性能提升，但是通过聪明地选择评估if...else块的顺序，你也可以获得类似甚至更好的收益。因为性能原因而切换到map只是过早的微观优化。

- John Dibling

---

“为了性能原因而切换到地图其实只是过早的微观优化。”我建议在这种情况下使用类似std::map的东西的主要原因是它有助于您维护开闭原则。 - Billy ONeal

在某个层面上，仍然需要进行字符串比较 - 显然问题提出者只是在比较指针，这很奇怪。 - Steve Jessop

@John：哦，不好意思，我收回之前的话。我没注意到这个问题是关于“C/C++” 的，但实际上并不是 C。所以 str 是一个 std::string，你是对的。 - Steve Jessop

这绝对是最好的答案。 - Walter

“过早的微观优化”并不是switch只能是const的全部原因，这是一种过早的微观优化吗？ - Spongman

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源代码。

另一种解决方案是使用有限状态解决方案，例如Lex程序，其时间复杂度为O(min(m, n))，其中n是您的输入字符串长度，m是最长关键字的长度。

- Fred Foo

Answer 6

这样做会太复杂了吗？

#include <iostream>
#include <map>

struct object
{
    object(int value): _value(value) {}

    bool operator< (object const& rhs) const
    {
        return _value < rhs._value;
    }

    int _value;
};

typedef void(*Func)();

void f1() {
    std::cout << "f1" << std::endl;
}

void f2() {
    std::cout << "f2" << std::endl;
}

void f3() {
    std::cout << "f3" << std::endl;
}

int main()
{
    object o1(0);
    object o2(1);
    object o3(2);

    std::map<object, Func> funcMap;
    funcMap[o1] = f1;   
    funcMap[o2] = f2;   
    funcMap[o3] = f3;

    funcMap[object(0)](); // prints "f1"
    funcMap[object(1)](); // prints "f2"
    funcMap[object(2)](); // prints "f3"
}

- Simone

---

+1 为你之前所说的内容点赞。请注意，在 main 函数中缺少返回类型（在 C++ 中是必需的，或者至少在 C++0x 中将是必需的，我现在记不清了）。 - Billy ONeal

Answer 7

这类似于lambda和unordered_map的解决方案，但我认为这是两者之间最好的选择，具有非常自然和可读的语法：

#include "switch.h"
#include <iostream>
#include <string>

int main(int argc, const char* argv[])
{
    std::string str(argv[1]);
    Switch(str)
        .Case("apple",  []() { std::cout << "apple" << std::endl; })
        .Case("banana", []() { std::cout << "banana" << std::endl; })
        .Default(       []() { std::cout << "unknown" << std::endl; });    
    return 0;
}

switch.h:

#include <unordered_map>
#include <functional>
template<typename Key>
class Switcher {
public:
    typedef std::function<void()> Func;
    Switcher(Key key) : m_impl(), m_default(), m_key(key) {}
    Switcher& Case(Key key, Func func) {
        m_impl.insert(std::make_pair(key, func));
        return *this;
    }
    Switcher& Default(Func func) {
        m_default = func;
        return *this;
    }
    ~Switcher() {
        auto iFunc = m_impl.find(m_key);
        if (iFunc != m_impl.end())
            iFunc->second();
        else
            m_default();
    }
private:
    std::unordered_map<Key, Func> m_impl;
    Func m_default;
    Key m_key;
};
template<typename Key>
Switcher<Key> Switch(Key key)
{
    return Switcher<Key>(key);
}

- Aaron Frantisak

Answer 8

以下是能正常运行的示例代码：

这应该可以正常工作。
（但仅适用于长度为4个字节或更短的字符串）

此方法将字符串视为4字节整数。

这种方法被认为很丑陋、不可移植、“hacky”且风格不佳。 但它确实可以做到你想要的效果。

#include "Winsock2.h"
#pragma comment(lib,"ws2_32.lib")

void main()
{
  char day[20];
  printf("Enter the short name of day");

  scanf("%s", day);

  switch(htonl(*((unsigned long*)day)))
  {
    case 'sun\0':
      printf("sunday");
      break;
    case 'mon\0':
      printf("monday");
      break;
    case 'Tue\0':
      printf("Tuesday");
      break;
    case 'wed\0':
      printf("wednesday");
      break;
    case 'Thu\0':
      printf("Thursday");
      break;
    case 'Fri\0':
      printf("friday");
      break;
    case 'sat\0':
      printf("saturday");
      break;
  }
}

已经在MSVC2010中测试过

- abelenky

---

不可移植。多字符常量的字节顺序未定义，与平台的字节序没有关联。 - Patrick Schlüter

在Windows x86上，使用这个编译器的实现时，我遇到了同一个编译器的两个版本之间发生变化的情况（Solaris-SPARC上的gcc v3与gcc v4）。 - Patrick Schlüter

Answer 9

您可以使用我的开关宏，它支持各种类型的值。对于一些情况，多次使用op==比每次创建映射并在其中查找快上几个数量级。

 sswitch(s) {
    scase("foo"): {
      std::cout << "s is foo" << std::endl;
      break; // could fall-through if we wanted
    }

    // supports brace-less style too
    scase("bar"):
      std::cout << "s is bar" << std::endl;
      break;

    // default must be at the end
    sdefault():
      std::cout << "neither of those!" << std::endl;
      break;
 }

- Johannes Schaub - litb

---

这将会花费O(n)。当然，创建一个映射表会花费更多的代价（特别是如果你在你的例子中使用它来处理三种情况），但如果你有很多情况并且运行switch语句很多次，那么这将是值得的。 - peoro

Answer 10

你可以使用任何类型的C/C++ 开关实现。你的代码将如下所示：

std::string name = "Alice";

std::string gender = "boy";
std::string role;

SWITCH(name)
  CASE("Alice")   FALL
  CASE("Carol")   gender = "girl"; FALL
  CASE("Bob")     FALL
  CASE("Dave")    role   = "participant"; BREAK
  CASE("Mallory") FALL
  CASE("Trudy")   role   = "attacker";    BREAK
  CASE("Peggy")   gender = "girl"; FALL
  CASE("Victor")  role   = "verifier";    BREAK
  DEFAULT         role   = "other";
END

// the role will be: "participant"
// the gender will be: "girl"

可以使用更复杂的类型，例如std::pairs或任何支持相等操作（或快速模式比较）的结构体或类。

特点

• 支持比较或检查相等性的任何数据类型
• 可能构建级联嵌套的开关语句。
• 可能中断或穿过CASE语句
• 可以使用非常量CASE表达式
• 可以启用带有树搜索的快速静态/动态模式（适用于C++11）

与语言开关的语法差异在于

• 大写关键字
• CASE语句需要括号
• 不允许在语句末尾使用分号“;”
• 不允许在CASE语句中使用冒号“:”
• CASE语句末尾需要BREAK或FALL关键字之一

在使用C++ 97语言时，使用线性搜索。在使用C++11及更现代的版本时，可以使用树搜索和快速模式，在这种情况下，CASE语句中的return语句将不再被允许。还存在使用char*类型和零终止字符串比较的C语言实现。

阅读有关此开关实现的更多信息。

- oklas