I need to create a pool of objects to eliminate dynamic allocations. Is it efficient to use std::stack to contain pointers of allocated objects?
I suspect every time I push the released object back to stack a new stack element will be dynamically allocated. Am I right? Should I use std::vector to make sure nothing new is allocated?
Thanks.
Whether a stack is suited for your particular purpose or not is an issue I will not deal with. Now, if you are concerned about the number of allocations, the default internal container for a std::stack is an std::deque<>. It will not need to allocate new memory for the stack in each push (as long as it has space) and when it allocates it does not need to relocate all existing elements as an std::vector<> would.
You can tell the stack to use an std::vector<> as underlying container with the second template argument:
std::stack< int, std::vector<int> > vector_stack;
STL containers of pointers don't do anything with the objects they point to, that's up to you, so you are responsible for not leaking any memory etc. Have a look at Boost Pointer Container Library or try storing the actual objects, you will save yourself hassle in the long run.
If you want to reduce the amount of dynamic allocations made by the container and you know roughly how many objects you need to store, you can use vector's 'reserve()' method, which will preallocate the memory you request in one shot.
You can also specify the number of records you want in the constructor, but this way will create x objects for you and then store them, which might not be want you want.
If, for some technical reason dynamic allocation is out completely, you might want to try using boost::pool as your allocator, (as you know you can specify a different std library memory allocator if you don't want to use the default one).
That said, when I tested it, the default one was always faster, at least with g++ so it may not be worth the effort. Make sure you profile it rather than assume you can out code the standards comity!
Doing ANY allocs during a free is WRONG due to nothrow-guarantees. If you have to do an alloc to do a free and the alloc throws where do you put the pointer? You either quietly capture the exception and leak or propagate the exception. Propagating the exception means objects that use your YourObject cant be put in STL containers. And leaking is, well, leaking. In either case you have violated the rules.
But what data structure to use depends on your object lifetime control idiom.
Is the idiom an object pool to be used with a factory method(s) and freeInstance
YourObject* pO = YourObject::getInstance(... reinitialize parameters ...);
......object public lifetime....
pO->freeInstance();
or a memory pool to be used with a class specific operator new/operator delete (or an allocator)?
YourObject::operator new(size_t);
......object public lifetime....
delete pO;
If it is an object pool and you have an idea about the number of YourObject*'s use vector in released code and deque or preferably a circular buffer (as deque has no reserve so you have to add this where as a dynamically self sizing circular buffer is precisely what you want) in debug code and reserve the approximate number. Allocate LIFO in release and FIFO in debug so you have history in debug.
In the path where there are no free objects, remember to do the reserve(nMade+1) on the YourObject* collection before you dynamically create an object.
(The reason for this reserve is two fold. First, it must be done at createInstance time Second, it simplifies the code. For otherwise you have the possibility of throwing a std::badalloc in freeInstance which may make destructor guarantees hard to guarantee. OUCH! e.g. - class Y has an YourObject* in it and does a freeInstance for that YourObject* in its destructor - if you don't reserve the space for the YourObject* when you make it where do you store that pointer at freeInstance time? If you reserve the space afterwards in getInstance then you have to catch the std::badalloc for the reserve, release the just made YourObject, and rethrow.)
If it is a memory pool then in the memory blocks use an intrusive singly linked list in release and doubly linked list in debug (I am assuming that sizeof(YourObject)>=2*sizeof(void*)) BTW there are a lot of MemoryPool implementations out there. Again allocate LIFO in release and FIFO in debug so you have history in debug.
BTW if you use the factory idiom don't skip on the overloaded getIntances() and add reinit methods. That just opens up the possibility of leaving out a reinit call. The getInstance methods are your "constructors" in the sense that it is they that get the object to the state that you want. Note that in the object pool case you need a freeInstance which may have to do "destructor like" things to the object.
In this case it makes some sense to speak of "public class invariants" and "private class invariants" - the object sits in a limbo state where public class invariants may NOT be satisfied while in the free pool. Its a YourObject as fas as a YourObject is concerned but all of the public class invariants may not be satisfied. It is the job of YourObject::getInstance to both get an instance AND ensure that its public invariants are satisfied. In a complementary fashion freeInstance releases resources that may have been acquired by getInstance to ensure the "public class invariants" were satisfied may be released during the objects "idle time" on the free list.
LIFO in release also has the SIGNIFICANT benefit of caching the last used objects/blocks where as FIFO is guaranteed not to cache if there are a sufficiently large number of objects/blocks - or even page if the number is larger! But you probably already realized this as you decided to use a stack.
strong text