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

Question

I've faced one problem recently. I want to get the relative index of std::set element. For example, if std::set stores {1, 2, 4, 6, 9, 15}, and I want to find element {4} and get its relative index {2} efficiently. Of course, I can write std::distance(myset.begin(), myiterator), but the complexity of this operation is O(n*logn). If I had access to real red-black tree of std::set, I would just run rb_tree_node_pos(see below), which is O(logn).That is exactly the relative index. Does anyone know how can I get real tree? Here's code example:

#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 ;
}

In general I want data structure that will maintain following operations: 1. insert element, 2. delete element, 3.print out relative index of element. I think there is a way to 'dig' it from STL.

Welcome to Stack Overflow. Please take the time to read [The Tour](http://stackoverflow.com/tour) and refer to the material from the [Help Center](http://stackoverflow.com/help/asking) what and how you can ask here. — πάντα ῥεῖ, May 14 '17 at 19:32
@πάνταῥεῖ - Are you implying there's something wrong with this question? — Oliver Charlesworth, May 14 '17 at 19:39
@Oliver I just recommend the OP to read [The Tour]. And the question certainly can be improved with some concise sample code. — πάντα ῥεῖ, May 14 '17 at 19:39
But how will I insert something efficiently in sorted array? — Sergey Grigoryants, May 14 '17 at 19:56
Note that the red black tree is an implementation detail which means your std::set may not even be implemented as a red black tree. This question smells like an XY problem. What is the problem you are really trying to solve? — rubenvb, May 14 '17 at 19:59
A red-black tree can be implemented without maintaining the subtree size at every node, so the best you could do with a "real" rb-tree would be O(n). — rici, May 14 '17 at 19:59
The real problem: "I want data structure that will maintain following operations: 1. insert element, 2. delete element, 3.print out relative index of element".And I don't want to write it myself. — Sergey Grigoryants, May 14 '17 at 20:05
Are you fine with using non-standard extensions? The libstdc++ policy-based trees can be used to implement an order statistic tree: http://stackoverflow.com/a/11231596 — , May 14 '17 at 20:27
Your idea that the index of an element is equal to the size of the left subtree of the element + 1 is not correct. See the example https://en.wikipedia.org/wiki/File:Red-black_tree_example.svg, e.g. the index of element 17 is 7, whereas the size of the left subtree+1 is 2. — opetroch, May 14 '17 at 22:40
@Fanael This is really close to what I want, but I can't find the rank method in this tree.find_by_order method is inverse function to rank method, but I can't find rank method in tree,rb_tree_tag,tree_order_statistics_node_update>. — Sergey Grigoryants, May 15 '17 at 04:40

score 3 · Accepted Answer · edited May 23 '17 at 12:10

Thanks to @Fanael , who found the solution! We can implement this data structure using GNU Policy Based Data Structures(PBDS). Here's the code example:

#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;
}

You can learn more about GNU PBDS from here and here. Thanks to everyone who helped!

score 0 · Answer 2 · answered May 14 '17 at 20:03

If you use std::set, you can find the index of element with linear complexity:

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;
}

But if you use sorted array and binary search, the complexity will be 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;
}

But I can't insert element in sorted array efficiently. – Sergey Grigoryants May 14 '17 at 20:06 — Sergey Grigoryants, May 14 '17 at 20:06

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

2 Answers2