比较std::strings的最佳方法

Question

如何比较std::string？显而易见的方法是使用if/else：

std::string input;
std::cin >> input;

if ( input == "blahblahblah" )
{
    // do something.
}

else if ( input == "blahblah" )
{
    // do something else.
}

else if ( input == "blah" )
{
    // do something else yet.
}

// etc. etc. etc.

另一个可能的选择是使用std::map和switch/case。在进行大量（如8、10、12个以上）比较时，哪种方法最好？

- user542687

---

没错，只需使用从字符串到函数的映射。 - Ben

@Ben，你能把一个例子发到回答里吗？ - user542687

Answer 1

这里有一个使用std::map的例子。

#include <map>
#include <string>
#include <iostream>
#include <utility>

void first()
{
  std::cout << "first\n";
}

void second()
{
  std::cout << "second\n";
}

void third()
{
  std::cout << "third\n";
}


int main()
{
  typedef void(*StringFunc)();
  std::map<std::string, StringFunc> stringToFuncMap;

  stringToFuncMap.insert(std::make_pair("blah", &first));
  stringToFuncMap.insert(std::make_pair("blahblah", &second));
  stringToFuncMap.insert(std::make_pair("blahblahblah", &third));

  stringToFuncMap["blahblah"]();
  stringToFuncMap["blahblahblah"]();
  stringToFuncMap["blah"]();
}

输出结果为：

second
third
first

这种方法的好处有：

• 易于扩展。
• 它强制您将字符串处理例程拆分为单独的函数（通过意图编程）。
• 函数查找是O（log n），而您的示例是O（n）

请考虑使用boost :: function使语法更加流畅，特别是对于类成员函数。

- Ben

---

这看起来不错。但是我有一个问题，为什么你使用 stringToFuncMap.insert(std::make_pair("blah", &first)); 而不是 stringToFuncMap["blah"] = &first？ - user542687

operator[]可以很好地用于初始化映射。我只是习惯使用insert方法来初始化一个映射。这样会更加高效，因为operator[]将首先创建一个带有“second”默认初始化的std: pair。我认为Meyers的“Effective STL”深入涵盖了这个问题。 - Ben

Answer 2

使用operator==已经很好了，但如果性能真的很关键，您可以根据您的用例进行优化。如果目标是从几个选择中挑选一个并执行特定操作，则可以使用TRIE。此外，如果字符串足够不同，您可以像这样处理：

switch(s[0]) {
case 'a':
    // only compare to strings which start with an 'a'
    if(s == "abcd") {

    } else if (s == "abcde") {

    }
    break;
case 'b':
    // only compare to strings which start with an 'b'
    if(s == "bcd") {

    } else if (s == "bcde") {

    }
    break;
default:
    // we know right away it doesn't match any of the above 4 choices...
}

基本上在字符串中使用某个具有良好独特性的字符（如果所有字符串至少为N，则不必是第一个，N之前的任何字符都可以！）来执行switch，然后对匹配该唯一特征的一部分字符串进行一系列比较。

- Evan Teran

Answer 3

"

“12”不算很多……但无论如何。

您只能对整数类型（例如char、int等）使用switch，因此对于std::string来说这是行不通的。使用映射可能更易读。

然而，一切都取决于您如何定义“最佳”。

"

- Etienne de Martel

---

他们是否曾经修复过C++0x，以便hashstd::string("foo")成为constexpr？然后你就可以根据字符串的哈希值进行切换。 - KitsuneYMG

@KitsuneYMG 即使如此，如果发生冲突怎么办？你最终会得到具有相同值的多个标签。我认为哈希值不适合用作开关的标签。 - Etienne de Martel

@EtiennedeMartel 你可以使用 static_assert 或 assert 进行检查。 - user1095108

Answer 4

如果你所说的“最好”是指“最有效率”，请往下看。

如果确实有很多字符串，我建议使用以下方法。
在Java 7中，Switch语句中的String实际上是Project Coin的一部分。

根据proposal，这是Java语言将要实现的方式。首先，计算每个字符串的哈希值。然后，这个问题就变成了一个“switch int”问题，大多数当前语言都支持，并且效率很高。在每个case语句中，您需要检查这是否真的是该字符串（在极少数情况下，不同的字符串可能会哈希到相同的int）。
我个人在实践中有时不执行最后一步，因为它的必要性取决于特定程序所处的情况，即字符串是否可能在程序员的控制范围内以及程序需要多么健壮。

以下是示例伪代码。

String s = ...
switch(s) {
 case "quux":
    processQuux(s);
    // fall-through

  case "foo":
  case "bar":
    processFooOrBar(s);
    break;

  case "baz":
     processBaz(s);
    // fall-through

  default:
    processDefault(s);
    break;
}

从上述提案来帮助您理解。

// Advanced example
{  // new scope for synthetic variables
  boolean $take_default = false;
  boolean $fallthrough = false;
  $default_label: {
      switch(s.hashCode()) { // cause NPE if s is null
      case 3482567: // "quux".hashCode()
          if (!s.equals("quux")) {
              $take_default = true;
              break $default_label;
          }
          processQuux(s);
          $fallthrough = true;
                case 101574: // "foo".hashCode()
          if (!$fallthrough && !s.equals("foo")) {
              $take_default = true;
              break $default_label;
          }
          $fallthrough = true;
      case 97299:  // "bar".hashCode()
          if (!$fallthrough && !s.equals("bar")) {
              $take_default = true;
              break $default_label;
          }
          processFooOrBar(s);
          break;

      case 97307: // "baz".hashCode()
          if (!s.equals("baz")) {
              $take_default = true;
              break $default_label;
          }
          processBaz(s);
          $fallthrough = true;

      default:
          $take_default = true;
          break $default_label;
      }
  }
  if($take_default)
      processDefault(s);
}

- Haozhun

---

问题是关于C++（std::string）的 :) - Tiago

Answer 5

这个问题的答案很大程度上取决于具体的问题。你提到了两个例子，还可以考虑使用哈希表、正则表达式等其他选项...

- Edward Strange

Answer 6

使用8、10甚至12次比较，您仍然可以使用if ... else if ...方案，没有任何问题。 如果要进行100次或其他操作，我建议编写一个函数来计算字符串的哈希值（即使通过简单地异或所有字符，但某些其他好的方法对于更好的分布更可取），然后根据Evan的建议切换其结果。 如果函数为所有可能的输入字符串返回唯一的数字-那就更好了，并且不需要额外的比较。

- mike.dld