获取大于数字的元素数量

Question

我试图解决以下问题:正在将数字插入容器中.每次插入一个数字时,我都需要知道容器中有多少元素大于或等于当前插入的数字.我相信这两个操作都可以以对数复杂度完成.

我的问题: C++库中是否有可以解决问题的标准容器？我知道std::multiset可以在对数时间插入元素,但是如何查询呢？或者我应该实现一个数据结构(从二叉搜索树)来解决它？

Answer 1

很好的问题。我认为 STL 中没有任何东西可以满足您的需求（前提是您必须有对数时间）。我认为最好的解决方案，正如 aschepler 在评论中所说，是实现 RB 树。您可以查看 STL 源代码，特别是stl_tree.h看看是否可以使用其中的某些部分。

更好的是，看看：（C++ 中的排名树）

其中包含实现链接：

（http://code.google.com/p/options/downloads/list）