11

我们需要具有搜索和排名功能的 ADT。即除了STL map的接口外，还需要一个函数'int get_rank(key)'。

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

我们正在寻找一种基于标准容器（STL，Boost）的解决方案，具有最佳的时间复杂度：查找/添加/擦除元素需要 O(log n) （如在 STL 映射/集合中），通过 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。

在我们看来，在上述时间复杂度约束下，不能通过两个映射的组合来解决问题，一个按 key 排序，另一个按 rank 排序。

谢谢。

4

4 回答 4

5

给定键 K 的秩是小于或等于 K 的键的数量。

例如，设 s = {1, 3, 4, 6, 9}。然后排名（1）= 1，排名（4）= 3，排名（9）= 5。

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

rank = 距离（s.begin(), s.find(x));

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

请注意，提出的按键和按等级索引的两个地图（或集合）不是正确的解决方案。问题是一个元素的变化会影响许多其他元素的等级。例如，将元素 0 添加到上面的集合 s 会改变所有现有元素的等级：s' = {0, 1, 3, 4, 6, 9}。排名（1）= 2，排名（4）= 4，排名（9）= 6。

谢谢。

于 2010-02-18T22:44:09.633 回答
2

我已经实现了一个“排名红黑树”，它类似于红黑树，除了每个节点通过有序遍历存储与它之前的节点的距离，而不是存储一个键。

这正是您想要的，除了第一个节点的“等级”是 0 而不是 1（如果需要，您可以添加/减去 1）。

我的解决方案是 PUBLIC DOMAIN，它基于常规红黑树的公共域教程。所有操作——包括插入、删除、查找和确定等级，都具有相对于数据结构中元素数量的对数时间。

你可以在这里找到它： http ://code.google.com/p/options/downloads/list

您应该从上面的链接获得最新版本，目前（在撰写本文时）rrb_v4_release.cpp。

于 2010-12-28T04:39:35.953 回答
1

您可以使用其他一些地图，例如容器。
保留一个大小字段可以使二叉搜索树易于随机访问。
这是我的实现...
标准样式，随机访问迭代器...
大小平衡树...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
和 B+tree ...
https： //github.com/mm304321141/zzz_lib/blob/master/bpptree.h

于 2015-10-21T03:13:37.160 回答
0

我想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我可能会工作更多，但我不想在错误的方向上花费太多时间。

于 2010-02-18T17:55:52.707 回答