std :: map具有高效的第n个元素访问权限

Question

我有一组数据需要存储在有序映射中(即通过键有效插入,删除和定位项目),但我还需要能够找到第n个元素而无需遍历整个映射(有时可能会有成千上万的物品).

我知道一种方法:使用红色/黑色树,但也要保留每个节点的一条腿上的子项目总数.它使插入和删除速度稍慢(因为你必须像沿着路径更新路径上每个节点的计数),但是你可以在找到密钥的大致相同的时间内找到任何n的第n个元素.

我想知道是否存在我可以使用的这种东西的现有C++实现.如果没有,我可以自己写,但我真的不愿意.

编辑:我得到了一些关于用例的澄清.我稍微误解了一下:在按键查找项目后,他们需要能够有效地找出找到的项目是什么索引,以正确显示滚动条.

这是一个合理的需求,我上面描述的数据结构仍然适用于它,所以我仍然在寻找答案.但是,由于似乎还没有人提出一个,我将开始自己编码.

Answer 1

这是我考虑类似问题时对其他问题的回答。

我想这也可能适用于你的问题。

我一直在寻找这样的数据结构。

最近，我发现非常有前途的库，它具有您正在寻找的所有功能。

请参阅 cntree::set 的随机访问，时间复杂度为 O(log n)。

虽然它似乎正在开发中，但我认为它非常有用。