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

Question

我有一组数据需要存储在有序映射中（即通过键有效插入、删除和定位项目），但我还需要能够在不遍历整个地图的情况下找到第 n 个 元素（有时可能有数以万计的项目）。

我知道一种方法：使用红/黑树，但也要在每个节点的一条腿上保留子项的总数。它使插入和删除稍微慢了一点（因为您必须像这样做一样更新路径上每个节点上的计数），但是您可以在与查找键大致相同的时间内找到任何 n 的 第 n 个 元素。

我想知道是否有一个我可以使用的现有 C++ 实现。如果没有，我可以自己写，但我真的宁愿不写。

---

编辑：我对它的用例做了一些澄清。我误解了一点：在按键查找项目后，他们需要能够有效地找出找到的项目的索引，以正确显示滚动条。

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

原文由 Head Geek 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

关联/随机访问容器

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

---

找这样的数据结构很久了。

最近，我发现了一个很有前途的库，它具有您正在寻找的所有功能。

请参阅 O(log n) 中随机访问的 cntree::set。

链接在这里。 http://dl.dropbox.com/u/8437476/works/countertree/index.html

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

原文由 Sungmin 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您使用修改后的 Trie，其中非终端节点跟踪其下方有多少终端节点，您可以进行快速有序查找。

原文由 Null Set 发布，翻译遵循 CC BY-SA 2.5 许可协议