Лучший способ сравнить 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

Если вы имеете в виду «самый эффективный» под «лучшим», читайте дальше.

Я предлагаю использовать следующий метод, если их действительно много.
Строка в 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 5

С 8, 10 и даже 12 сравнениями вы все еще можете использовать if ... else if ... схему, ничего плохого.Если вы хотите 100 или что-то еще, я бы порекомендовал написать функцию, которая будет вычислять хеш строки (даже путем простого кеширования всех символов, но для лучшего распределения предпочтителен другой хороший метод), а затем переключать его результат как Эванпредложил.Если функция возвращает уникальные числа для всех возможных входных строк - это даже лучше и не требует дополнительных сравнений.

Answer 6

Ответ на этот вопрос слишком зависит от проблемы.Вы назвали два примера.Вы можете добавить к своим опциям такие вещи, как хеш-таблицы, регулярные выражения и т. Д. *