C/С++: переключатель для нецелых чисел

Часто мне нужно выбрать, что делать в соответствии со значением элемента константы, отличного от POD, примерно так:

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

Печально switch может использоваться только с целыми числами: error: switch quantity not an integer.

Самый тривиальный способ реализовать такую ​​вещь - значит, это последовательность if s:

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

Но это решение выглядит грязным и должно стоить O (n), где n - количество случаев, тогда как эта часть кода может стоить O (log n) в худшем случае с двоичным поиском.

Используя некоторые структуры данных (например, Карты), можно получить целое число, представляющее строку (O (log n)), а затем использовать O (1) switch или реализовать статическую двоичную сортировку путем правильного вложения if, но все же эти хаки потребуют много кодирования, делая все более сложным и сложным для поддержания.

Какой лучший способ сделать это? (быстрый, чистый и простой, как и оператор switch)

4b9b3361

Используя некоторые неприятные макросы и шаблонные магии, можно получить развернутый двоичный поиск в compiletime с симпатичным синтаксисом - но MATCHES ( "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 неявные, вы не можете упасть. Извините. Но вы обнаружите, что есть еще несколько возможностей использования, посмотрите. ПРИМЕЧАНИЕ. Проверяется только с помощью g++.

Обновление С++ 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: время компиляции

Мой новый подход к этой проблеме использует передовое метапрограммирование С++ 11 для сгенерируйте search-trie во время компиляции. В отличие от предыдущих подходов, это будет обрабатывать несортированныеcase-ветки/строки просто отлично; они должны быть только строковыми литералами. g++ также допускает constexpr для них, но не clang (как из HEAD 3.9.0/trunk 274233).

В каждом trie node оператор switch используется для использования расширенного генератора кода компилятора.

Полная реализация доступна в github: smilingthax/cttrie.

51
ответ дан 12 нояб. '10 в 16:54
источник

В С++ вы можете получить производительность O(lg n), имея std::map<std::string, functionPointerType>. (В C вы могли бы реализовать то, что было по существу тем же, но было бы сложнее) Вытащите нужный указатель функции, используя std::map<k, v>::find, и вызовите этот указатель. Конечно, это будет не так просто, как оператор switch, поддерживаемый языком. С другой стороны, если у вас достаточно элементов, которые будут иметь огромную разницу между O(n) и O(lg n), это, вероятно, указывает на то, что вы должны пойти на другой дизайн в первую очередь.

Лично я всегда знал, что цепочка ELSEIF будет более читаемой.

28
ответ дан 12 нояб. '10 в 16:38
источник

Вы можете достичь этого, не используя любую карту или 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
    }
}

Это выглядит как оптимальное решение без каких-либо затрат, даже если оно не стандартное.

15
ответ дан 12 нояб. '10 в 17:20
источник

Используйте if...else block. У вас на самом деле нет веской причины не делать этого, кроме того, что это не красиво смотреть, а блок if...else - это самое простое решение.

Все остальное требует дополнительного кода, который, как говорят, увеличивает сложность. И это просто переводит уродство в другое место. Но на каком-то уровне все еще должно произойти сравнение строк. Теперь вы только что накрыли его большим количеством кода.

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

9
ответ дан 12 нояб. '10 в 16:45
источник

В 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 },
    ...
};

и выполните двоичный поиск на них. Предыдущее прямо из исходного кода awk от C гроссмейстера Брайана У. Кернигана.

Другое решение, которое равно O (min (m, n)), если n - длина вашей входной строки и m - длина самого длинного ключевого слова, - это использование решения с конечным состоянием, такого как программа Lex.

5
ответ дан 12 нояб. '10 в 16:57
источник

Что-то вроде этого было бы слишком сложным?

#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"
}
4
ответ дан 12 нояб. '10 в 16:46
источник

Это аналогично по духу решениям лямбда и 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);
}
3
ответ дан 25 мая '13 в 7:37
источник

Вот пример кода, который работает:

Это должно работать.
(но ТОЛЬКО на строки, которые составляют 4 байта или меньше)

Это рассматривает строки как 4-байтовые целые числа.

Это считается уродливым, не переносимым, "взломанным" и совсем не хорошим. Но он делает то, что вы хотели.

