map iterator

Discussion in 'C++' started by John, May 19, 2005.

  1. John

    John Guest

    I want to store an array of pointers (void *) to
    iterators inside a map. The idea is to reach the
    map <key,info> pair faster if the data is in the
    array. If not use a O(log) search.

    But stl wont let me typecast a map iterator to a void *
    and store it in an array. Can this be done. I was looking
    at the code of stl_tree and it seems that the "value" =
    key,info pair is stored in a node and never moved unless
    deleted. So if map points using an iterator to this value,
    and I could store this iterator as a void * in an array,
    I could do what I wanted.

    The problem is that this array needs to have pointers
    to many different maps and hence I want it to be void *.

    Any ideas on how this could be done?

    Thanks,
    --j
     
    John, May 19, 2005
    #1
    1. Advertising

  2. John wrote:
    ....
    >
    > The problem is that this array needs to have pointers
    > to many different maps and hence I want it to be void *.
    >
    > Any ideas on how this could be done?



    You may be able to use an "Any" object.


    Check out boost::any
     
    Gianni Mariani, May 19, 2005
    #2
    1. Advertising

  3. John

    John Guest

    Thanks. Isnt there a simpler way? :(

    Another question. If we do insertions in the map, does the iterator
    that
    points to an inserted element before get invalidated?

    Thanks,
    --j
     
    John, May 19, 2005
    #3
  4. John

    Andre Kostur Guest

    "John" <> wrote in news:1116475995.140153.92740
    @g14g2000cwa.googlegroups.com:

    > I want to store an array of pointers (void *) to
    > iterators inside a map. The idea is to reach the
    > map <key,info> pair faster if the data is in the
    > array. If not use a O(log) search.
    >
    > But stl wont let me typecast a map iterator to a void *
    > and store it in an array. Can this be done. I was looking
    > at the code of stl_tree and it seems that the "value" =
    > key,info pair is stored in a node and never moved unless
    > deleted. So if map points using an iterator to this value,
    > and I could store this iterator as a void * in an array,
    > I could do what I wanted.
    >
    > The problem is that this array needs to have pointers
    > to many different maps and hence I want it to be void *.
    >
    > Any ideas on how this could be done?


    I'm not sure I have any idea what you're trying to accomplish! I don't
    understand how this array relates to anything. Seems to be some sort of
    attempt to do a fast index into the map, but I'm not sure how. Do you have
    any short example of what you're trying to accomplish?

    One thing to note. An iterator is _not_ a pointer, so casting it to one is
    futile.
     
    Andre Kostur, May 19, 2005
    #4
  5. John

    Kai-Uwe Bux Guest

    John wrote:

    > I want to store an array of pointers (void *) to
    > iterators inside a map. The idea is to reach the
    > map <key,info> pair faster if the data is in the
    > array. If not use a O(log) search.


    There is no guarantee at all that iterators for std::map are pointers to
    ndes. In fact, a plausible implementation of std::map could use a binary
    tree without backlinking to parent nodes. Iterators could be implemented as
    single linked lists of nodes representing a whole path ending at the root.
    In this case, you would really be out of luck.

    Anyway, casting iterators to void* is almost certainly invoking undefined
    behavior.

    > But stl wont let me typecast a map iterator to a void *
    > and store it in an array. Can this be done.


    Sure, using reinterpret_cast you can cast almost without any restrictions.
    It will, however, not have the effects that you want.

    > I was looking
    > at the code of stl_tree and it seems that the "value" =
    > key,info pair is stored in a node and never moved unless
    > deleted. So if map points using an iterator to this value,
    > and I could store this iterator as a void * in an array,
    > I could do what I wanted.


    The standard does not specify the implementation. It does not pay to look
    at it (except, of course, to learn how it's done). In particular,
    implementations are allowed to move stuff around. This might even happen
    without you seeing it directly in the code for std::map<>. For instance, an
    implementation could allow the use of garbage collecting allocators whose
    pointer-types are not raw-pointers. In this case, the pointer might move
    the pointee behind your back.

    > The problem is that this array needs to have pointers
    > to many different maps and hence I want it to be void *.


    Do you mean different objects of the same type std::map< key, value >,
    or do you mean maps of different types: std::map< key_1, value_1 >,
    std::map< key_2, value_2 >, etc. If you mean the former, you can just use
    an array of std::map< key, value >::const_iterator. If you mean the latter,
    I would not see how you could make reasonable use of that array anyway: all
    type-information is discarded and how are you going to use the key-value
    pair without knowing its type?


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, May 19, 2005
    #5
  6. John

    Mark P Guest

    John wrote:
    > Thanks. Isnt there a simpler way? :(
    >
    > Another question. If we do insertions in the map, does the iterator
    > that
    > points to an inserted element before get invalidated?
    >
    > Thanks,
    > --j
    >


    If you mean an iterator that points to a previously inserted element
    then, no, an insert into the map does not invalidate that iterator.
     
    Mark P, May 19, 2005
    #6
  7. John wrote:
    >
    > I want to store an array of pointers (void *) to
    > iterators inside a map. The idea is to reach the
    > map <key,info> pair faster if the data is in the
    > array. If not use a O(log) search.


    I am not sure I understand your idea. But just one
    quick question:

    How do you figure out if the requested iterator
    is in the array?

    I am asking because O(log) is pretty good for
    searching an item and hard to beat. If it is not
    good enough, switch to hashing and a hashmap (which
    is currently non-standard, but there are implementations
    around).

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, May 19, 2005
    #7
    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. Hendrik Maryns
    Replies:
    18
    Views:
    1,447
  2. greg
    Replies:
    6
    Views:
    468
    Dietmar Kuehl
    Jul 17, 2003
  3. wolverine
    Replies:
    3
    Views:
    1,091
    Chris
    Jul 31, 2006
  4. Vikram Karandikar
    Replies:
    1
    Views:
    213
    Vikram Karandikar
    Oct 25, 2013
  5. Jim Anderson

    problem with iterator (map iterator)

    Jim Anderson, Jan 10, 2014, in forum: C++
    Replies:
    3
    Views:
    146
    Luca Risolia
    Jan 13, 2014
Loading...

Share This Page