比较 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+）这些比较时，最好的方法是什么？

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 来使语法更好一点，特别是对于类成员函数。

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

然后进行一系列比较在与该独特特征匹配的字符串子集上

Answer 3

“12”并不是很多......但无论如何。

您只能将

switch

用于整数类型（

char

、

int

等），因此对于

std::string

来说这是不可能的。使用地图可能会更具可读性。

话又说回来，这完全取决于你如何定义“最好”。

Answer 4

这个问题的答案完全取决于问题本身。 您举了两个例子。 您可以在选项中添加哈希表、正则表达式等内容...

Answer 5

经过 8、10 甚至 12 次比较，您仍然可以使用

if ... else if ...

方案，没什么不好的。如果你想要 100 或其他东西，我建议编写一个函数来计算字符串的哈希值（即使通过简单地异或所有字符，但其他一些好的方法将更好地实现更好的分布），然后将其结果切换为 Evan建议的。如果函数为所有可能的输入字符串返回唯一的数字 - 那就更好了，并且不需要额外的比较。

Answer 6

如果您的意思是“最好”是“最高效”，请继续阅读。

如果确实很多的话我建议使用以下方法。
Switch 中的字符串实际上是 Java 7 中的内容。（作为Project Coin的一部分）

并且根据提案，这就是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);
}

Answer 7

您可以使用编译时哈希进行切换，并且使用 64 位哈希而不必担心冲突。这样做的一个很好的副作用是您编译的程序中不会包含字符串常量，可能会更小。

// compile-time FNV-1a hash
// see (https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function)
static constexpr std::uint64_t basis = 14695981039346656037ULL;
static constexpr std::uint64_t prime = 1099511628211ULL;
constexpr std::uint64_t c_hash(const char *str) {
    std::uint64_t hash{basis};
    while (*str != 0) {
        hash ^= str[0];
        hash *= prime;
        ++str;
    }
    return hash;
}
switch (c_hash(input)) {
    case c_hash("blah"): cout << "first"; break;
    case c_hash("blahblah"): cout << "second"; break;
    case c_hash("blahblahblah"): cout << "third"; break;
    default: cout < "what?"; break;
}