获取大于数字的元素数 [英] Get number of elements greater than a number

问题描述

我试图解决以下问题：正在将数字插入到容器中。每次插入数字时，我需要知道容器中有多少个元素大于或等于要插入的当前数字。我相信两个操作都可以用对数复杂性来完成。

I am trying to solve the following problem: Numbers are being inserted into a container. Each time a number is inserted I need to know how many elements are in the container that are greater than or equal to the current number being inserted. I believe both operations can be done in logarithmic complexity.

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

My question: Are there standard containers in a C++ library that can solve the problem? I know that std::multiset can insert elements in logarithmic time, but how can you query it? Or should I implement a data structure (e.x. a binary search tree) to solve it?

推荐答案

我不认为有什么在STL可以满足您的需要（只要你必须有对数时间）。我认为最好的解决方案，因为aschepler在评论中说，是实现一个RB树。您可以查看STL源代码，特别是在 stl_tree.h ，看看是否可以使用它的位。

Great question. I do not think there is anything in STL which would suit your needs (provided you MUST have logarithmic times). I think the best solution then, as aschepler says in comments, is to implement a RB tree. You may have a look at STL source code, particularly on stl_tree.h to see whether you could use bits of it.

更进一步，请参阅：（排名树in C ++ ）

Better still, look at : (Rank Tree in C++)

其中包含实施链接：

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

这篇关于获取大于数字的元素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！