A Semi Compile Run-time Map with Nearly Zero Overhead Lookup

演讲主题一个静态map，保证O1查询，动态修改，还没有碰撞问题

作者列出了一个场景，自己使用的是static std::unordered_map，然后经常调用try_emplace，这会有碰撞问题

干脆直接搞一个compile-time map，比如 “constexpr all the things”³提到的 cx::map 或者boost::hana::map

但是场景要求，运行时改动，编译期查询，不需要提前知道kv对

针对这种需求，设计KV，要考虑k是非类型模板参数NTTP，但是这个c++20才支持，解决办法和boost::hana用的技巧相同，一个lambda包起来，然后把这个lambda key转成type key，兜一圈

template <auto...> struct dummy_t{};
template <typename Lambda>
constexpr auto key2type(Lambda lambda){
  return dummy_t<lambda()>{};
}
#define ID(x) []() constexpr {return x;}
//map<decltype(key2type(ID(5)))>

对于字符串还是有点问题，需要把foo展开成dummy_t<f,o,o>

template <typename Lambda, std::size_t... I>
constexpr auto str2type(Lambda lambda, std::index_sequence<I...>){
    return dummy_t<lambda()[i]...>{};
}

template <typename Lambda>
constexpr auto key2type(Lambda lambda){
  return array2type(lambda,std::make_index_sequence<strlen(lambda())>{});
}

这代码写的，make_index_sequence生成一组序列，然后dummy_t里的lambda()[I]…正好是数组展开，“foo” -> “f”, ‘o’,’o’ 写的真是绝了(好像我在那见过boost::hana用过一样的技术)

整体实现大框如下

template <typename Key, typename Value>
class static_map{
public:
  template <typename Lambda>
  static Value& get(Lambda lambda){
    static_assert(std::is_convertialb_v<decltype(lambda()),Key>);
    return get_internal<decltype(key2type(lambda))>();
  };
private:
  template <typename>
  static Value& get_internal(){
    static Value value;
    return value;
  }
};

这实际上还是个静态表，没有动态能力，实现方案还是加个std::unordered_map，加在get_internal存指针，如果值变了，直接placement new，这个方案还是有unordered_map的问题，调用开销。不能放在get_interal

最终方案就是placement new了，内部数组保存value(根据Value类型可能有多分)，和一个runtime_map，这个map保存key和value数组指针，init_flag用来维护初始化

struct ConstructorInvoker{
    constructorInvoker(char* mem){
        new(mem) Value;
    }
};

template <typename>
static Value& get_internal(){
    alignas (Value) static char storage[sizeof(Value)];
    static ConstructorInvoker invoker(storage);
    return *reinterpret_cast<Value*> (storage);
}

这个reinterpret_cast用法明显是错的，是UB，针对这种场景c++17新增了上 std::launder函数来解决这个问题

另外这个ConstructorInvoker只调用一次，用init_flag在需要的时候初始化会更合适一些

template <typename>
static Value& get_internal(){
    alignas (Value) static char storage[sizeof(Value)];
    static bool needs_init = true;
    if (needs_init){
        init(key,storage,needs_init); needs_init=false;
    }
    return *std::launder(reinterpret_cast<Value*> (storage));
}

更进一步，可以加上__builtin_expect分支优化加速

if (__builtin_expext(need_flags, false))
    ...

init函数怎么搞

placement new + std::move ，保存指针保存unique_ptr，要注意，数组需要保留，多次placement new，所以要指定析构器，只析构，不回收内存，析构了的话，保证下次placement new，需要重置init_flag https://github.com/hogliux/semimap/blob/de556c74721a5017f5a03faf2fbd1c6e5a768a32/semimap.h#L198

剩下的就是讨论突破static局限以及各种map性能测试了，semimap可以理解成一个unordered_map 静态加强版

reference

https://github.com/CppCon/CppCon2018/tree/master/Presentations/a_semi_compileruntime_map_with_nearly_zero_overhead_lookup
https://github.com/hogliux/semimap
https://github.com/CppCon/CppCon2017/tree/master/Presentations/constexpr%20ALL%20the%20things
1. 代码在这里https://github.com/lefticus/constexpr_all_the_things
限于篇幅，很多enable_if都省略了，可以看参考链接2中的源代码

或者到博客上提issue 我能收到邮件提醒。