random map

P

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

Thanks

Phil?
 
K

Kai-Uwe Bux

Philipp said:
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::eek: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
 
S

Stefan Ram

Philipp Kraus said:
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.
 
P

Philipp Kraus

Philipp said:
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::eek: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
 
J

Juha Nieminen

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

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
 
J

Juha Nieminen

Philipp Kraus said:
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.
 
P

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top