C / C ++: переключатель для нецелых - PullRequest
Новая
       12

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

53 голосов
/ 12 ноября 2010

Часто мне нужно выбрать, что делать, в соответствии со значением элемента, не являющегося постоянным 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 s, но все же эти хаки потребует большого количества кодирования, что сделает все более сложным и сложным в обслуживании.

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

Ответы [ 16 ]

56 голосов
/ 12 ноября 2010

Используя некоторые неприятные макросы и шаблонную магию, можно получить развернутый двоичный поиск во время компиляции с красивым синтаксисом, но MATCHES ("case") должны быть sorted : 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 ++.

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

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

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

Полная версия доступна на github: Smilingthax / Cttrie .

28 голосов
/ 12 ноября 2010

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

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

15 голосов
/ 12 ноября 2010

Вы можете достичь этого, не используя карту или unordered_map, как показано ниже.Сравните только первый символ, чтобы определить, какая строка.Если более одного совпадения, вы можете вернуться к цепочке if / else внутри этого оператора case.Количество сравнений будет значительно сокращено, если не будет много строк, начинающихся с одной и той же буквы. 

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
    }
}

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

10 голосов
/ 12 ноября 2010

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

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

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

5 голосов
/ 12 ноября 2010

В 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 (мин., n )) если n - длина вашей входной строки, а m длина самого длинного ключевого слова - использовать конечное состояниерешение, такое как программа Lex.

4 голосов
/ 25 мая 2013

По духу это похоже на решения lambda и 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);
}
4 голосов
/ 12 ноября 2010

Что-то подобное будет слишком сложным? 

#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"
}
3 голосов
/ 03 сентября 2013

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

Это должно работать.
(но ТОЛЬКО для строк длиной 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

1 голос
/ 13 января 2017

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);

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

1 голос
/ 08 октября 2016

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

Особенности

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

Различия по синтаксису при переключении языка:

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

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

Чтение Подробнее о этой реализации переключателя.

Страница:
...