random map

[Philipp Kraus]

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:perator+. How can I get k random key values
out of my map?

Thanks

Phil?

 

[Kai-Uwe Bux]

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:perator+. 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

 

[Stefan Ram]

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

Assuming

#include <map>
#include <iterator>
#include <iostream>
#include <ostream>

int main()
{ ::std::map< S, T >map;

, a random value can be possibly be printed with

if( map.size() > 0 )
{ ::std::map< S, T >::iterator item = map.begin();
::std::advance( item, rand( map.size() ));
::std::cout << item->second; }

, where »rand( n )« is a integral random number between 0
and n - 1.

 

[Philipp Kraus]

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:perator+. 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

 

[Philipp Kraus]

advance

Thanks the hint with std::adance works fine

Thx

Phil

 

[Juha Nieminen]

But this does not work, I'll get an error on stl_bvector.h with
std::_Bit_iterator std:perator+. 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?

 

[Philipp Kraus]

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

 

[Juha Nieminen]

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.

 

[Philipp Kraus]

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