[Boost-users] [pool] why no object-pool with O(1) allocation AND O(1) deallocation?!?

dear boost users, boost offers in lib pool the class object_pool. as is stated in the docs, it allows for allocation with O(1) but deallocation need O(n) time. i suppose it has to search the internal list for the position of the object ro be freed. but this could be speed up a lot by using a stack of free objects. if one would like to allocate an object, a pointer to a free memory cell is popped from the stack, if the object should be returned / freed to the pool, that objects pointer is pushed onto the stack. of course this causes memory overhead, but, for example if one would like to implement a really large pool of small objects for a particle system, then O(n) deallocation is prohibitive. so my question is why boost does not offer an alternative version of object_pool with both O(1) alloc and dealloc ? below is my version of a stack based object pool with O(1) both alloc and dealloc. i really do not like my implementation, but i did not know how to do better... template<class T> class Smallobjects_Pool { protected: class Node // a node of a double linked list { public: Node() {prev=next=NULL; idx=-1; } Node* prev; Node* next; int idx; // index to the objects - vector T obj; }; //Node* next(int cur) { return objects[cur].next;} //Node* root() { return _root; } //Node* last() { return _last; } protected: Node* _root; Node* _last; vector<Node> objects; vector<int> free_objects; public: T & operator[](int i){return objects[i].obj;} bool empty() { return _root == NULL;} Smallobjects_Pool(int initial_size) { _root=NULL; _last=NULL; objects.resize(initial_size); free_objects.reserve(initial_size); for(unsigned int a=0;aidx = free_objects.back(); free_objects.pop_back(); if(_root==NULL) { _root=new_obj; new_obj->prev=NULL; new_obj->next=NULL; } else { _last->next=new_obj; new_obj->prev=_last; new_obj->next=NULL; } _last=new_obj; new_obj->obj = t; } class iterator { //protected: public: Node* i; public: iterator(Node* _i) : i(_i) {} ~iterator() {} iterator& operator=(const iterator& other) { i = other.i; return(*this); } // The assignment and relational operators are straightforward bool operator==(const iterator& it) { return(i == it.i); } bool operator!=(const iterator& it) { return(i != it.i); } iterator& operator++() { assert(i && "increment on null pointer"); i = i->next; return(*this); } // Update my state such that I refer to the next element in the SQueue. //Iterator& operator++(int) { Iterator tmp(*this); ++(*this); return(tmp);} T& operator*() { return i->obj; } // Return a reference to the value in the node. I do this instead of returning by value so a caller can update the value in the node directly. T* operator->() { return &(i->obj); } // Return the address of the value referred to. }; iterator begin() { return(iterator(_root));} iterator end() { return(iterator( NULL));} iterator erase(iterator i) { assert(i.i!=NULL && "cannot free null pointer."); free_objects.push_back(i.i->idx); if(i.i == _last) { if(i.i->prev != NULL) _last = i.i->prev; _last->next=NULL; return NULL; } if(i.i == _root) { _root = i.i->next; _root->prev=NULL; return _root; } i.i->prev->next = i.i->next; i.i->next->prev = i.i->prev; return iterator(i.i->next); } };