如何获得 std::set 的相对索引？

Question

我最近遇到了一个问题。我想获得 std::set 元素的相对索引。例如，如果 std::set 存储 {1, 2, 4, 6, 9, 15}，我想高效地查找元素 {4} 并获取其相对索引 {2}。当然我可以写std::distance(myset.begin(), myiterator)，但是这个操作的复杂度是O(n*logn)。如果我能访问真正的std::set红黑树，我会运行 rb_tree_node_pos（见下文），也就是O(logn)。这就是相对索引。有谁知道我怎样才能得到真正的树？这是代码示例：

#include <iostream>
#include <set>
using namespace std ;
int rb_tree_node_pos(rb_tree_node *node) {
  //function that finds relative index of tree node
  if (node->parent==NULL) return rb_tree_size(node->left) ;
  else return rb_tree_node_pos(node->parent)+rb_tree_size(node->left)+1 ;_
}
int main () {
  set<int> myset ;
  //... reading some data in myset
  int find_int ;
  cin >> find_int ;
  set<int>::iterator myit=myset.find(find_int) ;
  int find_index=distance(myset.begin(), myit) ; // O(n*log(n)), to slow!!!
  find_index=rb_tree_node_pos(myit->get_rb_tree()) ; // that's O(logn)
  cout << find_index << endl ;
  return 0 ;
}

一般来说，我想要的数据结构将维护以下操作：1. 插入元素，2. 删除元素，3.print 输出元素的相对索引。我认为有一种方法可以从 STL 'dig' 它。

Answer 1

如果使用std::set，可以找到线性复杂度的元素索引：

int Search (const std::set<int>& a, int value)
{
    int c=0;
    for(auto&& i: a)
    {
        if(i==value) return c;
        ++c;
    }
    return -1;
}

int main()
{
    std::set <int> a{1, 2, 4, 6, 9, 15};
    std::cout << Search(a,4) << std::endl;
}

但是如果使用排序数组和二分查找，复杂度将是O(log(n))。

int Binary_search (const std::vector<int>& a, int value)
{
    int l=0;
    int r=a.size()-1;
    while(l<=r)
    {
        int m=(l+r+1)/2;
        if(a[m]==value) return m;
        else if(a[m]>value) r=m-1;
        else l=m+1;
    }
    return -1;
}

int main()
{
    std::vector <int> a{1, 2, 4, 6, 9, 15};
    std::cout << Binary_search(a,4) << std::endl;
}

Answer 2

感谢 @Fanael ，谁找到了解决方案！我们可以使用 GNU Policy Based Data Structures (PBDS) 来实现这个数据结构。这是代码示例：

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;

int main()
{
  ordered_set myset;
  //....reading some data to myset
  int find_int ;
  cin >> find_int ;
  find_index=myset.order_of_key(find_int) ;
  cout << find_index << endl ;
  return 0;
}

您可以从 here and here 了解更多关于 GNU PBDS 的信息。感谢所有帮助过的人！

如何获得 std::set 的相对索引？

How can I get relative index of std::set?

c++

binary-tree

stl

set

red-black-tree