rr459595's blog

TreeSet in Java.
By rr459595, history, 6 years 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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years 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.

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

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

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

        → Reply