GreyMaster's blog

By GreyMaster, history, 9 years ago, In English

Hello.

I need a little help about set data structure. Is it possible that access the i-th element of a set with O(1) ?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

First of all, you cannot access an element of a std::set with less complexity than O(log(n)). And also you cannot access the i-th element of a set. But you can do this with a little trick.

  • »
    »
    9 years ago, # ^ |
    Rev. 12   Vote: I like it 0 Vote: I do not like it

    Thank you. But I know before that it is possible to accsess the i-th element with O(n) .So is there no work to acsess the i-th element with O(log n)?

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

      unfortunately no. I don't know why they didn't make this feature although it was easy to be done