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

Groups > comp.lang.c++ > #5213 > unrolled thread

random map

Back to article view | Back to comp.lang.c++

Contents

  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

#5213 — random map

Hello,

I habe a std::map and I would like to read k random key values. I have 
tried it with the iterator like:
randvalue between [0, std::mapsize-1]
(*(std::map::iterator.begin() + randvalue)).first

But this does not work, I'll get an error on stl_bvector.h with 
std::_Bit_iterator std::operator+. How can I get k random key values 
out of my map?

Thanks

Phil?

[toc] | [next] | [standalone]

#5214

Philipp Kraus wrote:

> Hello,
> 
> I habe a std::map and I would like to read k random key values. I have
> tried it with the iterator like:
> randvalue between [0, std::mapsize-1]
> (*(std::map::iterator.begin() + randvalue)).first
> 
> But this does not work, I'll get an error on stl_bvector.h with
> std::_Bit_iterator std::operator+. How can I get k random key values
> out of my map?

Quick question: Do you want to allow repetitions or do you want k distinct 
random keys?


Best,

Kai-Uwe Bux

[toc] | [prev] | [next] | [standalone]

#5216

On 2011-05-20 20:12:15 +0200, Kai-Uwe Bux said:

> Philipp Kraus wrote:
> 
>> Hello,
>> 
>> I habe a std::map and I would like to read k random key values. I have
>> tried it with the iterator like:
>> randvalue between [0, std::mapsize-1]
>> (*(std::map::iterator.begin() + randvalue)).first
>> 
>> But this does not work, I'll get an error on stl_bvector.h with
>> std::_Bit_iterator std::operator+. How can I get k random key values
>> out of my map?
> 
> Quick question: Do you want to allow repetitions or do you want k distinct
> random keys?

I can use repetitions, so I don't need a unique set

Phil

[toc] | [prev] | [next] | [standalone]

#5217

On 2011-05-20 20:17:31 +0200, Stefan Ram said:

> advance

Thanks the hint with std::adance works fine

Thx

Phil

[toc] | [prev] | [next] | [standalone]

#5218

Philipp Kraus <philipp.kraus@flashpixx.de> wrote:
> But this does not work, I'll get an error on stl_bvector.h with 
> std::_Bit_iterator std::operator+. How can I get k random key values 
> out of my map?

  Do you understand the concept of random access iterators and why
std::map iterators aren't?

[toc] | [prev] | [next] | [standalone]

#5227

On 2011-05-20 22:33:04 +0200, Juha Nieminen said:

> Philipp Kraus <philipp.kraus@flashpixx.de> wrote:
>> But this does not work, I'll get an error on stl_bvector.h with
>> std::_Bit_iterator std::operator+. How can I get k random key values
>> out of my map?
> 
>   Do you understand the concept of random access iterators and why
> std::map iterators aren't?

std::advance shoudl be do something like this
for(i=0; i < n; ++i)
     iterator++;

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.

Thx

Phil

[toc] | [prev] | [next] | [standalone]

#5249

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.)

  Anyways, the + operator of random access iterators have been defined
to perform the operation in constant time, so doing it for a map would
break that specification, which is why it's not supported.

[toc] | [prev] | [next] | [standalone]

#5255

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web