Как эффективно идентифицировать строковые команды?

Question

Учитывая серию команд и очень уникальный код, который необходимо запускать для каждой:

      if(cmd == "cmd.setBoosterRocket")
    ...
else if(cmd == "cmd.windSales")
    ...
else if(cmd == "cmd.selfDustruct")
    ...
else if(cmd == "cmd.unleashHounds")
    ...

Как это можно оптимизировать? Быть помещенным в оператор switch, то есть?

Я подумал о создании вектора хешей:

      std::hash<std::string> hasher;
for(std::string command : m_commandList)
    m_mashes.push_back(hasher(command)

Но к вектору нельзя получить доступ как часть оператора switch case, поскольку он не является constexpr. Список строковых команд известен во время компиляции, и я потенциально мог бы жестко закодировать хеш-значения ... но это не кажется хорошей идеей.

Answer 1

Один из возможных подходов - токенизация: сделать enumтипа и словаря. Таким образом, вы воспользуетесь преимуществом переключателя (более удобным для программиста и компилятора способом, чем жестко запрограммированные хэши) и получите только логарифмическую сложность.

      enum Command {SET_BOOSTER_ROCKET, WINDSALES, ETC};
const std::map<std::string, Command> commands = {
  {"cmd.setBoosterRocket", SET_BOOSTER_ROCKET},
  {"cmd.windsales", WINDSALES},
  {"othercommands", ETC},
};

А потом

      auto cmd_it = commands.find(cmd);
if(cmd_it == commands.end()) { // ERROR }
switch(cmd_it->second){
  case SET_BOOSTER_ROCKET:
    // your code
  break;
  case WINDSALES:
    // your code
  break;
  // etc
}

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

Answer 2

Что ж, напишите простую хеш-функцию для вашего варианта использования:

      static constexpr hasher = [](auto&& s){ return char(s.size() < xyz ? 0 : expr); };

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

Сохраняйте результаты в явно жестких рамках, чтобы компилятор предпочел таблицу переходов.

Затем используйте макрос, чтобы избежать повторения:

      #define CASE(s) \
        break; \
    case hasher(s): \
        if (std::string_view(s) != cmd) \
            break;

А теперь вы можете написать свой switch-оператор:

      switch (cmd) {
CASE("cmd.setBoosterRocket")
    ...
CASE("cmd.windSales")
    ...
CASE("cmd.selfDustruct")
    ...
CASE("cmd.unleashHounds")
    ...
...
}

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

Не забывай чтобы ограничить область действия макроса.

Answer 3

Другой способ - создать отдельные функции для обработки каждого случая, а затем создать карту в качестве «диспетчера»:

      const static std::unordered_map<std::string, void(*)()> dispatcher{ 
   { "cmd.setBoosterRocket",  &setBoosterRocketHandler },
   { "cmd.windSales",  &windSalesHandler },
   { "cmd.selfDustruct",  &selfDustructHandler },
   { "cmd.unleashHounds",  &sunleashHoundsHandler },
};

auto const it = dispatcher.find(cmd);

if (it == dispatcher.end()) { /* handle default case */ }
else { (*it)(); }

Answer 4

В C ++ 20 можно использовать для определения -lambda, чтобы сделать это эффективным.

      static constexpr auto commands = { "cmd.setBoosterRocket", "cmd.windSales", ... };

constexpr auto index = [&](std::string s) -> size_t { /*...*/ };

switch(quick_index(cmd))
{
    case index("cmd.setBoosterRocket"):
        // ...
        break;

    default:
        // ...
        break;
}

Для, чего не должно быть, вы можете, например, использовать unordered_map чтобы найти индекс строк в O(1).

Вот полный пример использования двоичного поиска (который constexpr, поэтому его можно использовать как для index а также quick_index).

      #include <algorithm>
#include <array>
#include <iostream>
#include <string_view>

using namespace std;

template<class ForwardIt, class T, class Compare = std::less<>>
constexpr ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp = {})
{
   first = std::lower_bound(first, last, value, comp);
   return first != last && !comp(value, *first) ? first : last;
}

int main()
{
    constexpr auto sorted = [](array<string_view, 3> a) {sort(a.begin(), a.end()); return a;};
    
    static constexpr auto commands = sorted({ "bar", "foo", "foobar" });
    
    constexpr auto index = [&](string_view s)
        { return binary_find(commands.begin(), commands.end(), s)-commands.begin(); };

    string_view cmd = "bar";

    switch(index(cmd))
    {
        case index("bar"):
            cout << "bartender" << endl;
            break;

        case index("foo"):
            cout << "fighter" << endl;
            break;

        case index("foobar"):
            cout << "fighter bartender" << endl;
            break;
            
        default:
            cout << "moo" << endl;
            break;
    }
}