如何獲得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中「挖掘」它。

來源

2017-05-14 Сергей Григорянц

歡迎來到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。感謝所有幫助過的人！

來源

2017-05-15 12:44:30

如果您使用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; 
}

來源

2017-05-14 20:03:10 Lassie

但我無法有效地在排序的數組中插入元素。 –

如何獲得std :: set的相對索引？

回答

相關問題