-
Bug
-
Resolution: Unresolved
-
P4
-
None
-
None
-
generic
-
generic
A DESCRIPTION OF THE PROBLEM :
I just found that C++ or to be more apt G++ has policy based data structures. Its ordered set Data Structure has two function , find_by_order and order_of_key. These functions help to get address of (x+1) th element or to compute the number of elements smaller than a given key in O(logN) time . I guess Java Collections Framework has no such function. If I use TreeSet's headSet(key).size(). It takes O(N) time and for N queries it becomes N^2.
Now I can use a TreeMap to map element with index as its value but if I have to remove some element then I need to change the indices/values of all entries of TreeMap which will again bring complexity to O(n^2).
Also using custom built segment tree to perform queries is also a solution but I think if C++ users can have that functionality then why not Java users? It will increase the use of this language in the realm of Competitive Programming.
Use cases:
There are many problems which can be solved easily using this. One simple example is that if I have a n elements in TreeSet . I want to know the number of elements which are strictly less than an element in O(logn) time and then remove that element from TreeSet for some computational reason. If I perform n such queries it can be done in O(nlogn) rather than current O(n^2)
I just found that C++ or to be more apt G++ has policy based data structures. Its ordered set Data Structure has two function , find_by_order and order_of_key. These functions help to get address of (x+1) th element or to compute the number of elements smaller than a given key in O(logN) time . I guess Java Collections Framework has no such function. If I use TreeSet's headSet(key).size(). It takes O(N) time and for N queries it becomes N^2.
Now I can use a TreeMap to map element with index as its value but if I have to remove some element then I need to change the indices/values of all entries of TreeMap which will again bring complexity to O(n^2).
Also using custom built segment tree to perform queries is also a solution but I think if C++ users can have that functionality then why not Java users? It will increase the use of this language in the realm of Competitive Programming.
Use cases:
There are many problems which can be solved easily using this. One simple example is that if I have a n elements in TreeSet . I want to know the number of elements which are strictly less than an element in O(logn) time and then remove that element from TreeSet for some computational reason. If I perform n such queries it can be done in O(nlogn) rather than current O(n^2)