How to efficiently identify string commands?

Question

Given a series of commands and very unique code that must be run for each:

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

How might this be optimized? Be put into a switch statement, that is?

I considered making a vector of hashes:

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

But a vector cannot be accessed as part of a switch case statement as it is not a constexpr. The list of string commands is known at compile time, and I could potentially hardcode the hash values...but that does not seem like a great idea.

Toss all of the possibilities into a [`std::unordered_map`](https://en.cppreference.com/w/cpp/container/unordered_map) that maps a `std::string` to a [`std::function`](https://en.cppreference.com/w/cpp/utility/functional/function) that performs the desired action. If you don't care about error checking, that reduces the whole shebang to `mymap[cmd]();`. But you really should care about error checking. It doesn't add too much extra code, and it makes debugging a LOT easier. — user4581301, May 10 '21 at 19:02
You can implement a pretty good approximation of a compile-time constant map with a sorted array of pairs. You can then `std::binary_search` for the command in that array. — François Andrieux, May 10 '21 at 19:08
@FrançoisAndrieux unfortunately, [std::binary_search](https://en.cppreference.com/w/cpp/algorithm/binary_search) doesn't do what you think it does. That'd be too simple for C++! You want [std::lower_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound). — Aykhan Hagverdili, May 10 '21 at 20:18
@AyxanHaqverdili Oops, you're right. That gets me every time, it isn't the first time I've made that mistake. — François Andrieux, May 10 '21 at 20:31

score 6 · Accepted Answer · answered May 10 '21 at 19:26

One possible approach is tokenization: make an enum type and a dictionary. This way you take advantage of the switch (in a more programmer and compiler friendly way than hard-coded hashes) and have just logarithmic complexity.

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

And then

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
}

Tokenizing like this your commands might be a little tedious if you have a lot to start, but then it has a good balance between scalability and readability.

Deduplicator · Answer 2 · 2021-05-11T12:47:29.283

4

Well, write a simple hash-function for your use-case:

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

You could also take advantage of your std::string having a minimum reserved size if it uses SBO (just about all of them do), and drop the size-check above for more performance.

Keep the results in obviously tight bounds to get the compiler to favor a jump-table.

Next, use a macro to avoid repetition:

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

Yes, you can not use the (mis-?)feature fallthrough. If you really want it for one of them, use goto.

And now you can write your switch-statement:

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

Most compilers can warn you about duplicate case-statements, so fiddle with the hash until you get it cheap, unique, and tightly bound.

Don't forget #undef CASE to limit the macros scope.

edited May 11 '21 at 12:47

answered May 10 '21 at 19:38

Deduplicator

44,692
7
66
118

The `break;` in the macro would cause trouble in the first `case:`. – Aykhan Hagverdili May 10 '21 at 20:09
Why? Code in a switch is just code in a switch, whether it is reachable or dead. – Deduplicator May 10 '21 at 20:09
Looks like you're right. I didn't know you can start a `switch` with anything but a case. This is so random https://gcc.godbolt.org/z/TosbMWGnM – Aykhan Hagverdili May 10 '21 at 20:13
If you want to see something crazy one can do with switch in C and C++, see [Duff's device](//en.wikipedia.org/wiki/Duff's_device) – Deduplicator May 10 '21 at 20:53
Wow. That's...amazing. – Aykhan Hagverdili May 10 '21 at 21:04

Aykhan Hagverdili · Answer 3 · 2021-05-10T21:13:44.617

Another way would be to create separate functions to handle each case, then create a map as a "dispatcher":

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

score 1 · Answer 4 · answered May 15 '21 at 21:41

With C++20, constexpr can be utilized to define an index-lambda to make this efficient.

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

For quick_index, which doesn't have to be constexpr, you could e.g. use an unordered_map to look up the index of the strings in O(1).

Here's a full example using a binary search (which is constexpr, so it can be used both for index and 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;
    }
}

How to efficiently identify string commands?

4 Answers4

Linked