nerd's blog

By nerd, 6 years ago, In English,

Dear All,

How to access to i*th element of a set in c++ effectively (*O(1) or (logN))?

Thanks

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no documented way to do this. But set is a RB-tree, so you probably can get access to tree's structure and get i-th element in by yourself. I don't think it's a good way

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    But how to fetch i-th element from RB-tree itself in O(logN) without precalculation?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I don't know, that's true. Well, it looks like one does not simply access k-th element of set<>

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What means kth element in Set if the set is unordered?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Surely only ordered sets (for example TreeSet in java) are considered. It looks like set in c++ is implemented in the same way and is ordered therefore.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The trouble is that none of the tree-like data structures available in the standard libraries support a fast k-th element query ("given k, find the k-th smallest of the stored numbers").

The thing you have to add to a canonical balanced tree structure is information about subtree sizes: for each node in the tree, keep the count of elements in the subtree rooted at this node. For a particularly easy-to-implement balanced tree structures, check out splay trees and treaps.

(c) http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm310

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You forgot to mention the decreased efficiency of insert/remove for tree with info on branch sizes (up to O(n), I think). You see, it is just a way of precalculation.

    More obvious precalculation is, surely, to dump the set into an array and then to make as many queries as necessary.

    UPD: I think I am wrong and efficiency of inserting/removing may remain O(logN), sorry.

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

»
6 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

There is a cheat to access Parent, Left and Right nodes. But i have no idea how to use this information "online". There is problems because of tree modifications — rotations and other balancing stuff while inserting or erasing nodes.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! Looks like there's a way to do it after all. Please see http://codeforces.com/blog/entry/11080

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use C++ SGI STL tree.

For example:


#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //required #include <ext/pb_ds/tree_policy.hpp> //required using namespace __gnu_pbds; //required using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ordered_set <int> s; /* or: typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ordered_set s; This works in C++98 but the above version only works in C++11 */ int main(){ // It has C++ `set` functions: for(auto i: {1,3,5,8}) s.insert(i); s.erase(8); s.erase(s.find(8)); cout << * s.begin() << endl; if(s.begin() == s.end() or s.empty()) cout << "empty" << endl; s.lower_bound(3); s.upper_bound(1); cout << s.size() << endl; // special `tree` functions: cout << s.order_of_key(3) << endl; // the number of elements in s less than 3 (in this case, 0-based index of element 3) cout << *s.find_by_order(1) << endl; // 1-st elemt in s (in sorted order, 0-based) }
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how can we make ordered_multiset ?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use pair<T, size_t> as element and give each element an unique id.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    #include <ext/pb_ds/tree_policy.hpp> //required
    

    False. assoc_container.hpp is enough.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found something pretty crazy while using this data structure for the first time.

    I tried to test it a bit before using it in my real problem, and I was surprised to see that it was incredibly slow.

    It compiled but, still, it took around 50s just to do

    for(int i = 0; i < 500; i++)
        s.insert(i);
    

    So I gave up and I used a segment tree instead, but in fact the segment tree wasn't perfect for the problem and I ended with only 42 / 140 on this problem (today's COCI#2, problem 5)

    Now, I tried to see what went wrong and I found the culprit : -D_GLIBCXX_DEBUG Without that option, I can insert 106 elements in 0.6s, and that's honest for .

    Morality: never trust your complier options :D

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for this tip, this is totally awesome!

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How about binary search? You have lower_bound() for set. Please correct me if I am wrong. The complexity is log(n)*log(L) though. L= range of values in set,n=no. of values in set.

int idx=(int)(S.lower_bound(start,end,value)-S.begin()) if idx>k , search again.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    The problem here is operator - — it works in linear time. Iterators used by set are bidirectional only, not random access. It means that you can relatively fast increase/decrease them, but you cannot make bigger jumps or subtract them fast than in a linear time (more precisely, in O(answer)).