Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #5255

Re: random map

Show all headers | View raw

On 2011-05-21 10:32:23 +0200, Juha Nieminen said:

> Philipp Kraus <philipp.kraus@flashpixx.de> wrote:
>> In this case I can read / write any element in my map (bidirectional).
>> I need a random access iterator, because I will nagivation to each
>> element within the map in the worst-case in any order. But why can't I
>> use iterator+n, because the map is sorted by the keys, so there is an
>> order of the elements with transitivity dependency. ++ increses the
>> iterator position element by element, but +n jump to the element
>> directly.
> 
>   You can't jump in a binary tree directly from one node to another.
> You need to traverse the tree to get to the node you want. The very
> fastest you could do this is in O(log n) time (instead of O(1) time,
> which is what random access would allow).
> 
>   With some additional data in the tree it could perhaps be possible
> to implement a "give me the nth node" in O(log n) time. (I'm not sure
> this could be done without any additional data, only relying on the
> shape of the tree after it has been balanced.)

Okay, thanks. I know the searching algorithm in a binary tree, but I 
thought that I can directly process the the nth node. I had thought 
that the tree has implementated connection between the leaves, so that 
was my mistake

Phil

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

random map Philipp Kraus <philipp.kraus@flashpixx.de> - 2011-05-20 19:59 +0200
  Re: random map Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-20 20:12 +0200
    Re: random map Philipp Kraus <philipp.kraus@flashpixx.de> - 2011-05-20 20:18 +0200
  Re: random map Philipp Kraus <philipp.kraus@flashpixx.de> - 2011-05-20 20:36 +0200
  Re: random map Juha Nieminen <nospam@thanks.invalid> - 2011-05-20 20:33 +0000
    Re: random map Philipp Kraus <philipp.kraus@flashpixx.de> - 2011-05-21 08:11 +0200
      Re: random map Juha Nieminen <nospam@thanks.invalid> - 2011-05-21 08:32 +0000
        Re: random map Philipp Kraus <philipp.kraus@flashpixx.de> - 2011-05-21 13:20 +0200

csiph-web