c++ - 任何可用的实现，如 Loki 的 AssocVector，但具有 Boost 的 Bimap 的功能？

Question

我想知道是否有人知道任何库代码具有 Loki 的 AssocVector 提供的性能特征(元素引用的局部性，与映射相比每个元素的内存开销更低)但具有 Boost 的 BiMap 功能(能够查询关系两侧的 map )？

或者使用 std::pairs 的排序 std::vector 并添加功能以使用对中的任一元素作为键来查找 vector 是前进的方向吗？

Answer 1

这实际上取决于您想快速完成的操作。 Loki::AssocVector 的插入和删除复杂度为 O(n)，而 boost::bimap 与 hash 一起使用时的复杂度为 O(1)表。如果您可以在数据结构的一个“ View ”上接受 O(n) 操作，在另一个“ View ”上接受 O(lg n) 操作，那么您提出的解决方案将工作正常并占用很少的内存。如果在一个 View 上的操作占主导地位，对于小型数据集可能会非常快。

您也可以考虑使用 Boost.Intrusive或带有专用分配器的 boost::bimap。