STL map

[Haro Panosyan]

Seems there is no reserve() function defined for STL map.
If so, could someone please explain why?
Same goes with resize().

Thanks,
-haro

 

[Victor Bazarov]

Seems there is no reserve() function defined for STL map.
If so, could someone please explain why?
Same goes with resize().

What would 'reserve' do? What would 'resize' do? As soon as you
answer those, I will help you prepare a proposal for a change in
the library specification.

V

 

[Jules]

Seems there is no reserve() function defined for STL map.

If so, could someone please explain why?
Same goes with resize().

These operations don't really make much sense for map objects, which
don't necessarily use a structure where reserving space in advance
makes sense (e.g. balanced trees).

 

[Haro Panosyan]

What would 'reserve' do? What would 'resize' do? As soon as you
answer those, I will help you prepare a proposal for a change in
the library specification.

I would assume same as with vector.
But since you are asking, then this should be
something not logical and this is what I don't understand,
hence my original question was someone to explain.

 

[Victor Bazarov]

I would assume same as with vector.

Why would you assume that? 'map' has nothing really in common with
'vector'.

But since you are asking, then this should be
something not logical and this is what I don't understand,
hence my original question was someone to explain.

Why do I have to ask before you start thinking that "this should be
something not logical"? Why don't you think that when you just look
at the interface of 'map'? If it's not there, it probably wasn't very
logical to have it there.

Now that we've come to the conclusion that the absence of 'reserve'
and 'resize' in 'map' is due to them being "not logical" for 'map',
we could try to find out *why* that is. I proposed to try to prove
the illogicality of them by starting from the opposite end: let's
_assume_ that they need to be there because that's logical (again,
we're just _assuming_ it is, for the proof's sake). If they should
be there, what would they do and how would they do it? You can take
'vector's members 'reserve' or 'resize' as the guideline (as _you_
so kindly proposed).

The 'resize' member of 'vector', for example, changes the size of
the collection by either trimming it from the end or by adding some
elements at the end. Trimming is simple. We could, I suppose, trim
a map just as well, since the order of elements in it is well-known
and determined by the keys. But let's look at adding some elements
to the end. 'vector' does that by default-constructing or copy-
constructing them. How would map do it? Default-constructing of
a stored value puts some value into "key" part, right? Now, if we
resize by adding 10 values, would all "keys" be the same? Yes, of
course, they are copy-constructed, don't they? But wait, 'map' has
only _one_ element with any particular "key", doesn't it? So, adding
10 elements of the same value would result in fact in adding _at_most_
1. One! Or none, if such element already exists in the map. So, it
seems that resizing by 10 elements wouldn't really work as anybody
might expect... Or would it?...

V

 

[James Aguilar]

I would assume same as with vector.
But since you are asking, then this should be
something not logical and this is what I don't understand,
hence my original question was someone to explain.

It's because vector is like this

(1)(2)(3)(4)(5)(6)

All in a row, right? But map actually looks something like this:

(1)
(3) (4)
(7) (2) (6) (5)

Where the digits are just the order in which you inserted the elements. As
you can see, the data is not contiguous and the ideal thing for reserve to
do is not the same in all cases.

If your goal is to acheive a minimum number of allocation calls, you can
provide an allocator to the template for map [1]. [2] talks about how to
write an allocator. You might want to consider writing one that just
allocates blocks of a certain size, where that size is the most that you
would use. Then you could get all of the allocation over with quickly.
Alternately, you could write one that allocates blocks of sizes that
correspond to powers of two, which often reduces problems related to memory
fragmentation.

Hope this helps.

JFA1

[1]
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfmap_class.asp
[2] http://www.codeproject.com/cpp/allocator.asp

 

[Haro Panosyan]

Why would you assume that? 'map' has nothing really in common with
'vector'.



Why do I have to ask before you start thinking that "this should be
something not logical"? Why don't you think that when you just look
at the interface of 'map'? If it's not there, it probably wasn't very
logical to have it there.

Now that we've come to the conclusion that the absence of 'reserve'
and 'resize' in 'map' is due to them being "not logical" for 'map',
we could try to find out *why* that is. I proposed to try to prove
the illogicality of them by starting from the opposite end: let's
_assume_ that they need to be there because that's logical (again,
we're just _assuming_ it is, for the proof's sake). If they should
be there, what would they do and how would they do it? You can take
'vector's members 'reserve' or 'resize' as the guideline (as _you_
so kindly proposed).

The 'resize' member of 'vector', for example, changes the size of
the collection by either trimming it from the end or by adding some
elements at the end. Trimming is simple. We could, I suppose, trim
a map just as well, since the order of elements in it is well-known
and determined by the keys. But let's look at adding some elements
to the end. 'vector' does that by default-constructing or copy-
constructing them. How would map do it? Default-constructing of
a stored value puts some value into "key" part, right? Now, if we
resize by adding 10 values, would all "keys" be the same? Yes, of
course, they are copy-constructed, don't they? But wait, 'map' has
only _one_ element with any particular "key", doesn't it? So, adding
10 elements of the same value would result in fact in adding _at_most_
1. One! Or none, if such element already exists in the map. So, it
seems that resizing by 10 elements wouldn't really work as anybody
might expect... Or would it?...

V

OK, I am getting clear on 'resize', but still have some doubts about
'reserve'. If I understand correctly, it can be implemented without
using copy-constructors, what is needed just the size of key-element
pair. But then James already talked about this. The question is, if
the above logic(my primitive) is correct, then can 'reserve' be
implemented as part of the standard.

 

[Andre Kostur]

OK, I am getting clear on 'resize', but still have some doubts about
'reserve'. If I understand correctly, it can be implemented without
using copy-constructors, what is needed just the size of key-element
pair. But then James already talked about this. The question is, if
the above logic(my primitive) is correct, then can 'reserve' be
implemented as part of the standard.

Where would it put these "unconstructed" memory blocks?

 

[Victor Bazarov]

[...]
OK, I am getting clear on 'resize', but still have some doubts about
'reserve'. If I understand correctly, it can be implemented without
using copy-constructors, what is needed just the size of key-element
pair. But then James already talked about this. The question is, if
the above logic(my primitive) is correct, then can 'reserve' be
implemented as part of the standard.

What does 'reserve' do? The main reason to use 'reserve' for a 'vector'
is to prevent _frequent_ reallocations of the _entire_storage_ and all
the subsequent _copying_ of values (and invalidation of iterators and
references). 'map' organises its storage totally differently. There is
no need to reserve anything because 'map' insertions do not cause any
reallocation of existing storage, any copying, or invalidation. So, our
'reserve' for 'map' would do essentially _nothing_. Yes, we could simply
implement it as

void reserve(size_type) {}

but why?

V