我最近遇到过一个问题。我想获得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]。这个问题当然可以通过一些简洁的示例代码来改进。 –