Лучший способ сравнить std:: strings

Каков наилучший способ сравнить std::string s? Очевидным было бы с 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+) этих сравнений?

Ответ 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::, чтобы сделать синтаксис немного приятнее, особенно с функциями члена класса.

Ответ 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, а затем сделать серию сравнивается с подмножеством строк, которые соответствуют этой уникальной характеристике

Ответ 3

"12" не много... но в любом случае.

Вы можете использовать только switch для интегральных типов (char, int и т.д.), так что не может быть и речи о std::string. Использование карты, вероятно, было бы более читаемым.

И снова все зависит от того, как вы определяете "лучший".

Ответ 4

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

Ответ 5

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

Ответ 6

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

Я предлагаю использовать следующий метод, если действительно много.
String в Switch на самом деле что-то будет в Java 7. (В рамках Монета проекта)

И в соответствии с предложением так будет реализован 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);
}