我有一组数据需要存储在有序映射中(即通过键有效插入,删除和定位项目),但我还需要能够找到第n个元素而无需遍历整个映射(有时可能会有成千上万的物品).
我知道一种方法:使用红色/黑色树,但也要保留每个节点的一条腿上的子项目总数.它使插入和删除速度稍慢(因为你必须像沿着路径更新路径上每个节点的计数),但是你可以在找到密钥的大致相同的时间内找到任何n的第n个元素.
我想知道是否存在我可以使用的这种东西的现有C++实现.如果没有,我可以自己写,但我真的不愿意.
编辑:我得到了一些关于用例的澄清.我稍微误解了一下:在按键查找项目后,他们需要能够有效地找出找到的项目是什么索引,以正确显示滚动条.
这是一个合理的需求,我上面描述的数据结构仍然适用于它,所以我仍然在寻找答案.但是,由于似乎还没有人提出一个,我将开始自己编码.
我试图解决以下问题:正在将数字插入容器中.每次插入一个数字时,我都需要知道容器中有多少元素大于或等于当前插入的数字.我相信这两个操作都可以以对数复杂度完成.
我的问题:
C++库中是否有可以解决问题的标准容器？我知道std::multiset可以在对数时间插入元素,但是如何查询呢？或者我应该实现一个数据结构(从二叉搜索树)来解决它？
我正在寻找可以提供以下功能的 stl/boost 容器：
如果没有，那么实现这一目标的最佳方法是什么？我正在考虑使用双向链接列表的解决方案。那会是解决这个问题的好选择吗？