Preventing memory freeing in STL Container

Question

I have an STL container (std::list) that I am constantly reusing. By this I mean I

1. push a number of elements into the container
2. remove the elements during processing
3. clear the container
4. rinse and repeat a large number of times

When profiling using callgrind I am seeing a large number of calls to new (malloc) and delete (free) which can be quite expensive. I am therefore looking for some way to preferably preallocate a reasonably large number of elements. I would also like my allocation pool to continue to increase until a high water mark is reach and for the allocation pool to continue to hang onto the memory until the container itself is deleted.

Unfortunately the standard allocator continually resizes the memory pool so I am looking for some allocator that will do the above without me having to write my own.

Does such an allocator exist and where can I find such an allocator?

I am working on both Linux using GCC and Android using the STLPort.

Edit: Placement new is ok, what I want to minimize is heap walking which is expensive. I would also like all my object to be as close to eachother as possible to minimize cache misses.

Answer 1

It sounds like you may be just using the wrong kind of container: With a list, each element occupies a separate chunk of memory, to allow individual inserts/deletes - so every addition/deletion form the list will require a separate new()/delete().

If you can use a std::vector instead, then you can reserve the required size before adding the items.

Also for deletion, it's usually best not to remove the items individually. Just call clear() on the container to empty. it.

---

Edit: You've now made it clear in the comments that your 'remove the elements during processing' step is removing elements from the middle of the list and must not invalidate iterators, so switching to a vector is not suitable. I'll leave this answer for now (for the sake of the comment thread!)