Reimplement reverse key lookup with a sorted vector

It's more efficient than map due to compact storage.

diff --git a/source/input/keys.cpp b/source/input/keys.cpp
index 9b3349ac443346ca6e6e5e5867a9c9434e74cc54..d5687ae2c9e1142a92bc8b6d8b4844a2c0b3a1d6 100644 (file)
--- a/source/input/keys.cpp
+++ b/source/input/keys.cpp
@@ -1,6 +1,7 @@
 #include "keys.h"
-#include <map>
 #include <stdexcept>
+#include <vector>
+#include <msp/core/algorithm.h>
 #include <msp/strings/format.h>
 
 using namespace std;
@@ -12,21 +13,25 @@ extern unsigned sys_keymap[];
 
 unsigned key_from_sys(unsigned code)
 {
-       static bool init_done = false;
-       static map<unsigned, unsigned> reverse_map;
+       struct MappedKey
+       {
+               unsigned code;
+               Key key;
+       };
+
+       static vector<MappedKey> reverse_map;
 
-       if(!init_done)
+       if(reverse_map.empty())
        {
                for(unsigned i=0; i<N_KEYS_; ++i)
                        if(sys_keymap[i])
-                               reverse_map[sys_keymap[i]] = i;
-
-               init_done = true;
+                               reverse_map.push_back({ sys_keymap[i], static_cast<Key>(i) });
+               sort_member(reverse_map, &MappedKey::code);
        }
 
-       auto i = reverse_map.find(code);
-       if(i!=reverse_map.end())
-               return i->second;
+       auto i = lower_bound_member(reverse_map, code, &MappedKey::code);
+       if(i!=reverse_map.end() && i->code==code)
+               return i->key;
 
        return 0;
 }