STL MAP Allocator

>> Does anyone know how the STL map allocator works?
As jason said, there is no hard and fast way, it depends on the implimentationand which allocator you are talking about.   But the default allocator in the typical implimenation will just allocates arrays of the required length using the new operator and delete them with the delete opeator.  i.e.

pointer alloctor::allocate(size_type n,pointer *hint)
{
    return new value_type[n];
}

void allocator::deallocate(pointer *p,size_type n)
{
   delete [] p;
}


I would also add there is no speciall STL map allocator.  the STL map, uses an ordinary allocator, just like any other STL container class.

>> how much memory does it allocate when it is created?
Again, as jason said, no one knows.   but most probably allocate no memory when created.   Then allocate memory when it is requested.

>> how much does it allocate when it runs out of memory?
It it runs out of memory it can't allocate memory.  In that case it throws an exception.    It allocates memory when requested (when the allocate() function is called) until it can't allocate memory, then it throws an exceoption.


>> basically i'm looking for a map allocator that allocates rather
>> small amount of nodes on creation, and aech time it is required
>> to allocate more memory, it doubles the last amount of memory
>> that was allocated
That is not the allocator's responsibility.  The map will decide how many nodes it needs.    You could write your own special allocator that does this.   But imagine the problems you would face.   Lets sayt eh idea was to allocate the nodes in large arrays on some requests and then return pointers to those allocated and unsused enties on later requests.   The map will be allocating and freeing nodes in an apparently random order.   So you will find that some of your earlier used entries will become free again.  How will you manage to track which are used and which aren't?    The only efficient way to do this is to write your own heap code.    If you are going to do that, why not just use the standard heap?  i.e. why not just use new and delete.

By the way, in many implimenations, the containers reuse allocated memory rather then freeing it.   For example VC's STL map will save the nodes unused in a linked list so it doesn't have to free the nodes and allocate them again.  It allocates memory only when it runs out of nodes in the list.

thanks for your help guys, but i think i didn't give you all the info you need. i'm writing a W2K based application, that is, i will be using the microsoft implementation of the map and allocator. I know it uses a tree, and what i'm looking for is a way to control its allocations. if this means that i'll have to write my own heap, fine, isn't that what writing allocators is all about? it would be better if i had a working one though, or at least some examples.
do you know where can i find a code for such an allocator?

>> 'm looking for is a way to control its allocations.
Why?

The usual answer is that this is to improve either speed or memory use.   Both are the wrong reasons.

It is EXTREMELY unlikely that the allocator will be a bottleneck for your program.   If it isn't a bottleneck then improving its speed will not make any measurable difference in your program's speed.   So its very unlikely that you need to improve its speed.   Besides, the builtin heap functions a fairly well written.  You aren't likely to do significanly better (although you could do some thing they couldn't)

If you want to improve its memory use, you can just about forget it.   The map is still going to buffer its unused nodes just as before.   You don't have any chance for chaning this unless you rewrite map.

This is a guess,b ut your asking for doubling the size on each allocation seems to suggest you are hoping to do something like vector<> does to get amortized constant time efficiency on insertions into the container.   It won't work.  map's efficiency is not governed by the allocator, but instead by its internal structure.  i.e. the allocation is an approximately fixed-time cost, its the searches and reorganizations that must be done in the tree that governs its efficiency.

>>  if this means that i'll have to write my own heap, fine,
>> isn't that what writing allocators is all about? i
Not really.   The main reason is to control other aspects of allocation.    Like perhaps allighment, or the region in memory the data comes from (like in DOS the might be a near heap or far heap, on an embedded system there might be some memory that is set aside for long term allocations etc.)

Ok, i see where you getting at.
lets say that this map needs to know how to deal with millions of nodes. today, what we're using is some kind of a heap someone wrote ages ago. all the memory for this heap is allocated in one call to new, and its size is calculated according to the worse case scenario. however,
in most of the times the application doesn't need the whole amount of memory, but rather a small part of it. the nodes should be sorted by their keys, that's why map is good for us. now, the data flows in from a real time source, so we can't risk losing it due to the allocation time of a new bulk. all of that leads me to writing my own allocator, unless you wanna tell me otherwise...

>> so we can't risk losing it due to the allocation time of a new bulk
Do you have any evidenc that the allocation time is a bottleneck?   If not, then you aren't going to acomplish anything.  If you were an INCREADIBLY good programmer and magically made the allocation take no time at all, you probably wouldn't be able to measure any difference in the program speed.   Why?  Its the 80-20 rule.   There is very little--if any--benefit to optimizing a non-bottleneck.


The first thing to do is to see if this is a bottleneck, then if it is is--which is unlikely--then you can consider methods to improve it.   If its not a bottleneck, then no method to improve it is going to do much good for you.


If it really turns out this is a bottleneck, we can write an allocator that uses a vector for storing the data.   Basically it is a simplified heap that uses a vector for storing the data.  The allocator This is likely to be a liffle faster than using the general heap.  The main advantage to this method over the regular heap is that all items on this simplified heap are the same size, so there is no search to find an unused block of the right size i.e.  any unused block is the right size.  

But even though this is simplified, its still likely to be a few hours of programming.   Why spend that time if you don't need it.  Try it with the default allocator first.    Then if things aren't fast enough, then profile the code to find the bottlenecks.  (Note that even if the code with the default allocator is  not fast enough, there is a good chance that fixing the allocator won't make any difference, and instead there is something else you need to improve.)  

Dear udibs

I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. You can always request to keep this question open. But remember, experts can only help you if you provide feedback to their questions.
Unless there is objection or further activity,  I will suggest to split between

     "nietod and jasonclarke"

comment(s) as an answer.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner

Force accepted

** Mindphaser - Community Support Moderator **

nietod, there will be a separate question with points for your help.