我想知道是否有人知道任何库代码具有 Loki 的 AssocVector 提供的性能特征(元素引用的局部性,与映射相比每个元素的内存开销更低)但具有 Boost 的 BiMap 功能(能够查询关系两侧的 map )?
或者使用 std::pairs 的排序 std::vector 并添加功能以使用对中的任一元素作为键来查找 vector 是前进的方向吗?
最佳答案
这实际上取决于您想快速完成的操作。 Loki::AssocVector
的插入和删除复杂度为 O(n),而 boost::bimap
与 hash 一起使用时的复杂度为 O(1)表。如果您可以在数据结构的一个“ View ”上接受 O(n) 操作,在另一个“ View ”上接受 O(lg n) 操作,那么您提出的解决方案将工作正常并占用很少的内存。如果在一个 View 上的操作占主导地位,对于小型数据集可能会非常快。
您也可以考虑使用 Boost.Intrusive或带有专用分配器的 boost::bimap
。
关于c++ - 任何可用的实现,如 Loki 的 AssocVector,但具有 Boost 的 Bimap 的功能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4189770/