rr459595's blog

By rr459595, history, 4 weeks ago, In English,

Is there any way to get index of an element in TreeSet?

I want a data structure(like set in c++) which can handle deletions in O(1) and do search(like lower_bound in c++) in O(logn) time.

Is there any inbuilt data structure in Java which supports the above operations?

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Lol. How do you even maintain an ordering of elements with O(1) deletion time? Unless you tell me that you are only deleting the largest/smallest element at any one time.

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

    C++ has std:set which is a sorted container and performs erase(int position) in O(1). I just asked if there is a equivalent data structure of Set in Java which supports those operations. What's there to laugh in that ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lol. Even if the erase is really O(1), you will still need to find the position of the item right? So that itself is already O(logn). How can the erase even be O(1) in that case?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why don't you post your actual problem (i.e. what you are trying to solve/do)? Then we will see what you really need.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      std::set erases by iterator in o(1), KeyIterator.remove also works in amortized constant.

      I do not know of standard library navigable set with quick access by index

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

        In C++, we have lower_bound for set which returns the "index" of required element in O(logn).In Java, we have TreeSet.ceiling method which does almost the same thing except for the fact that it returns the "element" itself and not the index. To find the index of that element, it will take O(n) time.

        Do you know any way to achieve this in java ?