map iterator

[John]

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

 

[Gianni Mariani]

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

 

[John]

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

 

[Andre Kostur]

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.

 

[Kai-Uwe Bux]

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

 

[Mark P]

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.

 

[Karl Heinz Buchegger]

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