#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

3
ответ дан 03 сент. '13 в 15:26
источник

Вы можете использовать любую версию 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, или любые структуры или классы, которые поддерживают операции равенства (или comarisions для быстрого режима).

Функции

  • любые типы данных, которые поддерживают сравнения или проверяют равенство
  • возможность создания каскадных вложенных статусов коммутаторов.
  • возможность прерывания или падения по операторам case
  • возможность использования выражений case non constatnt
  • можно включить быстрый статический/динамический режим с поиском дерева (для С++ 11)

Различия в Sintax с языковым переключателем

  • заглавные слова
  • нужны скобки для оператора CASE
  • точка с запятой ';' в конце инструкций не допускается
  • двоеточие ':' в операторе CASE не разрешено
  • требуется одно из BREAK или FALL в конце оператора CASE.

Для языка C++97 используется линейный поиск. Для C++11 и более современных можно использовать quick режим поиска wuth tree, где оператор возврата в CASE становится недопустимым. Реализация языка C существует там, где используется тип char* и строковые сравнения с нулевым завершением.

Прочитайте подробнее о реализации этого коммутатора.

1
ответ дан 08 окт. '16 в 20:24
источник

вы все равно можете использовать переключатель. Если вы знаете метки перед рукой.. (это довольно неприятно (т.е. никаких проверок, но это должно быть тривиально добавлять до тех пор, пока у вас есть строка с нулевым завершением!), Я должен представить, что это выполняется быстрее, чем большинство опций?

//labels: "abc", "foo", "bar", "ant" "do"

switch(lbl[0])
{
  case 'a':
  {
    switch(lbl[1])
    {
      case 'b': // abc
      case 'n': // ant
      default:  // doofus!
    }
  }
  case 'b':
  {
    switch(lbl[1])
    {
      case 'a': //bar
      default:  // doofus
    }
  }
  case 'd':
  {
    switch(lbl[1])
    {
      case 'o': //do
      default:  // doofus
    }
  }
  case 'f':
  {
    switch(lbl[1])
    {
      case 'o': //foo
      default:  // doofus
    }
  }
}

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

1
ответ дан 12 нояб. '10 в 17:04
источник

Мне приходит в голову генератор хэшей, основанный на метапрограммировании, который вы можете использовать как в этом примере. Это для С++ 0x, но я уверен, что вы можете воспроизвести его аналогично для стандартного С++.

1
ответ дан 12 нояб. '10 в 16:56
источник

Вы можете использовать макросы , которые поддерживают все типы значений. В некоторых случаях использование 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;
 }
1
ответ дан 20 дек. '10 в 9:00
источник

Обратите внимание, что переключение на const char * не будет работать так, как предполагалось, даже если это разрешено.

A C Строка на самом деле является указателем на char. Код, который вы предположили:

// pseudocode (incorrect C!):
switch(str) {
   case "a": ...
   case "b": ...
}

Если наш язык согласован - он будет сравнивать значения указателя, а не фактическое содержимое строки. Для сравнения строк требуется strcmp(), поэтому даже если у компилятора был особый случай, например "если мы переключаемся на char*, используйте strcmp() вместо == (что, вероятно, было бы плохой дизайн языка) то в любом случае компилятору было бы невозможно сделать эту работу подобно O (1) взлому с целыми числами и переходами.

Так что не чувствуйте себя плохо для C/С++, поскольку он не поддерживается.:)

Я рекомендую решение O (logn) с картой (string -> funcptr) или (string -> some abstract object) - если вы чувствуете, что вам нужна масштабируемость. Если вы этого не сделаете, нет ничего особенно плохого в решении O (n) с else if. Он по-прежнему прозрачный, поддерживаемый код, поэтому вам не о чем беспокоиться.

0
ответ дан 12 нояб. '10 в 16:46
источник

Некоторое время назад я написал шаблонный класс, получивший какой-то эквивалент коммутатора, который можно использовать в любом типе данных. Однако есть некоторые ограничения, которые ограничивают его поля приложения:

  • задача достижения каждой ветки должна быть вызовом функции.
  • функции для вызова имеют один аргумент (или ни один, ни два, вы можете настроить шаблон, но он должен быть одинаковым для всех функций).
  • значение аргумента, переданное функциям, будет одинаковым в каждом случае (но оно дается в момент выполнения переключателя).

