nerd's blog

set index
By nerd, 12 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

»
12 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

→ Reply
  • »
    »
    12 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?

    → Reply
    • »
      »
      »
      12 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<>

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

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

        → Reply
        • »
          »
          »
          »
          »
          12 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.

          → Reply
»
12 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

→ Reply
  • »
    »
    12 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.

    → Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

→ Reply
»
12 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.

→ Reply
»
9 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.me/blog/entry/11080

→ Reply
»
9 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)
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how can we make ordered_multiset ?

    → Reply
    • »
      »
      »
      9 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.

      → Reply
  • »
    »
    9 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.

    → Reply
  • »
    »
    9 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

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

    Thanks for this tip, this is totally awesome!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    find_by_order takes O(N) where N is size of ordered set

    → Reply
»
9 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.

→ Reply
  • »
    »
    9 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)).

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

      So if we take the lower_bound value from set is O(log n) while taking the position of it is O(n) complexity ?!

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

        Correct.

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

          Thanks for sharing new things ^^ I will keep mind this so that never get TLE for stupid reasoning ^^

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know of something similar in Java?

→ Reply