c++ - std::map 或类似数据结构中的键压缩

Question

假设我想在 C++ 中存储键值。让我们进一步假设我有 1,000,000 个唯一键，它们仅映射到 100 个值，但每个键都有这 100 个值中的一个。

在 C++ 中是否有一种有效的方法来利用多次存在的多个值来压缩此查找表？

不知何故，在我的脑海中，它归结为 bool 逻辑最小化......但看看是否存在任何适用于 C++ 的库或数据结构会很有趣。

Answer 1

如果值的大小大于指针的大小，那么您可以保留指针/引用而不是值。

关于压缩查找表，我看到的唯一可行的解​​决方案是只填充映射一次，然后只执行读取操作(可以更改值，但不能添加)。如果是这种情况，那么您可以使用标准散列和修剪键值，这样每个桶的键都保持在区分它们所需的最小长度。这当然是假设您可以比较不完整的键，即 string 或类似的对象。