相关疑难解决方法(0)

我们需要ADT具有搜索和排名功能.也就是说,除了STL map的接口外,还需要一个函数'int get_rank(key)'.

这种功能的标准实现需要在自平衡搜索树的每个节点中支持和更新额外的整数字段(例如,在黑红树中,在STL映射/集合中使用).但似乎,STL map/set不这样做.

我们正在寻找一种基于标准容器(STL,Boost)的解决方案,它具有最佳的时间复杂度:查找/添加/删除元素需要O(log n)(如在STL map/set中),通过a计算排名key也需要O(log n).

通过元素的等级,我们指的是元素在地图/集合的所有元素的排序序列中的位置.

例.set = {0,4,6,7,8} rank(0)= 1,rank(4)= 2,rank(6)= 3,rank(7)= 4,rank(8)= 5.

在我们看来,在上述时间复杂性约束下,问题不能通过两个映射的组合来解决,一个按键排序,另一个按排序排序.

谢谢.

我有一个multiset,实现如下:

#include <bits/stdc++.h>
using namespace std;

multiset <int> M;

int numunder(int k){
    /*this function must return the number of elements smaller than or equal to k
    in M (taking multiplicity into account).
    */
}

起初我以为我可以返回M.upper_bound(k)-M.begin()+ 1.不幸的是,我们似乎无法减去这样的指针.我们最终必须实现AVLNodes结构.有没有办法让这个工作利用c ++ std？