我有一个 std::unordered_set 类型的元素 T 和一个函数 U key_of(const T& t)。现在，我想要一个 C++ 构造:
- 支持一些
std::unordered_map的方法；至少:operator[] const、find 和迭代器。 - 不会产生实际构建 map 的存储空间(即使使用 T*s 也不会)
- 由集合支持，即集合中的每个元素 e 都有一个映射条目，有一个映射条目 (key_of(e),e)。
使用(现代)C++ 执行此操作的惯用方法(如果有的话)是什么？
注意事项: - map 外观不会用于插入、删除或更改任何数据。 - 关于有序 map 和有序集的答案也很相关，尽管不那么重要。 - 可能缺乏性能，如果我想要快速的东西，我只会构建 map 。简单性更重要。 - 在 map 外观可能假设它永远不会改变的意义上，集合是不变的。 - 您可以假设集合中没有冗余(即没有具有相同键的元素)或建议多映射解决方案。
最佳答案
给定 std::unordered_set<T> 的概念，我们构建一个 std::unordered_map<K, V>这样 K = key_of(const T& t) , V = T对 key_of 施加了巨大的限制.
-
key_of是双射的。内射性，即for any x, y E T : key_of(x) == key_of(y) -> x == y是满足 map 的关键唯一性所必需的。 可能还需要满射，否则您的 map 不能包含未使用 key_of 计算的元素 z。您没有指定该结构将如何构建，所以让我们放弃它。 -
key_of应该保留Hash_v(T x)的碰撞概率.这没什么大不了的，因为如果是双射的，你可以构建Hash_u(U k)使得碰撞的概率完全相同。
一旦满足这些标准，就与构建一个 std::unordered_map<K, V> 没有什么不同了。使用 std::unordered_set<std::pair<K, V>> .考虑到both requires，哪个顺便说一句是完全可能的Container , AllocatorAwareContainer , UnorderedAssociativeContainer .
注意:相等是KeyEqual_u = std::equal_to<U>, KeyEqual_v = std::equal_to<V>
关于c++ - std::unordered_set 的 std::unordered_map facade - 怎么样？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34175762/