[boost] Library proposal: box

From: Chris Jefferson (chris_at_[hidden])
Date: 2008-08-06 17:04:25

I wish to seek interest in generalising, extending and documenting a
simple but useful library I use personally.

'box' is a simple class which provides an almost standard C++
container on top of a pre-allocated block of memory or range of
iterators. For raw memory this container is a perfect implementation
of vector, except for the constructors. It is possible for the
underlying objects to be already constructed, or have the container
handle construction and destruction.

Simple usages:

box<int> b1(malloc(sizeof(int) * 10), 10); // makes an empty container
of size 10.

assert(b1.size() = 0);
assert(b1.max_size() == 10);
b1.resize(10, 1); // Fills the container with 1s.
b1.push_back(1); // throws std::length_error

box<int> b2(alloca(sizeof(int) * 10), 10); // makes an empty container
on the stack of size 10.

void get_things(b2); // passing 'alloca'ed boxes to functions avoid
heap allocation.

A number of macros exist for automating the creation of containers
with 'alloca'ed memory. Further, a simple alternative implementation
of alloca which uses a parallel stack is provided.

Common use cases:

1) Use 'alloca'ed memory to make a container on the stack.
2) In general allow the use of C++ container idioms (push_back,
resize) while maintaining fully controlled, clear memory management.

Design decisions:

1) Box has no copy constructor or assignment, and will have no move
constructor either, as it seems difficult to give any definition
without too many 'gotchas'.
2) Box does not attempt to implement complex memory management,
3) In general box aims to be as simple as possible, sticking with
fixed size containers and no container copying.

Possible Qs (with I hope correct answers)

Q) Why is this not just boost::range?
A) The container starts empty, and can be inserted into.

Q) Why not implement this as an allocator to give to vector/list?
A) Allocators are a complex and often misunderstood type, and it is
not felt it makes things easier for users to give a different
allocator to vector as opposed to defining a new class.

In particular, getting correct behaviour for the copy constructors of
the container is difficult, and it is not possible to give a correct
definition of max_size, which is more important for small-sized
containers.

Current state:

box is currently in usage in a number of projects, based on a
heavily-hacked SGI vector implementation. As a library the code would
probably be rewritten, and also of course carefully documented.

Chris