В качестве примера, скажем, вы хотите включить значение типа MyType, если оно равно value1, вызовите function1("abc"), если оно равно value2, вызовите function2("abc") ( и так далее). Это закончилось бы так:

// set up the object
//               Type  -        function sig       - function arg. type
SWITCH mySwitch< MyType, void(*)(const std::string&), std::string >;
mySwitch.Add( value1, function1 );
mySwitch.Add( value2, function2 );
mySwitch.AddDefault( function_def );

// process the value
MyType a =...// whatever.
mySwitch.Process( a, "abc" );

В принципе, он обертывает контейнер std:: map, удерживая значение/функцию пары. Он также может обрабатывать "по умолчанию", что делает такой интерес интересным. Его можно легко адаптировать к другим ситуациям. Вот код:

template < typename KEY, typename FUNC, typename ARG >
class SWITCH
{
    public:
    SWITCH()
    {
      Def = 0; // no default function at startup
    }

    void Process( const KEY& key, ARG arg )
    {
      typename std::map< KEY, FUNC >::const_iterator it = my_map.find( key );
      if( it != my_map.end() )  // If key exists, call
         it->second( arg );    // associated function
      else               // else, call
        if( Def )       // default function, if there is one.
           Def( arg );  // else, do nothing
    }

    void Add( const KEY& key, FUNC my_func )
    {
      typename std::map< KEY, FUNC >::const_iterator it = my_map.find( key );
      if( it != my_map.end() )
      {
        throw "Already defined !\n";
      }
      my_map[ key ] = my_func;
    }

    void AddDefault( FUNC f )
    {
      Def = f;
    }

 private:
   std::map< KEY, FUNC > my_map;
   FUNC Def; // default function
 };

Другие сведения здесь.

0
ответ дан 10 янв. '13 в 20:06
источник

Хеши свой путь к Победе

Вы можете использовать хэш-функцию времени компиляции, как в этом славном переполнении стека answer. Если вы создаете функции

  • int_crc32_s, который возвращает хеш строки во время выполнения и
  • int_crc32, который возвращает хэш строки во время компиляции

вы настроены. Чтобы обрабатывать ложное соответствие crc вашей ключевой строки и строки case, вам нужно включить явную проверку соответствия. Это не влияет на производительность, потому что это всего лишь одна проверка, но она делает ее намного уродливее, а макро версия выглядит намного приятнее.

Я нашел эти две строки, у которых тот же CRC32.

//two strings that yield same crc32
const char* collision1="DeferredAmbient_6_1_18-1of2_5";
const char* collision2="PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19";

Без макросов

//without macros (you need to check for collisions)
switch( int_crc32_s(str.c_str()) )
{
    case int_crc32("foo"): if( str=="foo"){std::cout << "foo you\n"; break;}
    case int_crc32("bar"): if( str=="bar"){std::cout << "bar you\n"; break;}
    case int_crc32("baz"): if( str=="baz"){std::cout << "baz you\n"; break;}
    case int_crc32("PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"):
        if( str=="PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"){
            std::cout << "jackpot!\n"; break;
        }
    default: std::cout << "just you\n";
}

С макросами

//convenient macros
#define S_SWITCH( X ) const char* SWITCH_KEY(X.c_str()); switch( int_crc32_s(X.c_str()) )
#define S_CASE( X ) case int_crc32(X): if( strcmp(SWITCH_KEY,X) ){ goto S_DEFAULT_LABEL;}
#define S_DEFAULT S_DEFAULT_LABEL: default:

//with macros
S_SWITCH( str )
{
    S_CASE("foo"){ std::cout << "foo you\n"; break; }
    S_CASE("bar"){ std::cout << "bar you\n"; break; }
    S_CASE("baz"){ std::cout << "baz you\n"; break; }
    S_CASE("PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"){ std::cout << "jackpot!\n"; break; }
    S_DEFAULT{ std::cout << "just you\n"; }
}    

Полная реализация [gist]

