获取大于数字的元素个数
我正在尝试解决以下问题:正在将数字插入容器中.每次插入一个数字时，我都需要知道容器中有多少元素大于或等于当前插入的数字.我相信这两种操作都可以在对数复杂度中完成.
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 可以在对数时间内插入元素，但是如何查询呢?还是我应该实现一个数据结构(例如二叉搜索树)来解决它?
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.
更好的是，看看:(C++ 中的排名树)
其中包含实现的链接:
(http://code.google.com/p/options/downloads/列表)
相关文章