CODEWITHSUNDEEP
c++memory-managementstlallocator
jorgander
jorgander

Reputation: 560

Is there an STL Allocator that will not implicitly free memory?

Memory usage in my STL containers is projected to be volatile - that is to say it will frequently shrink and grow. I'm thinking to account for this by specifying an allocator to the STL container type declarations. I understand that pool allocators are meant to handle this type of situation, but my concern is that the volatility will be more than the pool accounts for, and to overcome it I would have to do a lot of testing to determine good pool metrics.

My ideal allocator would never implicitly release memory, and in fact is perfectly acceptable if memory is only ever released upon destruction of the allocator. A member function to explicitly release unused memory would be nice, but not necessary. I know that what I'm referring to sounds like a per-object allocator and this violates the standard. I'd rather stick with the standard, but will abandon it if I can't resolve this within it.

I am less concerned with initial performance and more with average performance. Put another way, it matters less whether a single element or a pool of them is allocated at a time, and more whether said allocation results in a call to new/malloc. I have no problem writing my own allocator, but does anyone know of a preexisting one that accomplishes this? If it makes a difference, this will be for contiguous memory containers (e.g. vector, deque), although a generalized solution would be nice.

Upvotes: 3

Views: 570

Answers (1)

Ben L
Ben L

Reputation: 1321

I hope this isn't too basic.

Memory will be allocated and freed more for adding items than removing them.

I believe that never "freeing" memory isn't possible unless you know the maximum number of elements allowed by your application. The CRT might try to allocate a larger block of memory in place, but how would you handle the failure cases?

Explaination:

To create a dynamically expanding vector, there will be a larger capacity to handle most push_backs, and a reallocation to handle when this is insufficient.

  • During the reallocation, a new larger piece of memory is "newed" up and the elements of the old piece of memory are copied into the new one.

  • It is important that you don't hold any iterators while to push_back elements, because the reallocation will invalidate the memory
    locations the iterator point to.

  • In c++11 and TR1, you might have perfect forwarding where only the pointer to the elements need to be copied. This is done via a move constructor instead of a copy constructor.

However, you seem to want to avoid reallocation as much as possible.

Using the default allocator for vector you can specify an initial capacity.

  • Capacity is the memory allocated and size is the number of elements.

  • Memory will only be allocated at construction and if the size reaches capacity. This should only happen with a push_back();

  • The default allocator will increase the capacity by a multiple (eg. 1.5, 2.0) so that reallocation takes place in linear time. So if you have a loop that pushes back data it's linear. Or if you know the number of elements ahead of time you can allocate once.

There are pool concepts you can explore. The idea with a pool is you are not destroying elements but deactivating them.

If you still want to write your own allocator, this is a good article.

custom allocators

Upvotes: 1

Related Questions