Chris Baus

C++ pooled_list class alpha release

This is geeky as hell, but I am releasing a C++ pooled_list class. Every time an insert or erase operation is performed on a std::list global operator new is called and generally a trip to the system heap is made. This can be a problem because the heap operation:

Pool allocation addresses these problems by pre-allocating a specific number of elements, and using these elements for insert and erase operations. This of course limits the maximum size of the lists, but I'd argue that allowing data structures to grow unbounded is poor practice anyway.

It was commonly thought that pool allocation could be done by changing the allocators used by the list, but it is now accepted by the C++ community that allocators are fairly useless. My friendly local committee member speculates that the original intention had something to do with near/far pointers in DOS and Win16. Yikes. If you want something other than the default allocation behavior your best bet is to roll your own container. That's what I've done here.

I've gone through a lot of pains to make the interface compatible with the standard list container. I've even implemented obscure functions I'm sure I'll never use, such as unique() and merge().

I think the implementation is pretty cool, if I do say so myself. It uses the std::list class as the underlying data structure. Data alignment is done in a cross platform way. It requires a recent version of boost, which makes the iterator specification something other than a total nightmare. All the memory isn't allocated in one shot. Each element is still allocated individually, but at pool creation time, not list insertion time.

The code requires a significant amount of testing, cleanup and documentation, that's why I'm calling it alpha. You can check it out here: pooled_list.hpp.

Here's a quick example.
// create a pool of 1500 elements.
  switchflow::util::pooled_list < int > ::pool list_pool(1500);

// attach a list to the pool
  switchflow::util::pooled_list < int > ::pooled_list list1(list_pool);

// attach another list to the pool
  switchflow::util::pooled_list < int > ::pooled_list list2(list_pool);

// do list operations...
  list1.push_back(1);

A pool must have a lifetime greater than the lists attached to it. I recommend creating pools at startup. If you are in a situation where you are constantly creating and destroying pools, rethink pool ownership or if pooling is a good choice for your application.

BTW, C++ is not dead. Check out all the job listings on Joel's new job board that require C++. If anything, since so many developers have left for other languages there is a dearth of C++ talent out there.

Send questions and comments to christopher@baus.net.