### nerd's blog

By nerd, 6 years ago, ,

Dear All,

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

Thanks

•
• +1
•

 » 6 years ago, # |   0 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 →   0 But how to fetch i-th element from RB-tree itself in O(logN) without precalculation?
•  » » » 6 years ago, # ^ |   +8 I don't know, that's true. Well, it looks like one does not simply access k-th element of set<>
•  » » » » 6 years ago, # ^ |   0 What means kth element in Set if the set is unordered?
•  » » » » » 6 years ago, # ^ |   0 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, # |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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, # |   +14
 » 6 years ago, # | ← Rev. 5 →   +3 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.
•  » » 6 years ago, # ^ |   0 Some discussion about maintaining subtree sizes: http://online-judge.uva.es/board/viewtopic.php?p=42339&sid=06bcbb8c183b8bea4de63a3fa44fb3f2#p42339
 » 3 years ago, # |   0 Hey! Looks like there's a way to do it after all. Please see http://codeforces.com/blog/entry/11080
•  » » 3 years ago, # ^ |   0 No there isn't!. That is another implementation!
 » 3 years ago, # |   0 You can use C++ SGI STL tree.For example: #include #include //required #include //required using namespace __gnu_pbds; //required using namespace std; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; ordered_set s; /* or: typedef tree, 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, # ^ |   0 how can we make ordered_multiset ?
•  » » » 3 years ago, # ^ |   0 Use pair as element and give each element an unique id.
•  » » 3 years ago, # ^ |   -10 #include //required False. assoc_container.hpp is enough.
•  » » 3 years ago, # ^ |   0 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
•  » » 6 months ago, # ^ |   0 Thanks for this tip, this is totally awesome!
 » 3 years ago, # | ← Rev. 2 →   0 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, # ^ |   +19 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)).