rr459595's blog

By rr459595, history, 5 months 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?

 
 
 
 

»
5 months 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.

  • »
    »
    5 months 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 ?

    • »
      »
      »
      5 months 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?

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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 ?