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

问题描述：

我最近遇到过一个问题。我想获得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)。这正是相对指数。有谁知道我怎么能得到真正的树？这里的代码示例：如何获得std :: set的相对索引？

#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 delete元素，走出3.打印元素的相对指标。我认为有一种方法可以从STL中“挖掘”它。

欢迎来到Stack Overflow。请花些时间阅读[The Tour]（http://stackoverflow.com/tour），并参阅[帮助中心]（http://stackoverflow.com/help/asking）中的资料，了解您可以在这里问。 –

@πάνταῥεῖ - 你是否暗示这个问题有什么问题？ –

@Oliver我只是推荐OP阅读[The Tour]。这个问题当然可以通过一些简洁的示例代码来改进。 –

答

感谢@Fanael，谁找到了解决方案！我们可以使用基于GNU策略的数据结构（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和here更多关于GNU PBDS。感谢所有帮助过的人！

答

如果您使用std ::集，你可以找到元素与线性复杂度指数：

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（日志（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; 
}

但我无法有效地在排序的数组中插入元素。 –

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

相关推荐