我最近遇到過一個問題。我想獲得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]。這個問題當然可以通過一些簡潔的示例代碼來改進。 –