我想实现一个字典，将唯一的异构数据（变体）与唯一的int配对，这样我就可以重复int，而不是重复值（可能很大）。当需要时，我会通过字典将其转换为原始值。
数据集将很大，因此O(1)中的（int->data）很重要。（data->int）和insert/delete都应该是O(log n)的平均大小写，因为这些操作不那么重要。数据的顺序无关紧要，但插入/删除不能使现有的int键无效。
我尝试过哈希表和SSTable方法。对于哈希表，即使使用哈希值作为标记，而不是将其与值一起存储，所需的存储空间也相当高。冲突降低了效率，但所有操作的分摊复杂性为O(1)。另一方面，SSTable为操作提供了更糟糕的复杂性，并复制了值（一次用于向量存储，一次用于映射索引）。总体内存消耗仅略低于哈希表字典的内存消耗。
字典摘要要求：
- 查找int->数据：O（1）
- 查找数据->最坏情况下为int:O（logn）
- 插入：最坏情况下为O（log n）
- 删除：最坏情况下为O（logn）[或其他方法，如垃圾收集，如果不一直运行，可能会执行得更糟]
- 可能的最低内存要求
有没有办法改进字典的设计，以进一步降低内存需求，同时保留O(1) int->data查找和合理的插入/删除/data->int？
如果int->数据速度是最重要的，那么您应该将其设置为只进行数组索引操作。
将数据对象保存在std::vector<data> forward_map中。int->数据只是一个forward_map[i]查找，它是O（1），具有尽可能低的常数因子。
使用单独的数据结构来支持搜索/插入/删除操作
根据"数据"对象支持的比较操作，二进制搜索树或std:：无序集可能是不错的选择。BST/集的"值"类型只是int，但根据i < j，对这些int的比较实际上比较的是forward_map[i] < forward_map[j]，而不是。
假设你有一个std::unordered_set< forward_map_reference_t > reverse_map。（使用STL容器并不是那么容易，请参阅下文。）
我们实际上使用一个集合作为映射：键是forward_map[val]，值是int val本身
要查找给定int k的reverse_map条目，您需要实际搜索forward_map[k]。
-
const data_t & lookup(int k) { return forward_map[k]; } -
int search(const data_t &):reverse_map.find()是有效的。 -
delete(const data_t &)：搜索&删除reverse_map条目，返回int k。将k添加到forward_map的LIFO自由列表中。（不要触摸forward_map条目。如果您需要在没有forward_map条目后检测使用情况，请在此时将其归零。） -
insert(const data_t &)：检查空闲列表的头部是否有要重用的条目，否则为forward_map.push_back()。k=您将条目放在前向地图中的位置。将k添加到反向映射中
为了避免存储data_t项目的另一个副本，reverse_map需要在其搜索操作中引用forward_map。
由于缓存未命中，使用基于哈希表而不是搜索树的reverse_map有很大的潜在优势。通常，将键与树节点进行比较所需的所有数据都存在于节点中，但在这种情况下，它是对forward_map的引用。reverse_map本身的加载不仅可以缓存未命中，forward_map[k]也可以。（来自未知地址的加载无法尽早开始，这与乱序CPU上的已知地址情况不同，所以这非常糟糕）。推测性执行可能会启动reverse_map的下一个加载，但情况仍然很糟糕哈希表需要更少的总密钥比较，这是一大优势。
使用STL容器
在这里使用STL容器实际上存在一个"鸡和蛋"的问题：考虑一个std::unordered_set<int>:Key类型是int。我们将使用基于forward_map[i]的自定义KeyEqual函数进行比较。但只有.find(const Key& key)，没有.find(const data_t&)。
一个丑陋的解决方法是将data_t临时复制到forward_map中的空闲插槽中，这样它就会有一个索引，我们可以将其传递给unordered_set<int, custom_compare>::find，但这种额外的复制是愚蠢的。
另一个坏选项（可能不会在编译时进行优化）是一个具有访问data_t的虚拟函数的类。映射包含一个具有单个int成员的类。我们将传递一个派生类.find()，该派生类也有一个data_t &，并在Hash和KeyEquals函数使用的虚拟函数的重载中引用它，而不是int数组索引。
您可能需要构建自己的自定义数据结构，或者使用STL以外的其他方法，除非有一种方法可以让STL接受与现有集合成员不同类型的键。
您可以使用侵入式链表。例如：
struct Node {
Node *prev, *next;
variant<int, float, vector<string>> data;
};
现在，不需要存储int来定位其中一个，只需存储Node*即可。当你想删除一个：
~Node() {
if (prev) prev->next = next;
if (next) next->prev = prev;
}
现在，当您调用delete node时，它将从列表中消失。
不出所料，Boost有一个具有许多奇特功能的实现：http://www.boost.org/doc/libs/release/doc/html/intrusive.html