std :: setの相対インデックスを取得するにはどうすればよいですか？

Question

最近私は1つの問題に直面しました。私はstd::set要素の相対的なインデックスを取得したい。たとえば、std::setが{1, 2, 4, 6, 9, 15}を格納していて、要素{4}を見つけて、相対インデックス{2}を効率的に取得したいとします。もちろん、私はstd::distance(myset.begin(), myiterator)と書くことができますが、この操作の複雑さはO(n*logn)です。私がstd::setの真の赤黒の木にアクセスできたら、O(logn)というちょうどrb_tree_node_pos（以下を参照）を実行します。これは正確に相対インデックスです。誰も私は本当の木を得ることができるか知っていますか？要素の相対的な指標を3.print、1インサート要素、2 delete要素：一般的に

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

は、私は次の操作を維持するデータ構造をしたい： は、ここではコードの例です。私はSTLからそれを「掘り起こす」方法があると思う。

Answer 1

解決策を見つけたのは@Fanaelです。このデータ構造は、GNU Policy Based Data Structures（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についての詳細を学ぶことができます。助けてくれた皆様に感謝します！

Answer 2

あなたがの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; 
}