C++ 固定容量关联容器

Question

我正在寻找像 std::unordered_map 这样不使用任何动态分配的容器。我相信对于任何具有固定数量键的关联容器，甚至是必须在编译时选择的键，都是这种情况。

我不是在寻找 constexpr 或编译时哈希映射，因为我希望能够更新映射中的值。

示例用例：

FixedCapacityMap<std::string_view, int> fruits {
  {"n_apples", 0},
  {"n_pairs", 0}
}

fruits["n_apples"] += 1;
fruits["n_pairs"] += 1;

有谁知道这样的库是否存在，如果不存在，如何实现这样的库？

Answer 1

“无动态分配”规则的必然结果是底层数据嵌入到您的类型中，因此您还需要将键的数量指定为模板参数。

如果密钥在编译时已知，您可以在其上构造一个 fixed-size 散列 table。

一般来说，下一个最好的方法是链式哈希或二进制搜索。这是一个使用二进制搜索 std::array<std::pair<K,V>, N>:

的小实现

template <class K, class V, size_t N>
class FixedCapacityMap {
    public:
        using value_type = std::pair<K,V>;
        FixedCapacityMap(std::initializer_list<value_type> init) {
            assert(init.size() == N);
            std::copy(cbegin(init), cend(init), begin(store));
        }

        V& operator[](const K& key) {
            auto it = std::lower_bound(begin(store), end(store), std::pair{key, V()});
            if (it == end(store) || it.first != key)
                throw std::out_of_range(key);
            return it.second;
        }

    private:
        std::array<value_type, N> store;
}

Answer 2

我找到了具有此功能的库：

https://github.com/serge-sans-paille/frozen

它允许 constexpr 和 constinit 有序和无序映射（我新添加的）能够在运行时更新值。

C++ 固定容量关联容器

C++ fixed-capacity associate container

c++

dictionary

associative-array

stdmap