C++中的排名树

Question

我们需要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.

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

谢谢.

Answer 1

给定密钥K的等级是小于或等于K的密钥的数量.

例如,设s = {1,3,4,6,9}.然后秩(1)= 1,秩(4)= 3,秩(9)= 5.

STL函数distance()可用于计算出现在集合s中的元素x的等级.

rank = distance(s.begin(),s.find(x));

问题是它的时间复杂度是O(n).

请注意,建议的两个按键和按列索引的映射(或集合)不是正确的解决方案.问题是一个元素的变化会影响许多其他元素的排名.例如,向上面的集合s添加元素0会改变所有现有元素的等级:s'= {0,1,3,4,6,9}.rank(1)= 2,rank(4)= 4,rank(9)= 6.

谢谢.

Answer 2

我认为rank你实际上指的是距根的距离，因为如果它可以与值连续存储，那么你就不必达到这样的长度。

我认为你可以“外部”执行此操作，因为在这种情况下，可以根据使用比较谓词的次数推断出排名......

namespace detail
{
  template <class Comparator>
  class CounterComparator: Comparator
  {
  public:
    CounterComparator(size_t& counter):
        Comparator(), mCounter(&counter) {}
    CounterComparator(Comparator comp, size_t& counter):
        Comparator(comp), mCounter(&counter) {}

    template <class T, class U>
    bool operator()(T& lhs, U& rhs) const
    { 
      ++(*mCounter);
      return this->Comparator::operator()(lhs,rhs);
    }
  private:
    size_t* mCounter;
  };
} // namespace detail

template <
  class Key, 
  class Value, 
  class Cmp = std::less<Key>, 
  class Allocator = std::allocator< std::pair<const Key,Value> >
>
class SuperMap
{
  typedef detail::CounterComparator<Cmp> Comparator;
public:
  SuperMap(): mCounter(0), mData(Comparator(mCounter)) {}

  Value& operator[](const Key& key) { return mData[key]; }

  size_t rank(const Key& key) const
  { 
    mCounter = 0; mData.find(key); return mCounter;
  }

private:
  typedef std::map<Key,Value, Comparator, Allocator> data_type;

  mutable size_t mCounter;
  data_type mData;
}; // class SuperMap

int main(int argc, char* argv[])
{
  SuperMap<int,int> superMap;
  superMap[1] = 42;
  std::cout << superMap.rank(1) << std::endl;
}

// outputs
// 2

它计算测试的数量，但是因为std::map一旦获得正确的密钥就停止测试......应该没问题:)尽管可能有一些偏移量可以推断出（1或2）来获得排名。

如果你给出了更好的定义，rank我可能会做更多的工作，但我不想在错误的方向上花费太多时间。