// This is a demonstration of using a COMPILE-TIME hash to do a
// switch statement with a string to answer this question.
//
// https://stackoverflow.com/info/4165131/c-c-switch-for-non-integers
//
// It is based on the StackOverflow question:
// https://stackoverflow.com/info/2111667/compile-time-string-hashing
//
// And the solution
// /info/9803/compile-time-string-hashing/66117#66117
//

#include <iostream>
#include <string>
#include <vector>
namespace detail {

// CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] =
{
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

//constexpr combine
template<size_t idx>
constexpr uint32_t combine_crc32(const char * str, uint32_t part) {
  return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
}

//constexpr driver
template<size_t idx>
constexpr uint32_t crc32(const char * str) {
  return combine_crc32<idx>(str, crc32<idx - 1>(str));
}

//constexpr recursion stopper
template<>
constexpr uint32_t crc32<size_t(-1)>(const char * str) {
  return 0xFFFFFFFF;
}

//runtime combine
uint32_t combine_crc32_s(size_t idx, const char * str, uint32_t part) {
  return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
}

//runtime driver
uint32_t crc32_s(size_t idx, const char * str) {
  if( idx==static_cast<size_t>(-1) )return 0xFFFFFFFF;
  return combine_crc32_s(idx, str, crc32_s(idx-1,str));
}

} //namespace detail

//constexpr that returns unsigned int
template <size_t len>
constexpr uint32_t uint_crc32(const char (&str)[len]) {
  return detail::crc32<len - 2>(str) ^ 0xFFFFFFFF;
}

//constexpr that returns signed int
template <size_t len>
constexpr int int_crc32(const char (&str)[len]) {
  return static_cast<int>( uint_crc32(str) );
}

//runtime that returns unsigned int
uint32_t uint_crc32_s( const char* str ) {
  return detail::crc32_s(strlen(str)-1,str) ^ 0xFFFFFFFF;
}

//runtime that returns signed int
int int_crc32_s( const char* str) {
  return static_cast<int>( uint_crc32_s(str) );
}

//convenient macros
#define S_SWITCH( X ) const char* SWITCH_KEY(X.c_str()); switch( int_crc32_s(X.c_str()) )
#define S_CASE( X ) case int_crc32(X): if( strcmp(SWITCH_KEY,X) ){ goto S_DEFAULT_LABEL;}
#define S_DEFAULT S_DEFAULT_LABEL: default:

int main()
{
    std::string str;
    std::cin >> str;

    //two strings that yield same crc32
    const char* collision1="DeferredAmbient_6_1_18-1of2_5";
    const char* collision2="PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19";

    //without macros (you need to check
    switch( int_crc32_s(str.c_str()) )
    {
        case int_crc32("foo"): if( str=="foo"){std::cout << "foo you\n"; break;}
        case int_crc32("bar"): if( str=="bar"){std::cout << "bar you\n"; break;}
        case int_crc32("baz"): if( str=="baz"){std::cout << "baz you\n"; break;}
        case int_crc32("PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"):
            if( str=="PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"){
                std::cout << "jackpot!\n"; break;
            }
        default: std::cout << "just you\n";
    }

    //with macros
    S_SWITCH( str )
    {
        S_CASE("foo"){ std::cout << "foo you\n"; break; }
        S_CASE("bar"){ std::cout << "bar you\n"; break; }
        S_CASE("baz"){ std::cout << "baz you\n"; break; }
        S_CASE("PostEffect_Lighting_18_6-0of1_8_14_13-1of2_19"){ std::cout << "jackpot!\n"; break; }
        S_DEFAULT{ std::cout << "just you\n"; }
    }
}
0
ответ дан 21 июля '17 в 1:20
источник

LLVM имеет llvm::StringSwitch, который вы бы использовали следующим образом:

Color color = StringSwitch<Color>(argv[i])
   .Case("red", Red)
   .Case("orange", Orange)
   .Case("yellow", Yellow)
   .Case("green", Green)
   .Case("blue", Blue)
   .Case("indigo", Indigo)
   .Cases("violet", "purple", Violet)
   .Default(UnknownColor);

Основная победа здесь в том, что никаких проблем из-за хеш-коллизий нет: независимо от того, какие фактические строки всегда сравниваются до того, как будет принят случай.

0
ответ дан 13 янв. '17 в 19:11
источник