random map

Discussion in 'C++' started by Philipp Kraus, May 20, 2011.

  1. 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?
     
    Philipp Kraus, May 20, 2011
    #1
    1. Advertising

  2. Philipp Kraus

    Kai-Uwe Bux Guest

    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::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
     
    Kai-Uwe Bux, May 20, 2011
    #2
    1. Advertising

  3. Philipp Kraus

    Stefan Ram Guest

    Philipp Kraus <> writes:
    >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.
     
    Stefan Ram, May 20, 2011
    #3
  4. 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::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
     
    Philipp Kraus, May 20, 2011
    #4
  5. On 2011-05-20 20:17:31 +0200, Stefan Ram said:

    > advance


    Thanks the hint with std::adance works fine

    Thx

    Phil
     
    Philipp Kraus, May 20, 2011
    #5
  6. Philipp Kraus <> wrote:
    > 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?
     
    Juha Nieminen, May 20, 2011
    #6
  7. On 2011-05-20 22:33:04 +0200, Juha Nieminen said:

    > Philipp Kraus <> wrote:
    >> 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?


    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
     
    Philipp Kraus, May 21, 2011
    #7
  8. Philipp Kraus <> 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.
     
    Juha Nieminen, May 21, 2011
    #8
  9. On 2011-05-21 10:32:23 +0200, Juha Nieminen said:

    > Philipp Kraus <> 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
     
    Philipp Kraus, May 21, 2011
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Darren Clark

    Random NOt random?

    Darren Clark, Jun 24, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    459
    mikeb
    Jun 24, 2004
  2. Maziar Aflatoun

    Random not really random...

    Maziar Aflatoun, Aug 4, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    26,714
    Maziar Aflatoun
    Aug 5, 2004
  3. Lars-Erik Aabech
    Replies:
    8
    Views:
    845
    Lars-Erik Aabech
    Apr 28, 2005
  4. globalrev
    Replies:
    4
    Views:
    774
    Gabriel Genellina
    Apr 20, 2008
  5. VK
    Replies:
    15
    Views:
    1,180
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page